源码地址（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 份有序文件
- 而后再归并，最初归并成一个有序的大文件。
算法复杂度及稳定性
- 数组中雷同的值，排完序后绝对地位不变，就是稳固的，否则就是不稳固。