九种排序算法(重要！!)

分类：（九种排序算法)

1、插入排序：直接插入排序、二分插入排序、希尔排序；

2、选择排序：简单选择排序、堆排序

3、交换排序：冒泡排序、快速排序

4、归并排序

5、基数排序

---

一、插入排序

1、直接插入排序（稳定排序）

基本思想：将待排序的记录，从后往前找位置，一个个比较，插入到合适的地方。每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。

 时间复杂度：平均时间复杂度为O(n^2)。（ps:与文件的初态有很大关系，若文件的初态为正序，则每个待插入的记录只要比较一次就可找到合适位置插入，算法的时间复杂度为O(n)；若初态为反序，则第i个记录需比较i+1次才能插入，所以时间复杂度为O(n^2),这是最坏情况。

2、二分插入排序：（稳定排序）

基本思想：首先必须是排好序的数组，然后通过二分查找，找到合适的位置，插入。

时间复杂度：平均时间复杂度为O(n^2)

3、希尔排序（不稳定排序）

 基本思路：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<...<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。

    时间复杂度：平均时间复杂度为O(nlogn)    

二、选择排序

1、简单选择排序：（不稳定排序）

基本思路：每一趟从待排序的数据元素中选择最小（或最大）的一个元素作为首元素，直到所有元素排完为止。

2、堆排序：(不稳定排序）

基本思路:初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储序，使之成为一个堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。

从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。

时间复杂度：平均时间复杂度为O(nlogn) 

三、交换排序

1、冒泡排序（稳定排序）

基本思路：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

 时间复杂度：平均时间复杂度为O(n^2)。

2、快速排序（不稳定排序）

基本思想：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。

时间复杂度：平均时间复杂度为O(nlogn) 

四、归并排序(稳定排序）

 基本思路：将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

平均时间复杂度为O(nlogn)

代码如下：

五、基数排序（稳定排序）

基本思路：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。从最低位开始，依次进行排序，从最低位一直排序到最高位,数列就变成一个有序序列。

时间复杂度：O(d(n+r)),d为位数，r为基数