关于c++:排序算法

11次阅读

共计 2260 个字符,预计需要花费 6 分钟才能阅读完成。

源码地址(gitee)

  • 堆排序源码地址:https://gitee.com/BJFyfwl/Lin…
  • 其余排序办法源码地址:https://gitee.com/BJFyfwl/Lin…

常见排序算法

  • 插入排序:

    • 间接插入排序
    • 希尔排序
  • 抉择排序:

    • 间接抉择排序
    • 堆排序
  • 替换排序:

    • 冒泡排序
    • 疾速排序
  • 归并排序

间接插入排序

  • 核心思想:将一个数插入一段有序区间。

希尔排序

  • 核心思想:

    • 先分组预排序(应用间接插入排序),使整个数组靠近有序(小的数在前,大的数在后)
    • 再间接插入排序
  • 能够将较大的数疾速地挪动到前面,实用于大量数据
  • gap == 1 就相当于间接插入排序。
  • gap 越大,预排越快,预排序越不靠近有序。
  • gap 越小,预排越慢,预排序越靠近有序。

间接抉择排序

  • 遍历数组,选出最大的数,与最初一个数替换。
  • 而后顺次遍历抉择次大的数,与倒数第二个数替换。
  • 如此循环。

堆排序

  • 建堆工夫是 O(N)
  • 排序工夫是 O(logN)
  • 堆只存在两种类型:大根堆和小根堆。
  • 大根堆:根节点是最大的(即孩子节点 < 父亲节点)
  • 小根对:根节点是最小的(即孩子节点 > 父亲节点)
  • 堆在逻辑构造上是齐全二叉树,在物理构造上还是数组模式。所以实现堆时,依然以数组来存储。

堆的下标法则

  • 设父节点下标为 x,右边子节点下标为 y,左边节点下标为 z。
  • y = x*2 + 1;
  • z = x*2 + 2;
  • x =(x – 1)/ 2 或者(y-1)/ 2;

堆排序问题一:

  • 假如数组数据很大(有 10 亿个数,大略 4G 内存),他们存在文件中,取最大的前 k 个数
  • 解决办法:建设一个 k 个数的小根堆,而后将文件中的数顺次取出与根节点比拟,如果比根节点大,则替换根节点,而后向下调整,如此循环,最初这个小根堆中的数据就是最大的前 k 个数。

堆排序问题二:

  • 堆排序:将一个数组升序排列
  • 解决办法:将数组建设小根堆,顺次取根节点的数据,而后将根节点数据与开端数据交换,再删除开端数据(即删除最小的那个数了),而后再向下调整,如此循环即可。

疾速排序

  • 工夫复杂度 O(N * logN)
  • 空间复杂度 O(logN)
  • 稳定性:不稳固

如何取要害数 key

  • 先取数组的第一个数、最初一个数和两头地位的数,而后取这三个数中不是最大也不是最小的那个数作为 key。
  • 这种办法能够防止 key 间接选到最大值或者最小值。

左右指针法快排

  • 一前一后两个指针,抉择一个要害数 key(个别是结尾位或者末位)
  • 如果抉择结尾位为要害数 key,则让 end 向后先走,寻找比 key 小的数,找到小的数后停下。
  • 而后 pre 向前走,寻找比 key 大的数,找到后进行。
  • 而后替换 pre 的值和 end 的值,替换完后,end 持续向后挪动。
  • 始终循环,直到 pre 和 end 相遇为止,相遇时的值肯定是比 key 小的,所以替换 key 和 pre 的值
  • 这样,key 的数就会被挪动到整个数组的两头值地位,它右边的都比它小,左边的都比它大
  • 最初应用递归。

挖坑法快排

  • 另外定义一个变量 sum,用来保留第一个 pre,pre 的地位则空进去了。
  • 而后 end 先向前挪动,寻找比 sum 小的数,找到后将 end 与 pre 替换,当初 end 的地位为空。
  • 而后 pre 向前挪动,寻找比 sum 大的数,找到将 pre 与 end 替换,当初 pre 的地位为空。
  • 而后再是 end 向前挪动………………
  • 这样循环直到 pre 和 end 相遇为止,相遇时的地位为空,再将 sum 的值放到相遇的地位上。
  • 这样这个数的右边都是比它小的数,左边都是比它大的数。
  • 最初应用递归即可。

前后指针法快排

  • 起始地位,pre 在第一位,end 在第二位。
  • 而后 end 向后挪动,寻找比 key 小的值,找到后,pre++,而后替换 pre 和 end 的值。
  • 而后持续 end 向后挪动,直到 end 拜访完为止
  • 最初在替换 pre 和 key 的值
  • 这样 key 这个数的右边都是比它小的数,左边都是比它大的数。
  • 最初递归即可。

递归式快排的小区间优化

  • 当数据量很大时,在最初几层递归时,会呈现大量递归(呈现大量递归时可能会栈溢出),然而每个递归解决的数据较小。
  • 所以为了防止最初几层的递归,在数据量较小时,间接应用插入排序
  • 这样大数据处理的最初几层递归,则变为插入排序,能够缩小大量递归,升高解决工夫。

非递归快排

  • 应用循环代替递归。
  • 为了防止栈溢出,本人创立一个栈(malloc 创立的空间是在堆中的),应用循环来进行排序,其实质是本人模仿栈的出栈和压栈。
  • 而后将单趟排序隔离进去,压栈时将 pre 和 end 的下标压栈,出栈将 pre 和 end 传给单趟排序,并且将栈中的 pre 和 end 打消,
  • 循环如此即可排序。

计数排序

  • 外围思路:依据所给数组的最大值与小值,开拓等大小的数组,并且初始化为 0,遍历数组,将该整数对应下标的新数组的地位加 1。(相当于一种映射)
  • 例如:给定一个数组 {5,6,7,8,9,6}
  • 最大值为 9,最小值为 5,开拓新数组 arr 大小为 5。
  • 遍历数组,第一个数为 5,对应下标为 0,即 arr[0]++,
  • 如此遍历残缺个数组即可。

适用范围

  • 只适宜数据范畴比拟集中的数组,如果数据集中效率还是很高的。
  • 并且只适宜整数,浮点数和字符串等都不适宜。

归并排序

  • 核心思想:将数组切分成两份,如果右边有序,左边也有序,那么两份归并,整个数组都是有序的了。

归并的海量数据处理(外排序)

  • 例如:一个 4G 的文件,文件中是一些整数,将这些整数排序,零碎提供内存为 512M

    • 将文件分成 8 等分,而后别离将小文件的数据读取到内存中进行排序(不要用归并,因为归并有 O(N) 的空间复杂度)
    • 这样 8 份小文件中的数据都是有序的了。
    • 而后再将 8 分小文件两两进行归并,合称 4 份有序文件
    • 而后再归并,最初归并成一个有序的大文件。

算法复杂度及稳定性

  • 数组中雷同的值,排完序后绝对地位不变,就是稳固的,否则就是不稳固。
正文完
 0