概述
排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，这里八大排序就是内部排序，指直接插入，希尔，选择，堆排，冒泡，快排，归并，计数。
下面让我们来共同学习这八大排序吧！🤗🤗🤗
什么是外部排序：
外排序是数据量较大,内存放不下,数据放到外部磁盘空间,一般使用归并排序进行外排序
假设内存为512m,给10亿个数据,然后内存每次读取512m的数据,排序完成后返回给磁盘,然后重复这个过程,直到拍完,然后外部的小文件,再经过归并,即可得到一个有序的数据.
一、插入排序
1、直接插入排序
基本思想：
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中（我们假设有序），直到所有的记录插入完为止，得到一个新的有序序列。就像是我们玩扑克牌时按顺序大小整理好牌的过程
动图展示 ：
实现代码：
void InsertSort(int* arr, int n) { //我们默认序列有序，从一个数据开始，即只有一个数据有序 for (int i = 0; i < n - 1; i++) // 最后一个插入数据下标为n-1，此次end下标为n-2 { int end = i; //end标记当前有序序列的最后一个位置下标 int tmp = arr[end + 1];// 要插入的数据的位置为end后面 while (end >= 0) //利用end来进行单趟遍历排序 { //升序 if (arr[end] > tmp) //若原数据比插入数据大，则后移一位 { arr[end + 1] = arr[end]; end--; //向前遍历，进行数据排序 } else //原数据小于插入数据，直接break { break; } } arr[end + 1] = tmp; } }
相关分析 ：
对于插入排序：
时间复杂度
- 最坏：逆序 （计算类似等差数列） --O(N^2)
- 最好：顺序 （数据有序） ---O(N)
待排序元素集合越接近有序，直接插入排序算法的时间效率越高
2、希尔排序
希尔排序是1959 年由D.L.Shell 提出来的，相对直接插入排序有较大的改进。希尔排序又叫缩小增量排序.。希尔排序是对直接插入排序的优化。
基本思想：
- 希尔排序 = 预排序（分组插入排序） + 直接插入排序（最后一次为整体排序）
- 我们先选定一个整数gap，间隔为Gap的数据为一组,然后对这组数据进行排序（预排序）,再分组,再排,直到数组被分完.
- 将Gap减小,继续分组,排序.
- 最后Gap设为1,此时数据基本有序，即进行直接插入排序,得到有序数组
动图展示：
代码实现：
void ShellSort(int* arr, int n) { //多组预排,插排 int gap = n; while (gap > 1) //当gap为1时，最后一次为直接插入排序，循环结束 { gap = gap / 3 + 1; //除3能保证最后一次分组 gap == 1，即进行直接插入排序 for (int i = 0; i < n - gap; ++i) //++i实现gap组并排，减少循环调用 { int end = i; //end 为最后一个有效数据下标 int tmp = arr[end + gap]; while (end>=0) //希尔的单趟排序实现 { if (arr[end] > tmp) { arr[end + gap] = arr[end]; end -= gap; } else { break; } } arr[end + gap] = tmp; } } }
相关分析：
希尔排序对直接插入排序的优化在于：优化了直接插入排序对逆序数据排序效率很差的缺点。我们将数据进行了一个gap分组，然后进行组预排序，这样下来数据会越来越接近有序，等到最后一次排序的时候，我们无需进行大量的数据遍历，只需遍历个别不满足升序的数据即可。这样希尔排序效率就会比直接插入排序高很多。
对于希尔排序的时间复杂度：计算是不好计算的，需要进行数学推导，推导出来平均时间复杂度： O(N^1.3—N^2）
二、选择排序
1、直接选择排序
基本思想：
每次将数组遍历一遍，在数组[0,n]中选取最小（最大）的数,存放在序列的起始（或者末尾）位置，在[1,n-1]再次遍历选取,交换,缩减,直到全部待排序的数据元素排完
优化版：每次遍历待排序数据找出最大和最小的数据，分别排列到序列起始和末尾
动图展示：
代码实现：
void Swap(int* p1, int* p2) { int* tmp = *p1; *p1 = *p2; *p2 = *tmp; } //一般版 void SelectSort(int* a, int n) { int begin = 0, end = n - 1; while (begin<end) { int min = begin; for (int i = begin; i <= end; i++) { if (a[i] < a[min]) //遍历最小数据并记录下标 min = i; } Swap(&a[begin], &a[min]); begin++; //缩小范围 } } //优化版 void SelectSort(int* a, int n) { int begin = 0, end = n - 1; while (begin < end) { int max = begin, min = begin; for (int i = begin; i <= end; i++) { if (a[i] > a[max]) max = i; if (a[i] < a[min]) min = i; } if (begin == max) //若最大数据在begin位置，与begin下标重合，则需进行修正 max = min; Swap(&a[begin], &a[min]); //进行交换 Swap(&a[end], &a[max]); begin++; end--; //接着缩小遍历范围 } }
相关分析：
直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用。其稳定性也较差
2、堆排序
基本思想：
学过二叉树我们知道堆排序是指利用堆（数据结构）进行选择数据的一种排序算法。在已经建好堆的情况下，升序建大堆，降序建小堆，通过堆来选择数据,向下调整算法,得到小数(大数),然后再与堆底数据进行交换。每重新调整堆时，传给向下调整算法的数组个数要减1，数组的最后一个元素已经变得有序了，因此不需要我们调整了。
图示（大堆排序）：
代码实现：
void Adjustdown(int* a, int n, int parent) { int child = parent * 2 + 1; //首先假设最大孩子为左孩子 while (child < n) { //找到数据大的子结点 if (child + 1 < n && a[child + 1] > a[child]) //可能父节点没有右孩子 { ++child; } //父节点数据小于子节点就交换 if (a[parent] < a[child]) //大堆调整 { Swap(&a[parent], &a[child]); //更新下标 parent = child; child = parent * 2 + 1; } else//否则直接break break; } } // 堆排序(升序) void HeapSort(int* a, int n) { int i; for (i = (n - 1 - 1) / 2; i >= 0; i--) { Adjustdown(a, n, i); } //交换调整 for (i = n - 1; i >= 0; i--) { Swap(&a[0], &a[i]);//与当前堆尾数据交换 Adjustdown(a, i, 0);//对交换后堆顶数据进行向下调整 } }
相关分析：
- 堆排序使用堆来选数，效率就会高出很多
- 核心向下调整算法是实现排序的精髓，建堆同样用到
三、交换排序
1、冒泡排序
基本思想：
每次遍历待排序数组，对相邻数据进行比较，将值较大的数据向序列尾部移动，值较小的数据向序列前部移动。
动图展示：
代码实现：
void Bubblesort(int* a, int n) { for (int i = 0; i < n; i++)//遍历次数 { for (int j = 0; j < n - i - 1; j++)//向后冒泡 ,控制边界 { if (a[j] > a[j + 1])//如果前一个值大于后一个值,交换. { swap(&a[j], &a[j + 1]); } } } } //优化 void BubbleSort(int* a, int n) { for (int j = 0; j < n; ++j) { int exchange = 0; for (int i = 1; i < n-j; ++i) { if (a[i - 1] > a[i]) { Swap(&a[i - 1], &a[i]); exchange = 1; } } // 一趟冒泡过程中，没有发生交换，说明已经有序了，不需要再处理 if (exchange == 0) { break; } } }
相关分析：
我们可以做一个简单的优化，如果我们排序的某一趟每个元素都不用交换，则说明要排序的元素已经有序，那么后面的排序就可以直接跳出循环了。
2、快速排序
2.1 hoare版本
基本思想：
我们将左边值设为key,然后右边right先走,找小的,比key小停下来,然后左边left走找比key大,然后交换左边右边，继续上述过程，直至left和right相遇，此时的值一定是比key小的值，我们再把key和这个相遇位置的值进行交换，此时key所在的位置，左边的数据一定比key值小，右边的数据一定比key值大，即key放到了合适的位置上。重复此过程进行递归，直至所有的元素都处在合适位置。
动图展示：
代码实现：
int HoareSort(int* arr, int left, int right) { int key = left; //我们默认key为左边值 while (left < right) { while (left < right && arr[right] >= arr[key]) //找小 { right--; } while (left < right && arr[left] <= arr[key]) //找大 { left++; } Swap(&arr[left], &arr[right]); } Swap(&arr[key], &arr[left]); key = left; return key; } void QuickSort(int* arr, int begin, int end) //快排hoare版 { if (begin >= end)//递归结束条件 { return; } int key = HoareSort(arr, begin, end); QuickSort(arr, begin, key - 1); //递归key左边数组排序 QuickSort(arr, key + 1, end); //递归key右边数组排序 }
相关分析：
Hoare版本的快排需要注意的地方挺多的：
如果key后面的每个数都比key小或大的话，那left向后面找或right向前面找，会产生越界访问的问题，所以我们选择在if语句的判断部分逻辑与&&保证left小于right，以免产生越界访问的问题。
在if语句的判断部分，找的数据一定得比key小或大的。因为若相等会产生死循环。
对次的优化：
我们可以对key值的选取进行优化，采用三数取中法让我们选取的key数据在序列中的位置尽量靠中间，以提高递归的效率。同时，递归建立的栈帧数量会随着递归深度的增加而增加，为了避免递归深度太深，造成栈溢出的问题。我们采用小区间优化，当递归区间的数据量较小的时候，采用直接插入法进行排序。
相关代码：
//三数取中 int GetMidIndex(int *arr, int begin, int end) { int mid = (begin + end) / 2; if (arr[begin] > arr[end]) { if (arr[end] > arr[mid]) { return end; } else if (arr[begin] < arr[mid]) { return begin; } else { return mid; } } else// arr[begin] < arr[end] { if (arr[mid] < arr[begin]) { return begin; } else if (arr[end] > arr[mid]) { return mid; } else { return end; } } }
//对小区间优化 void QuickSort(int* arr, int begin, int end) { if ((end - begin) < 1)//递归结束条件 { return; } if ((end - begin + 1) < 15) { InsertSort(arr + begin, end - begin + 1); } else { int key = PartSort1(arr, begin, end); QuickSort(arr, begin, key - 1); QuickSort(arr, key + 1, end); } }
