【数据结构与算法】常见排序算法详解（C++实现）

目录

一、排序的基本概念

二、插入排序

2.1 直接插入排序

2.2 折半插入排序

2.3 希尔排序

三、交换排序

3.1 冒泡排序

3.2 快速排序

四、选择排序

4.1 简单选择排序

4.2 堆排序

五、归并排序

六、基数排序

七、计数排序

结语

---

一、排序的基本概念

排序

就是重新排列一串记录中的元素，使元素按照其中的某个或某些关键字的大小，递增或递减的排列起来的过程。

排序前：n个记录R1,R2......Rn，对应的关键字为K1,K2......Kn。

排序后：R1',R2'......Rn'，对应的关键字顺序K1'<=K2'<=......<=Kn'，其中<=可以换成其它比较大小的符号。

稳定性

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

内部排序

排序期间数据元素全部放在内存中的排序。

外部排序

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

二、插入排序

插入排序的基本思想是每次将一个待排序的记录元素按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成。

2.1 直接插入排序

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。

void insertSort(vector<int>& arr)
{int n = arr.size();if(n < 2)return;for(int i = 1; i < n; ++i) // 第一个元素作为基准元素，从第二个元素开始把其插到正确的位置{int end = i - 1;     // 需要判断第i个元素与前面的多个元素的大小int tmp = arr[i];    // 将第i个元素复制为哨兵while(end >= 0 && arr[end] > tmp) // 找哨兵的正确位置，比哨兵大的元素依次后移{arr[end + 1] = arr[end]; end--;}arr[end + 1] = tmp;  //把哨兵插入到正确的位置}   
}

空间复杂度：O(1)，仅使用常数个辅助单元。

时间复杂度：

对于N个元素，将第一个元素看作有序后，需要操作剩下的N-1个元素，也就是需要比较N-1趟，每趟操作都分为比较关键字和移动元素，比较次数与移动元素的次数取决于待排序表的初始状态。

在最好的情况下，表中元素已经有序，N-1个元素只需要插入到已排好序的后面，因此时间复杂度为O(N)。

在最坏的情况下，表中元素为排序结果的逆序，N-1个元素每个比较后都要移动到排好序的最前面，因此时间复杂度为O(N²)。

稳定性：稳定。每次插入元素都是从后往前先比较再移动，所以不会出现相同元素相对位置发生变化的情况。

适用性：适用于顺序存储和链式存储的线性表，采用链式存储时不需要移动元素。

2.2 折半插入排序

插入排序步骤分为比较元素和移动元素，其中对于比较元素这一步骤，由于前面的元素已经排好序，可以使用二分查找提高查找效率。

void insertSort(vector<int>& arr)
{int n = arr.size();if(n < 2)return;for(int i = 1; i < n; ++i) // 第一个元素作为基准元素，从第二个元素开始把其插到正确的位置{int tmp = arr[i];    // 将第i个元素复制为哨兵int left = 0;int right = i - 1; // 二分查找while(left <= right){int mid = left + (right - left) / 2;if(arr[mid] > tmp)right = mid - 1;elseleft = mid + 1;}    // 此时 left > right， left 为插入的位置for(int j = i; j > left; j--) // 比哨兵大的元素依次后移{arr[j] = arr[j-1];}arr[left] = tmp;  //把哨兵插入到正确的位置}   
}

空间复杂度：O(1)，仅使用常数个辅助单元。

时间复杂度：

虽说改进了查找方法，减少了比较的次数，但元素的移动次数并未改变，因此时间复杂度同直接插入排序一致，最好为O(N)，最坏为O(N²)。

稳定性：稳定。和直接插入排序一致。

适用性：采用了随机存取的特点，只适用于顺序存储的线性表。

2.3 希尔排序

直接插入排序在元素接近有序的时候，时间效率较高，一般更适用于基本有序的排序表和数据量不大的排序表。基于这两点，在插入排序的基础上进行改进，得到了希尔排序。 

希尔排序又称缩小增量排序。希尔排序法的基本思想是：先选定一个整数，将待排序表分割成若干子表，对各个子表分别进行直接插入排序。重复上述分组和排序的工作。当整数到达1时，所有记录在统一组内排好序。

