一、前言
本章主要讲解：
八大排序的基本知识及其实现
注：这里的八大排序指直接插入，希尔，选择，堆排，冒泡，快排，归并，计数
- 八大排序汇总图：
二、排序概念及应用
1、概念
排序：
所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作
稳定性：
假设在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的(记录的相对次序保持不变)；否则称为不稳定的
内部排序：
数据元素全部放在内存中的排序
外部排序：
数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序
2、排序应用
- 示例：搜索电影时
三、排序算法接口展示
// 排序实现的接口 // 插入排序 void InsertSort(int* a, int n); // 希尔排序 void ShellSort(int* a, int n); // 选择排序 void SelectSort(int* a, int n); // 堆排序 void AdjustDwon(int* a, int n, int root); void HeapSort(int* a, int n); // 冒泡排序 void BubbleSort(int* a, int n) // 快速排序递归实现 // 快速排序hoare版本 int PartSort1(int* a, int left, int right); // 快速排序挖坑法 int PartSort2(int* a, int left, int right); // 快速排序前后指针法 int PartSort3(int* a, int left, int right); void QuickSort(int* a, int left, int right); // 快速排序 非递归实现 void QuickSortNonR(int* a, int left, int right) // 归并排序递归实现 void MergeSort(int* a, int n) // 归并排序非递归实现 void MergeSortNonR(int* a, int n) // 计数排序 void CountSort(int* a, int n)
四、插入排序
1、直接插入排序
直接插入排序是一种简单的插入排序法
- 基本思想：
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列
- 动图展示：
- 实现代码：
//直接插入排序 void InsertSort(int* a, int n) { assert(a);//传入数组不为空指针 int i; for (i = 0; i < n - 1; i++) //注意：最后一个要插入数据的下标为n-1，此次插入有序数列的end下标为n-2 { int end = i;//标记当前有序数列的最后一个位置下标 int x = a[end + 1];//要插入的数据为有序数列的后一个位置 while (end >= 0)//进行当前趟次的插入排列 { //升序 if (a[end] >x)//有序数列的数据比插入数据大，则往后挪动 { a[end + 1] = a[end]; end--;//向前找，进行排列数据 } else//遇到不大于要插入数据，则不再往前找 { break; } } a[end + 1] = x;//将要插入数据插入到不大于该数据的后一个位置 } }
- 直接插入排序的特性总结：
- 元素集合越接近有序，直接插入排序算法的时间效率越高
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)，它是一种稳定的排序算法
- 稳定性：稳定
2、希尔排序
- 基本思想：
对于直接插入排序在面对一些特殊情况时，效率非常低（例如：将降序排成升序），而对于已经接近排好的序列，效率非常高
希尔排序在直接排序之前，进行预排列，将某些极端数据更快的排列到数列前面，构成一个接近排列好的序列，最后再进行一次直接插入排序
预排列的原理也是插入排列，只不过这里的将数组分成了gap组，分别对每一个小组进行插入排序
如下动图：对于升序，当gap从5 – 2 – 1的过程中，排在后面的数值小的数能更快排到前面，当gap为1的时候实际上就是进行了一次插入排序
动图展示：
// 希尔排序 void ShellSort(int* a, int n) { //多组预排（一锅炖）+插排 int gap = n; while (gap > 1) { gap /= 2;//保证最后一次分组gap==1,即最后一次为直接插入排序 //gap = gap / 3 + 1;//也可以写成这样，除3预排的效率相比于除2的好点 for (int i = 0; i < n - gap; i++) { int end = i; int x = a[end + gap]; while (end >= 0) { if (a[end] > x) { a[end + gap] = a[end]; end-=gap; } else break; } a[end + gap] = x; } } }
- 希尔排序的特性总结：
、
