[数据结构与算法]数据结构(c语言)--九大排序算法总结

数据结构(c语言)–排序算法总结

一：总体介绍

1、排序分类、时间、空间复杂度

2、算法的稳定性

? ? 稳定性：经过排序后，使得关键字相同元素保持原顺序当中的相对位置保持不变。

3、内部排序和外部排序

? ? 内部排序：在排序期间，所有的元素全部存放在内存当中的排序。

? ? 外部排序：在排序期间，无法全部同时存放在内存中，必须在排序的过程中根据要求不断的在内存、外存之间移动的排序。

二：九大排序分类（单独记录）

1、插入排序

• 直接插入排序
• 折半插入排序
• 希尔排序

2、交换排序

• 冒泡排序
• 快速排序

3、选择排序

• 简单选择排序
• 堆排序

4、归并排序和基数排序

三：内部排序算法的比较

1. 从时间复杂度看：
   ??简单选择排序、直接插入排序和冒泡排序平均情况下为O(nn)，过程比较简单，但是冒泡和直接插入排序的最好情况下的时间复杂度为O(n)；简单直接排序和序列初始状态无关。
   ??堆排序:可在线性时间内完成建堆操作，且在O(log2n)内完成排序的过程。
   ??快速排序：最坏情况下时间会达到O(nn)，但是快排的平均性能可以达到O(nlog2n)。
   ??归并排序：与初始序列的排序无关，最好、最坏和平均的时间复杂度为O(nlog2n)。

2. 从空间复杂度看：
   ??简单选择排序、插入排序、冒泡排序、希尔排序、堆排序都仅需要常数个辅助空间。
   ??快排在空间上主需要一个小的辅助空间O（log2n）。
   ??归并排序需要借助于多个辅助空间用于元素的辅助O(n)。

3. 从稳定性角度看：
   ??插入、冒泡、归并、基数排序都是稳定的。
   ??简单选择排序、快速排序、希尔排序、堆排序都是不稳定的排序。

4. 从过程特征看：
   ??采用冒泡排序和堆排序在每趟处理后都能产生当前的最大值或者最小值。
   ??快速排序一趟处理完成后能确定一个元素的位置。

四：内部排序算法的应用（小结）

1. 当n较小，可采用直接插入排序或者简单选择排序。（当记录本身的信息量比较大的时候，用简单选择排序）
2. 若序列的初始状态已按照关键字基本有序，则选用直接插入或者冒泡排序为好
3. 若n较大，则应采用时间复杂度为O(log2n)的排序方法：堆排序、快速排序（基于比较较的内部排序中最好的方法）、归并排序；
   ??当待排序的关键字随机分布时，快排的平均时间最短；
   ??要求算法的稳定选择归并排序；
   ??要求所需的辅助空间最少时，堆排序最好，而且相对于快拍不会出现最好、最坏的情况。
4. 当n很大，记录的关键字的位数较少，且可以分解的时候，采用基数排序较好。.