void ShellSort(vector<int>& arr)
{int n = arr.size();if(n < 2) return;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 && tmp < a[end]){arr[end + gap] = arr[end];end -= gap;}arr[end + gap] = tmp;}}
}

空间复杂度：O(1)，仅使用常数个辅助单元。

时间复杂度：最坏情况下为O(N²)，N在某个特定范围时，时间复杂度约为。

稳定性：不稳定。当相同关键字的记录元素被划分到不同的子表时，可能会改变它们之间的相对次序。

适用性：仅适用于顺序存储的线性表。

三、交换排序

交换排序的思想：根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。

3.1 冒泡排序

从前往后（从后往前）两两比较相邻元素的值，若为逆序（A[i-1] > A[i]），则交换它们，直到序列比完。这是一趟冒泡，最后会将最大的元素交换到最后一个位置，这个过程中，关键字最大的元素慢慢的移动到后面，就像冒泡一样。最多n-1趟冒泡就能把所有元素排好序。

void BubbleSort(vector<int>& arr)
{int n = arr.size(); for (int i = 0; i < n - 1; i++){// 标记位，当这一趟冒泡没有交换元素则说明已经有序，可以停止int exchange = 0;for (int j = 0; j < n - 1 - i; j++){if (arr[j] > arr[j + 1]){std::swap(a[j], a[j + 1]);exchange = 1;}}if (exchange == 0)break;}
}

空间复杂度： O(1)，仅使用常数个辅助单元。

时间复杂度：

当初始序列有序时，只需要第一趟冒泡，比较次数为N-1，移动次数为0，因此最好情况下时间复杂度为O(N)。

当初始序列为逆序时，需要N-1趟冒泡，第i趟排序要进行N-i次关键字的比较，并且要进行N-1次的移动，因此最坏情况下时间复杂度为O(N²)。

稳定性：稳定。当A[i] = A[j] 时，不会发生交换。

适用性：适用于顺序存储和链式存储的线性表。

3.2 快速排序

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

void QuickSort(vector<int>& arr, int left, int right)
{if (left >= right)return;//很大的时候用快速排序if ((right - left + 1) > 10){//int div = PartSort1(arr, left, right);int div = PartSort2(arr, left, right);//int div = PartSort3(arr, left, right);QuickSort(arr, left, div - 1);QuickSort(arr, div + 1, right);}//小了的时候用插入排序else{InsertSort(arr + left, right - left + 1);}
}// 头 中间 尾 三数取中
int GetMidIndex(vector<int>& arr, int begin, int end)
{int mid = (begin + end) / 2;if (arr[begin] < arr[mid]){if (a[mid] < a[end]){return mid;}else if (arr[begin] > arr[end]){return begin;}else{return end;}}else{if (arr[end] > arr[begin]){return begin;}else if (arr[end] < arr[mid]){return mid;}else{return end;}}
}// 左右指针法  
int PartSort1(vector<int>& arr, int begin, int end)
{if (begin >= end) return begin;// 三数取中选择基准值索引int midindex = GetMidIndex(arr, begin, end);std::swap(arr[midindex], arr[end]);int keyindex = end;while (begin < end){while (begin < end && arr[begin] <= arr[keyindex])begin++;while (begin < end && arr[end] >= arr[keyindex])end--;std::swap(arr[begin], arr[end]);}// 将基准值放到正确位置std::swap(arr[begin], arr[keyindex]);return begin;  // 返回基准值的最终位置
}// 挖坑法：挪动基准值
int PartSort2(vector<int>& arr, int begin, int end)
{int midindex = GetMidIndex(arr, begin, end);std::swap(arr[midindex], arr[end]);int key = arr[end];while (begin < end){while (begin < end && arr[begin] <= key)begin++;arr[end] = arr[begin];while (begin < end && arr[end] >= key)end--;arr[begin] = arr[end];}arr[begin] = key;return begin;
}// 前后指针法
int PartSort3(vector<int>& arr, int begin, int end)
{int midindex = GetMidIndex(arr, begin, end);std::swap(arr[midindex], arr[end]);int key = arr[end];int cur = begin;int prev = cur - 1;while (cur < end){if (arr[cur] < key && ++prev != cur){std::swap(arr[cur], arr[prev]);}cur++;}prev++;std::swap(arr[prev], arr[end]);return prev;
}

空间复杂度：快速排序使用了递归，因此空间与递归调用的最大层数一致。最好情况下为O(logN) ，最坏情况下进行N-1次递归调用，空间复杂度为O(N)。

时间复杂度：

最坏情况下每次基准值选的都是最大或者最小的，相当于每次递归的时候一个数组范围为N-1，另一个为0，变成了单个数组排序，时间复杂度为O(N²)。

最好情况下每次基准值都选到了中间的值，那么在递归的时候，每个数组都是N/2的长度，最后的时间复杂度为O(NlogN)。

在这里我们利用了三数取中来避免最坏情况的发生，因此可以将快速排序的时间复杂度看作O(NlogN)。

稳定性：不稳定。划分区间的时候会将两个相同关键字的交换后位置发生变化。

适用性：仅适用于顺序存储的线性表。

四、选择排序

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

4.1 简单选择排序

void SelectSort(vector<int>& arr)
{int n = arr.size();if(n < 2) return;int begin = 0, end = n - 1;while (begin < end){int mini, maxi;mini = maxi = begin;for (int i = begin + 1; i <= end; i++){if (arr[i] > arr[maxi]){maxi = i;}if (arr[i] < arr[mini]){mini = i;}}std::swap(arr[begin], arr[mini]);if (begin == maxi){maxi = mini;}std::swap(arr[end], arr[maxi]);begin++;end--;}
}

空间复杂度： O(1)，仅使用常数个辅助单元。

时间复杂度：

一趟选择排序中分为比较和交换两个部分，元素之间比较次数与表的初始状态无关，始终是N(N-1)/2次，而交换与表的初始状态有关，有序或者接近有序则交换的次数少，但是时间复杂度最终都是O(N²)。

稳定性：不稳定。交换的时候会将相同的值的前一个元素交换到后面。

适用性：适用于顺序存储和链式存储的线性表，以及关键字较少的情况。

4.2 堆排序

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

这里有需要的可以去我的另一篇文章查看更具体的堆的操作：【重走C++学习之路】11、STL-stack和queue在这篇文章的优先队列讲解中。

void HeapSort(vector<int>& arr)
{int n = arr.size();if(n < 2) return;// 从叶子节点的父节点开始调整for (int i = (n - 1 - 1) / 2; i >= 0;i--){AdjustDown(arr, n, i);}int end = n - 1;while (end > 0){std::swap(arr[0], arr[end]);AdjustDown(arr, end, 0);end--;}
}//大堆向下调整
void AdjustDown(vector<int>& arr, int n, int root)
{int parent = root;int child = parent * 2 + 1;while (child < n){if (child + 1 < n && arr[child] < arr[child + 1]){child++;}if (arr[child] > arr[parent]){std::swap(arr[child], arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

空间复杂度： O(1)，仅使用常数个辅助单元。

时间复杂度：

建堆的时间复杂度为O(N)，建堆完后需要将最顶上的值挪动到最后来，又需要进行调整，这里的时间复杂度为O(H)，最后总的时间复杂度为O(NlogN)。

稳定性：不稳定。建堆的时候有可能把后面相同关键字的元素调整到前面，

适用性：仅适用于顺序存储的线性表。

五、归并排序

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列：即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

void MergeSort(vector<int>& arr)
{int n = arr.size();if(n < 2) return;_MergeSort(arr, 0, n-1);
}void _MergeSort(vector<int>& arr, int left, int right)
{if (left >= right)return;int mid = (left + right) / 2;_MergeSort(arr, left, mid);_MergeSort(arr, mid + 1, right);int n1 = mid - left + 1;int n2 = right - mid;vector<int> L(n1), R(n2);// 拷贝数据到临时数组for (int i = 0; i < n1; i++) L[i] = arr[left + i];for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];// 合并临时数组到原数组int i = 0, j = 0, k = left;while (i < n1 && j < n2) {if (L[i] <= R[j]) arr[k++] = L[i++];else arr[k++] = R[j++];}// 剩余没拷贝完的while (i < n1) arr[k++] = L[i++];while (j < n2) arr[k++] = R[j++];
}

空间复杂度： O(N)，在合并数组的时候借助了辅助空间，开辟了大小为N的数组。

时间复杂度：

每趟归并的时间复杂度为O(N)，共需要进行[logN]趟归并，因此算法的时间复杂度为O(NlogN)。

稳定性：稳定。合并的时候不会改变相同关键字记录的相对顺序。

适用性：适用于顺序存储和链式存储的线性表。

六、基数排序

基数排序不基于比较和移动进行排序，而基于关键字各位的大小进行排序。基数排序的思想：不管多大多小的数，都是由0~9这十个基本数字组成的，不同的数只是位数不同或同一位（权值）上的基数不同。借此，我们先从每个数的最低位（如个位）开始比较，将它们分类（借助队列），然后依次取出再比较上一位（如十位），还是同样的方法，直到最后所有数最高位均为0时排序结束。

// 获取最大位数
int getMaxDigits(const vector<int>& arr) 
{if (arr.empty()) return 0;int maxVal = *max_element(arr.begin(), arr.end());int digits = 0;while (maxVal > 0) {digits++;maxVal /= 10;}return digits;
}// LSD(低位优先)基数排序
void radixSortLSD(vector<int>& arr) 
{if (arr.size() < 2) return;int maxDigits = getMaxDigits(arr);vector<int> temp(arr.size());vector<int> count(10, 0);  // 十进制每一位的计数器for (int exp = 1; exp <= maxDigits; exp++) {int power = 1;for (int i = 1; i < exp; i++) power *= 10;// 重置计数器fill(count.begin(), count.end(), 0);// 统计每个位的出现次数for (int num : arr) {int digit = (num / power) % 10;count[digit]++;}// 转换为前缀和数组，确定元素在temp中的位置for (int i = 1; i < 10; i++) {count[i] += count[i - 1];}// 从后向前填充temp数组，保证稳定性for (int i = arr.size() - 1; i >= 0; i--) {int digit = (arr[i] / power) % 10;temp[--count[digit]] = arr[i];}// 复制回原数组arr = temp;}
}

空间复杂度： O(N)，借助了一个N个元素大小的数组存放临时结果。

时间复杂度：

每趟需要进行分配和收集操作，分配需要遍历所有关键字，时间复杂度为O(N)，收集需要合并r个队列，时间复杂度为O(r)，总共需要d趟，其中d为最大的位数，因此基数排序的时间复杂度为O(d(N+r))。

稳定性：稳定。每一趟分配和收集都是从后往前进行的，不会交换相同关键字的相对位置。

适用性：适用于顺序存储和链式存储的线性表。

七、计数排序

计数排序不基于比较，主要思想是：对于每个待排序元素x，统计小于x的元素个数，利用该信息就可以确定x的最终位置。

void stableCountingSort(vector<int>& arr) 
{if (arr.empty()) return;// 计算最小值和最大值，确定计数数组的大小int minVal = *min_element(arr.begin(), arr.end());int maxVal = *max_element(arr.begin(), arr.end());int range = maxVal - minVal + 1;// 创建计数数组并统计每个元素的出现次数vector<int> count(range, 0);for (int num : arr) {count[num - minVal]++;}// 将计数数组转换为前缀和数组，记录每个元素的最终位置for (int i = 1; i < range; i++) {count[i] += count[i - 1];}// 创建临时数组，从后向前填充元素以保证稳定性vector<int> temp(arr.size());for (int i = arr.size() - 1; i >= 0; i--) {int value = arr[i];int index = count[value - minVal] - 1;temp[index] = value;count[value - minVal]--; // 更新位置指针}// 将临时数组复制回原数组arr = temp;
}

空间复杂度： O(范围)，其中范围为排序中最大的元素到0之间的个数。

时间复杂度：

O(MAX(N,范围))，这里有三个for循环，两个个是排序数组的N次，另一个是数中范围的次数，看这两个谁更大。

稳定性：稳定。最后参考排序表中元素的位置，从后往前遍历数组，相同元素在输出数组中的相对位置不会改变。

适用性：适用于顺序存储的线性表，并且序列中元素是整数且元素的范围不大。

结语

到这里基本上就解释完了常见的排序算法，排序在面试中非常常见，在学习的时候需要了解各个排序的思想，思想掌握了再写出来就不麻烦了。