排序算法总结-各种排序算法总结含代码

1、排序算法总结 | 各种排序算法总结含代码【汇总】排序算法总结 " />插入排序原理依次选择一个待排序的数据，插入到前边已排好序的序列中。性能时间复杂度为 O(N )，空间复杂度为 O(1) 。算法是稳定的，比 较次数和交换次数都与初始序列有关。优化直接插入排序每次往前插入时，是按顺序依次往前找，可在这 里进行优化， 往前找合适的插入位置时采用二分查找的方式， 即折半 插入。折半插入排序相对直接插入排序而言：平均性能更快，时间复 杂度降至 O(NlogN) ，排序是稳定的， 但排序的比较次数与初始序列 无关，总是需要 foor(log(i)+1 次排序比较。使用场景当数据基本有序

2、时，采用插入排序可以明显减少数据交换和数 据移动次数，进而提升排序效率。代码希尔排序原理插入排序的改进版，是基于插入排序的以下俩点性质而提出的改进方法：插入排序对几乎已排好序的数据操作时，效率很高，可以达到 线性排序的效率。但插入排序在每次往前插入时只能将数据移动一位，效率比较所以希尔排序的思想是：先是取一个合适的 gap缩小间隔 gap ，例如去 gap=ceil(gap/2) ，重复上述子序列划分和排序直到，最后 gap=1 时，将所有元素放在同一个序列中进行插入 排序为止。性能开始时， gap 取值较大，子序列中的元素较少，排序速度快， 克服了直接插入排序的缺点 ;其次， gap 值逐渐

3、变小后，虽然子序列 的元素逐渐变多， 但大多元素已基本有序， 所以继承了直接插入排序的优点，能以近线性的速度排好序。代码选择排序原理每次从未排序的序列中找到最小值，记录并最后存放到已排序序列的末尾性能时间复杂度为 O(N )，空间复杂度为 O(1) ，排序是不稳定的 (把最小值交换到已排序的末尾导致的 )，每次都能确定一个元素所在的 最终位置，比较次数与初始序列无关。代码快速排序原理分而治之思想：Divide ： 找 到 基 准 元 素 pivot ， 将 数 组 Ap.r 划 分 为Ap.pivotpos-1 和 Apivotpos+1 q ，左边的元素都比基准小，右边的元素都比基准大 ;C

4、onquer ：对俩个划分的数组进行递归排序 ;Combine ：因为基准的作用，使得俩个子数组就地有序，无需 合并操作。性能快排的平均时间复杂度为 O(NlogN) ，空间复杂度为 O(logN) ， 但最坏情况下，时间复杂度为 O(N )，空间复杂度为 O(N); 且排序是 不稳定的， 但每次都能确定一个元素所在序列中的最终位置， 复杂度 与初始序列有关。优化当初始序列是非递减序列时，快排性能下降到最坏情况，主要因为基准每次都是从最左边取得，这时每次只能排好一个元素。所以快排的优化思路如下： 优化基准，不每次都从左边取，可以进行三路划分，分别取最左边，中间和最右边的中间值，再交换到最左边进

5、行排序 ;或者进行随机取得待排序数组中的某一个元素，再交换到最左边，进行排序。在规模较小情况下，采用直接插入排序代码归并排序原理分而治之思想：Divide ：将 n 个元素平均划分为各含 n/2 个元素的子序列 ;Conquer ：递归的解决俩个规模为 n/2 的子问题 ;Combine ：合并俩个已排序的子序列性能时间复杂度总是为 O(NlogN) ，空间复杂度也总为为 O(N) ，算 法与初始序列无关，排序是稳定的。优化优化思路：在规模较小时，合并排序可采用直接插入 ;在写法上，可以在生成辅助数组时，俩头小，中间大，这时不 需要再在后边加俩个 while 循环进行判断，只需一次比完。代码1

6、0堆排序原理堆的性质：是一棵完全二叉树;反之为最每个节点的值都大于或等于其子节点的值，为最大堆 小堆。11堆排序思想：将待排序的序列构造成一个最大堆，此时序列的最大值为根节点依次将根节点与待排序序列的最后一个元素交换再维护从根节点到该元素的前一个节点为最大堆，如此往复，最终得到一个递增序列性能时间复杂度为 O(NlogN) ，空间复杂度为 O(1) ，因为利用的排序空间仍然是初始的序列，并未开辟新空间。算法是不稳定的，与初始序列无关。12使用场景想知道最大值或最小值时， 比如优先级队列， 作业调度等场景代码计数排序原理先把每个元素的出现次数算出来，然后算出该元素所在最终排 好序列中的绝对位置

7、（最终位置 ），再依次把初始序列中的元素，根据 该元素所在最终的绝对位置移到排序数组中。13性能时间复杂度为 O(N+K) ，空间复杂度为 O(N+K) ，算法是稳定 的，与初始序列无关，不需要进行比较就能排好序的算法。使用场景算法只能使用在已知序列中的元素在 0-k 之间，且要求排序的 复杂度在线性效率上。代码桶排序14原理根据待排序列元素的大小范围，均匀独立的划分 M 个桶将N 个输入元素分布到各个桶中去再对各个桶中的元素进行排序此时再按次序把各桶中的元素列出来即是已排序好的性能15时 间 复 杂 度 为 O(N+C)O(C)=O(M(N/M)log(N/M)=O(NlogN-NlogM) ，空间复杂度为O(N+M) ，算法是稳定的，且与初始序列无关。使用场景算法思想和散列中的开散列法差不多，当冲突时放入同一个桶 中;可应用于数据量分布比较均匀，或比较侧重于区间数量时。基数排序原理对于有 d 个关键字时，可以分别按关键字进行排序。有俩种方法：16MSD ：