C语言实现八大排序

要努力，但不要着急，繁花锦簇，硕果累累都需要过程！

 

前言：

在现实生活中，我们经常需要对数据进行升序和降序的排序，当数据量比较大的时候，就对排序算法的时间复杂度提出了更高的要求，下面我们分别来看看八种排序算法的时间复杂度和空间复杂度

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

1.插入排序：

1.直接插入排序：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

升序为例：

直接插入排序的特性总结：

1 . 元素集合越接近有序，直接插入排序算法的时间效率越高

2. 时间复杂度：

最好的情况：（已经有序）O(N)

最坏的情况：O(N^2)

3. 空间复杂度： O(1 )，它是一种稳定的排序算法

2.希尔排序：

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个gap 组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达gap=1时，所有记录在统一组内排好序。

实现思路：

1.预排序：

目的：接近有序

2.以gap为间隔进行直接插入排序

例：将数据：9，8，7，6，5，4，3，2，1排成升序：

希尔排序的特性总结：

1 . 希尔排序是对直接插入排序的优化。

2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就 会很快。这样整体而言，可以达到优化的效果。

gap的选取：

1.gap = gap / 2   2.gap = gap / 3 + 1(保证gap最后一定是1)

3.时间复杂度：O(N^1.3)

4.空间复杂度：O(1)

2.选择排序：

1.直接选择排序：

每一次从待排序的数据中选出最小和最大的元素，放在起始位置和末尾，直到将全部待排序的数据元素排完

例：将9，8，7，6，5，4，3，2，1，0排成升序

 实现思路：mini找最小的元素，maxi找最大的元素，然后将最大的元素放到end的位置，最小的元素放到begin的位置

直接选择排序特性总结：

时间复杂度为O(N);

空间复杂度为O(1)；

2.堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是 通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

例：将0，1，2，3，4，5，6，7，8，9排成降序

实现思路：首先将数据采用向下调整的方法建成小堆，然后通过向下调整的方法选数交换排序：

建堆详情：建堆链接

堆排序的特性总结：

1.利用建堆的特性进行选数排序；

2.时间复杂度为O(N*logN);

3.空间复杂度为O(1);

3.交换排序：

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排 序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

1.冒泡排序：

实现思路：每一次通过遍历数据，前一个数据比后一个数据大就交换(升序)

例：将9，8，7，6，5，4，3，2，1数据排成升序：

  

冒泡排序的特性总结：

1.时间复杂度为O(N);

2.空间复杂度为O(1);

2.快速排序：

1.递归实现：

快速排序是Hoare于1 962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右 子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

实现思路：单趟排序，分区间，递归子区间

第一种单趟排序方式：Hoare排序

单趟排序：

单趟排序图例演示：

第二种单趟排序：挖坑法：

图例演示： 

 第三种单趟排序：双"指针"法

 图例演示：

 

  例：将9，8，7，6，5，4，3，2，1，0排成升序：

 分区间：

 递归子区间：

 

递归终止的条件：left>=right 

快速排序的时间复杂度：

假设有N个数据：

递归调用的深度为logN

排序数据：1+2+3+……+N-1+N-2 ==>  N

时间复杂度：O(N*logN)

快速排序的的缺点：针对有序或接近有序的数据

假设有N个数据：

递归调用的深度为N

排序数据：1+2+3+……+N-1+N-2 ==>  N

时间复杂度：O(N^2)

优化： 三数取中：比较起始位置和中间位置以及末尾的数据大小，取中间数据做key

递归子区间优化：小区间优化

假设递归深度为h:

假设第三层的数据为8，最后三层总递归调用次数占总递归次数的80%，所以当right-left<=8的时候采用插入排序： 

2.非递归实现： 

实现思路：建立一个栈，先向栈中放入区间数据，然后出栈，进行单趟排序，当left>=right的时候不再执行单趟排序，继续出栈顶数据，直到栈为空(模拟递归的过程)

栈详解：栈的实现链接

3.归并排序

方法一：递归实现归并排序：

实现思路：将一个大区间的数据分成若干个小区间的数据进行排序，采用先分解后合并的方法进行排序；首先递归分解左区间直到剩余一个数据的时候默认有序，然后递归右区间，有两个数据的时候（升序）比较取小的数据尾插到开辟好的空间，然后拷贝到原数组中。

图解：

方法二：非递归实现归并排序：

实现思路：选取一个gap变量，两两归并（取小的数据尾插到开辟好的临时空间中），每组gap个数据

图解：

 

存在的问题：当数据个数不是2^n个的时候就会存在越界访问的情况！

 

 原因：

 

 

 

存在越界的三种情况： 

1.第一组right1越界；

2.第二组部分越界；

3.第三组全部越界；

改正思路：当遇到越界访问的时候就跳出循环，并且避免整齐拷贝的时候对于跳出循环漏掉数据，则采用归并一个数据就拷贝一个数据

改正后的代码：

 

归并排序特性总结：

1.归并排序的缺点是需要O(N)的空间复杂度；

2.时间复杂度：O(N*logN);

3.稳定性：稳定

4.非比较排序

1.计数排序

实现思路：1.统计相同元素出现的次数;2.根据统计的次数对数据进行排序

实现方法：采用相对映射的方法

1.开辟max-min+1的空间大小；

2.a[i]-min就是相对映射的位置

特点：适用于相对集中范围的数据进行排序 

计数排序的特性总结

时间复杂度：O(N+range)

空间复杂度：O(range)