排序算法（九大）- C++实现

---

目录

基数排序

快速排序 

Hoare版本（单趟）

快速排序优化

三数取中

 小区间优化

挖坑法（单趟）

前后指针法（单趟）

非递归实现（快排）

归并排序

非递归实现（归并）

计数排序

冒泡排序

插入排序

希尔排序（缩小增量排序）

选择排序（优化版本）

堆排序

---

基数排序

实现原理：

        将所有待比较值统一为同样的数位长度，数位端的数据前面补0，然后，从最低位开始，依次进行一次排序，这样不断从最低位到最高位排序完成之后，数据就有序了。

实现步骤：

（1）、先确实数据中最高位是几位数（定义为 K）。

（2）、创建下标为 0~9 （共10个）的队列，因为所有的数字元素每一位都是由 0~9 这10个数组成的。

（3）、依次判断每个数据的 个位，十位，到 K位（共K次），依次将数据进行分发到下标对应的队列中，然后拿取回原数组中，最后到第K次后数据就有序了。

一组数据演示：

再将数据依次从每个队列的队头中拿取出来：

 最后一次拿取分发：

代码实现：

Sort.h 中函数实现代码

#pragma once
#include <iostream>
#include <queue>
using namespace std;
#define K 3 //最高位次数
#define RaIndex 10std::queue<int> q[RaIndex];//用于存储分发的数据// value: 278    k: 0   ->   8
int GetKey(int value, int k)
{int key = 0;while (k >= 0){key = value % 10;value /= 10;k--;}return key;
}//分发数据
void Distribute(int arr[], int left, int right, int k)
{for (int i = left; i < right; i++) //[left,right){//按照位数以此分发int key = GetKey(arr[i], k);//按照 key的下标分发的对应下标的队列q[key].push(arr[i]);}
}//接受数据
void Receive(int arr[])
{int index = 0;//从各个队列中依次回收数据for (int i = 0; i < RaIndex; i++){while (!q[i].empty()){arr[index] = q[i].front();q[i].pop();index++;}}
}//基数排序
void RadixSort(int arr[], int n)
{for (int i = 0; i < K; i++){//分发数据Distribute(arr, 0, n, i);//接受数据Receive(arr);}
}

 Test.cpp 中测试代码：

#include "Sort.h"int main()
{int arr[] = { 267,89,98,34,7,984,58,83,384,150,384,394,463 };int n = sizeof(arr) / sizeof(arr[0]);cout << "排序前：" << endl;for (int i = 0; i < n; i++){cout << arr[i] << " ";}cout << endl;RadixSort(arr, n);cout << "排序后：" << endl;for (int i = 0; i < n; i++){cout << arr[i] << " ";}cout << endl;return 0;
}

最后进行数据测试：

---

快速排序 

快速排序是一种基于二叉树结构的交换排序算法，其基本思想：

        任取待排序元素序列中的某元素作为基准值，按照该基准值将待排序列分为两个子序列，左子序列中所有的元素均小于基准值，右子序列中所有元素均大于基准值，然后左右序列递归实现该过程，直到所有元素都排序在相对应位置上为止。

Hoare版本（单趟）

单趟动图演示：

  单趟排序基本步骤：

（1）、选出一个key值作为基准，一般是最左边或者最右边。

（2）、定义两个向指针一样的下标（L 从左往右走 和 R 从右往左走），如果key值选的是最左边的，就需要R先走，如果key值选的是最右边的，就需要L先走。

（3）、若R走过程中，遇到小于key的就停下，然后L开始走，遇到大于key的就停下，随后交换R和L位置的值，然后再次开始走，直到L撞上R，或者R撞上L，然后交换key与相撞位置的值即可。（选取左边的值为key）

当L撞上R时：

 当R撞上L时：

（4）、左边序列都是小于key的，右边序列都是大于key的，然后再次对两个序列进行单趟排序，直到左右序列只有一个数据或者左右序列不存在即可，此时就是数据就是有序的了。

代码实现：

//快排的单趟排序  [] 左闭右闭
int SingSort(int arr[], int left, int right)
{//选取一个key值 左边int keyi = left;while (left < right){//右边先走，右边找比keyi小的 相等也跳过，否则可能会死循环while (left < right && arr[right] >= arr[keyi]){right--;}//左边找比keyi大的while (left < right && arr[left] <= arr[keyi]){left++;}if (left < right){std::swap(arr[left], arr[right]);}}int meeti = left;//此时相遇了std::swap(arr[keyi], arr[meeti]);return meeti;
}//快速排序
void QuickSort(int arr[], int begin, int end)
{if (begin >= end){return;}int keyi = SingSort(arr, begin, end);//[begin,keyi-1] keyi [keyi+1,end]QuickSort(arr, begin, keyi - 1);QuickSort(arr, keyi + 1, end);
}

---

快速排序优化

三数取中

         快速排序的时间复杂度为O（N * log N），是在理想的情况下计算的结果，每次进行完单趟排序之后，key的左序列与右序列的长度相同，并且所选key正好都是该序列中的 left 下标的值与 right 下标的值的中间值，每趟排序结束后key都位于序列的中间：

如果待排序的序列是一个有序序列，选key时依旧选最左边或者最右边，那么此时时间复杂度就会退化：

快速排序效率的影响最大的就是选key，key越接近中间位置，效率就越高。

三数取中逻辑：最左下标的值，最右下标的值，以及中间位置的值，进行大小比较，然后选大小居中位置的值作为key，当大小居中的位置的值不在最左端或者最右端时，就需要将key值与最左端的值进行交换即可。

//三数取中逻辑
int GetMidWay(int arr[], int left, int right)
{int mid = (right + left) / 2;if (arr[right] > arr[mid]){if (arr[left] > arr[right]){return right;}else if (arr[mid] > arr[left]){return mid;}else{return right;}}else // arr[right] <= arr[mid]{if (arr[left] > arr[mid]){return mid;}else if (arr[right] > arr[left]){return right;}else{return left;}}
}//快排的单趟排序  [] 左闭右闭
int SingSort(int arr[], int left, int right)
{int mid = GetMidWay(arr, left, right);std::swap(arr[left], arr[mid]);//选取一个key值 左边int keyi = left;while (left < right){//右边先走，右边找比keyi小的 相等也跳过，否则可能会死循环while (left < right && arr[right] >= arr[keyi]){right--;}//左边找比keyi大的while (left < right && arr[left] <= arr[keyi]){left++;}if (left < right){std::swap(arr[left], arr[right]);}}int meeti = left;//此时相遇了std::swap(arr[keyi], arr[meeti]);return meeti;
}

 小区间优化

随着递归的深入，每一层的递归次数会以2倍的形式快速增长，如果递归的森度过大，可能会导致栈溢出的情况，为了减少递归树的最后几层递归，可以设置一个判断语句，当递归序列的长度小于某个值时，就不再进行递归转向使用其他排序方法：

//快速排序
void QuickSort(int arr[], int begin, int end)
{if (begin >= end){return;}//小区间优化if (end - begin <= 13){//进行希尔排序InsertSort(arr + begin, end - begin + 1);//个数+1}else{int keyi = SingSort(arr, begin, end);//[begin,keyi-1] keyi [keyi+1,end]QuickSort(arr, begin, keyi - 1);QuickSort(arr, keyi + 1, end);}
}

---

挖坑法（单趟）

单趟动图演示：

 基本思想步骤：

（1）、选出一个数值（一般是最左边或者最右边的值）存储在key变量中，在该数据位置形成了一个坑。

（2）、定义两个像指针一样的下表（L与R），L从左往右走，R从右往左走。（若在坑位在最左边，需要R先走，若坑位在右边，需要L先走）。

（3）、若R遇到小于key值的数，就将该数填入到左边的坑位，再将这个数的位置设置为新的坑位，此时L再走，若遇到大于key值的数，就将该数填入的右边的坑位，这个数的位置形成新的坑位，循环往下走，直到L和R的位置相遇，再将key值填入遇到位置的坑位。（最左边的值为key）

// 挖坑法
int PartSort(int arr[], int left, int right)
{//三数取中int mid = GetMidWay(arr, left, right);std::swap(arr[left], arr[mid]);int key = arr[left];int hole = left;while (left < right){//右边找比key小的坑，填到左边while (left < right && arr[right] >= key){right --;}arr[hole] = arr[right];hole = right;//左边找比key大的坑，填到右边while (left < right && arr[left] <= key){left++;}arr[hole] = arr[left];hole = left;}arr[hole] = key;return hole;
}

---

前后指针法（单趟）

单趟动图演示：

 前后指针法的思想：

• cur 遇到比key小的值就停下来，是否一直++；

• prev++，交换 cur 与 prev 位置的值（也可以进行判断 prev ++ 之后与 cur 位置是否相等，相等就不交换）

基本步骤：

（1）、选 keyi 位置的值作为基准值，一般是最左边或者最右边。

（2）、定义两个指针变量，开始 prev 指向序列开头的位置，cur 指向 prev + 1 的位置。

（3）、若 cur 位置的值小于key，则 prev 位置进行 ++ ，交换 prev 位置与 cur 位置的值；

如果 cur 位置的值大于key，cur 位置一直 ++，直到 cur 指针越界，此时将 keyi 位置的值与 prev 位置的值进行交换即可。

// 前后指针法
int PartSort2(int arr[], int left, int right)
{int mid = GetMidWay(arr, left, right);std::swap(arr[mid], arr[left]);int keyi = left;int prev = left;int cur = prev + 1;while (cur <= right){//cur位置向前找小的while (arr[cur] >= arr[keyi]){cur++;}swap(arr[cur], arr[prev + 1]);}swap(arr[prev], arr[keyi]);return prev;
}

---

非递归实现（快排）

需要借助一个数据结构（栈）来实现，直接用STL中的容器（stack）即可，其中栈中存储的是区间位置，也就是下标。

基本思想步骤：

（1）、先将待排序序列的第一个元素的下标与最后一个元素的下标进行入栈。

（2）、当栈不为空时，先读取栈顶元素作为子区间的 right，出栈后再读取栈顶的元素作为子区间的 left，将这个子区间进行单趟排序，随后将被分割的新的子区间，再进行入栈处理，直到序列中只有一个元素或者不存在即可。

//快速排序 - 非递归
void QuickSortNonR(int arr[], int begin, int end)
{stack<int> st;//存储的是区间st.push(begin);st.push(end);while (!st.empty()){int right = st.top();st.pop();int left = st.top();st.pop();//区间不存在 结束/*if (left >= right){continue;}*///对区间进行单趟排序int key = PartSort(arr, left, right);// [left key-1] key [key+1 right]//对子区间进行入栈if (key + 1 < right){st.push(key + 1);st.push(right);}if (left < key - 1){st.push(left);st.push(key - 1);}}
}

---

归并排序

动图演示：

 归并排序基本思想：采用分治的方法，将已经有序的子序列合并，从而得到一组完全有序的序列，即先使每个子序列先有序，再使子序列段间有序。

如何将两个有序序列合并成一个有序序列？（只需要取小的尾插到新数组即可）

 如何得到有序的子序列呢？（当序列分解到只有一个元素或者没有元素时，就可以认为是有序的了）

归并排序（递归）实现步骤：

（1）、需要申请一块用于与待排序数组大小相同的用于合并两个 子序列的临时数组。

（2）、进行递归分治，直到只有一个元素或者不存在。

（3）、得到的两个子序列，取小的尾插的临时数组中，直到两个子序列都尾插完全，再拷贝回原数组的相对应位置。

代码：

void _MergeSort(int arr[], int begin, int end, int* tmp)
{//分if (begin >= end){return;}int mid = (end + begin) / 2;//[begin mid] [mid+1 end]//递归划分子区间_MergeSort(arr, begin, mid, tmp);_MergeSort(arr, mid + 1, end, tmp);//归并int i = begin; //区间的开始int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;while (begin1 <= end1 && begin2 <= end2){//取小的尾插到临时数组中if (arr[begin1] <= arr[begin2]){tmp[i++] = arr[begin1++];}else{tmp[i++] = arr[begin2++];}}//此时有的区间还没有结束while (begin1 <= end1){tmp[i++] = arr[begin1++];}while (begin2 <= end2){tmp[i++] = arr[begin2++];}//拷贝子区间数组到原数组当中memcpy(arr + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}//归并排序 - 递归
void MergeSort(int arr[], int n)
{int* tmp = new int(n);//分为子函数进行 闭区间_MergeSort(arr, 0, n - 1, tmp);
}

时间复杂度（ O(N * log N) ）   空间复杂度（ O(N) ） 

---

非递归实现（归并）

归并排序的非递归实现，不需要借助栈等数据结构来实现，只需要控制好，每次参加合并的元素个数即可，最终便能使序列变成有序：

 上面只是一个广泛适用的样例，其中还有很多极端场景：

场景一：

当最后一个小组进行合并时，第二个小区间存在，但是该区间元素个数不足gap个，需要在合并序列时，对第二个小区间的边界进行控制：

 场景二：

当最后一个小组进行合并时，第二个小区间不存在，此时不需要对该小组进行合并：

 场景三：

当最后一个小组进行合并时，第二个小区间不存在，并且第一个小区间元素不够gap个时，此时也不需要对该小组进行合并：

//归并排序 - 非递归
void MergeSortNonR(int arr[], int n)
{int* v = new int(n);int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap){int j = i;int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;//场景一：第二组部分越界  直接修正边界if (end2 >= n){end2 = n - 1;}//场景二：第二组全部越界  if (begin2>= n){break;}//场景三：第一组越界if (end1 >= n){break;}//将数组归并while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] <= arr[begin2]){v[j++] = arr[begin1++];}else{v[j++] = arr[begin2++];}}//把剩下的数进行归并while (begin1 <= end1){v[j++] = arr[begin1++];}while (begin2 <= end2){v[j++] = arr[begin2++];}memcpy(arr + i, v + i, sizeof(int)*(end2 - i + 1));}gap *= 2;}
}

---

计数排序

        计数排序，又叫非比较排序，通过统计数组中相同元素出现的次数，然后通过统计的结果将序列回收到原来的序列。

如例：

绝对映射：统计数组中的下标 i 的位置记录的是arr数组中数字i出现的次数。

相对映射：统计中下标为i的位置记录的是arr数组中数字 i + min 出现的次数。

注意：

        计数排序只适用于数据范围较集中的序列的排序，若待排序列的数据较分散，会造成空间浪费，计数排序只适用于整型数据的排序，不适用于字符串以及浮点型数据。

代码：

//计数排序
void CountSort(int arr[], int n)
{int a_max = arr[0], a_min = arr[0];for (int i = 1; i < n; i++){if (arr[i] > a_max){a_max = arr[i];}if (arr[i] < a_min){a_min = arr[i];}}int num = a_max - a_min + 1;//开这么大的数组vector<int> v(num);for (int i = 0; i < n; i++){v[arr[i] - a_min]++;//统计次数}int j = 0;for (int i = 0; i < num; i++){while (v[i]--)//次数{arr[j++] = i + a_min;}}
}

时间复杂度（O(N + NUM)），空间复杂度（O(NUM)）

---

冒泡排序

动态演示：

 冒泡排序思想：

最外层循环控制的是循环的次数，内层循环控制的是数组中哪些元素进行交换。

代码：

//冒泡排序
void BubbleSort(int arr[], int n)
{int flag = 0;for (int i = 0; i < n; i++){for (int j = 0; j < n - 1 - i; j++){if (arr[j] > arr[j + 1]){swap(arr[j], arr[j + 1]);//把大的换到最后面的位置flag = 1;}}if (flag == 0){break;//此时是有序的数组}}
}

时间复杂度（O(N^2)）空间复杂度（O(1)） 

---

插入排序

动图演示：

         插入排序，又名直接插入排序。在待排序的元素中，假设前 n-1 个元素已经是有序的，现将第n个数插入到前面已经排好序的序列中，使得前n个元素有序。依次对所有插入要的元素，直到整个序列有序为止。

实现步骤：

（1）、保存要插入的第 n 个数（要将前面的数据移动到后面所以要临时保存）。

（2）、依次在 end >= 0的情况下，与前面的数进行对比，如果要插入的数据小于前面的数，则向 end + 1 位置进行覆盖，大于则 break。

（3）、插入的位置有两种情况，只需要向 end + 1位置填入即可。

 代码：

//插入排序
void InsertSort(int arr[], int n)
{//假设[0,end]有序for (int i = 0; i < n - 1; i++){int end = i;//不能使用iint tmp = arr[end + 1];while (end >= 0){if (tmp < arr[end]){arr[end + 1] = arr[end];//继续往前比较end--;}else{//此时 2 4 这种情况break;}}arr[end + 1] = tmp;}
}

时间复杂度（O(N^2)）

---

希尔排序（缩小增量排序）

希尔排序对普通插入排序的时间复杂度进行分析，得出以下结论：

1、普通插入排序的时间复杂度最坏情况下为O(N^2)，此时待排序序列为逆序情况下，或者说接近逆序。

2、普通插入排序的时间复杂度最好情况下为O(N)，此时待排序序列为有序情况下，或者说接近有序。

希尔排序的思想：先将待排序序列进行一次与排序，使得待排序序列接近有序，然后再对该序列进行一次直接插入排序。

希尔排序基本步骤：

1、先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在统一组，并对每一组的元素进行直接插入排序，然后再取一个币第一增量小的整数作为第二增量，重复上述步骤，直到增量为1为止。

2、当增量大小为1时，就相当于整个序列被分到一组，直接进行插入排序即可将排序序列成为有序序列。

问题：gap如何选择？

gap越大，数据挪动得越快，gap越小，数据挪动得越慢，前期让gap较大，可以让数据更快得移动到自己对应的位置附近（比如：大的数据到后面，小的数据到前面，对升序而言）。一般情况下，取序列的一半作为增量，也可以取 / 3 + 1，直接增量为1。

举例说明分析：

前面两趟都是预排序，最后一趟为直接插入排序。

//希尔排序
void ShellSort(int arr[], int n)
{控制gap的值//int gap = n;//while (gap > 1)//{//	gap = gap / 3 + 1;//	//按组进行//	for (int j = 0; j < gap; j++)//	{//		for (int i = j; i < n - gap; i += gap)//		{//			int end = i;//			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的值int gap = n;while (gap > 1){gap = gap / 3 + 1;//齐头并进for (int i = 0; i < n - gap; i++){int end = i;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;}}
}

 时间复杂度（O(N * Log N)） 平均时间复杂度（O(N^1.3)）

---

选择排序（优化版本）

动图演示（未优化，选择一个数的）：

 未优化选择排序思想：每次从待排序中选出一个最小值，然后放在序列的起始位置，直到全部待排序序列排完即可。

void SelectSort(int arr[], int n)
{for (int i = 0; i < n; i++){int begin = i;int mini = begin;while (begin < n){if (arr[begin] < arr[mini]){mini = begin;}begin++;}swap(arr[mini], arr[i]);}
}

优化选择排序：可以一趟选出两个数值，一个最大值，和一个最小值，然后将它们分别放在序列的末端以及开头，直到遍历完整个序列。

特殊情况：

//选择排序
void SelectSort(int arr[], int n)
{int begin = 0;int end = n - 1;while (begin < end){int mini = begin;int maxi = begin;for (int i = begin + 1; i <= end; i++){if (arr[i] > arr[maxi]){maxi = i;}if (arr[i] < arr[mini]){mini = i;}}//进行交换swap(arr[begin], arr[mini]);//如果最大的数在begin位置，被换到mini位置了if (maxi == begin){maxi = mini;}swap(arr[end], arr[maxi]);begin++;end--;}
}

时间复杂度最好与最坏（O(N^2)） 

---

堆排序

首先要建堆，而建堆需要执行多次堆的向下调整算法。

堆的向下调整算法：

        新插入节点，要调整为小堆，那么根节点的左右子树必须都为小堆；调整为大堆，那么根节点的左右子树必须都是大堆。

 向下调整算法步骤（建大堆）：

1、从根节点开始，选出左右孩子中值较大的孩子。

2、让大的孩子与父亲位置的值进行比较，若大于父亲位置的值，则该孩子与父亲位置进行交换，并将原来大的孩子的位置当成父亲继续向下进行调整，直到调整到叶子节点位置；若小于父亲位置的值，就不需要处理了，此时整棵数就是大堆了。

示例演示：

//堆的向下调整算法
void AdjustDown(int arr[], int n, int root)
{int parent = root;int child = parent * 2 + 1;//假设左边孩子的值大while (child < n){if (child + 1 < n && arr[child + 1] > arr[child]) //child位置存在的情况下{child++;}if (arr[child] > arr[parent]){swap(arr[child], arr[parent]);parent = child;child = parent * 2 + 1;}else{break;//此时已经是大堆了}}
}

 堆的向下调整算法，最快情况下，一直要向下调整节点，次数为 h - 1 次（h为数的高度），而 

h = log 2 (N+1) N为结点总数，所以堆的向下调整算法的时间复杂度为 O(log N)

        使用堆的向下调整算法需要满足其根节点的左右子树是大堆或者小堆才行，方法如下：

只需要从倒数第一个非叶子结点来说，从后往前，按下标，依次作为根取向下调整即可。

建堆代码：

//最后一个位置的下班是n-1,父亲位置是 (n - 1 -1)/2
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{AdjustDown(arr, n, i);
}

 建堆的时间复杂度大概是 O(N)。

如何进行堆排序？

1、将堆顶数据与堆的最后一个数据交换，然后对根位置进行一次向下调整算法，但是被交换到最后的那个最大的数不参与向下调整。

2、此时除了最后一个数之外，其余的数又成了一个大堆，然后又将堆顶数据与堆的最后一个数据进行交换，第二大的数就被放到了倒数第二位置上，反复进行运算，直到堆中只有一个数据即可。

void HeapSort(int arr[], int n)
{//最后一个位置的下班是n-1,父亲位置是 (n - 1 -1)/2for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, n, i);}//此时是一个大堆，进行把大的数，放到最后即可int end = n - 1;while (end){swap(arr[0], arr[end]);//继续向下调整，成为大堆AdjustDown(arr, end, 0);end--;}
}

时间复杂度（O(N^2)）

---