【算法】经典排序算法介绍+代码示例
排序算法介绍
- 1）冒泡排序 (Bubble Sort)
- 2）选择排序（Selection Sort）
- 3）插入排序（Insertion Sort）
- 4）希尔排序（Shell Sort）
- 5）归并排序（Merge Sort）
- 6）快速排序（Quick Sort）
- 7）堆排序（Heap Sort）
- 8）计数排序（Counting Sort）
- 9）桶排序（Bucket Sort）
排序算法的目的是将一组数据按照某种顺序（通常是升序或降序）排列。以下内容主要参考：十大经典排序算法（动图演示） ，下面先解释一下相关概念，然后介绍常见的排序算法：
稳定性解释：
- 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
- 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
1）冒泡排序 (Bubble Sort)
思想： 通过重复遍历待排序序列，比较相邻元素并根据他们的小大交换他们，小的在前大的最后，最后使较大的元素逐渐“冒泡”到序列的末尾
算法描述：
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个的位置
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数
- 此时后面的元素就是从小到大排好序的（有序序列），前的所有元素（无序序列）需要重复以上操作，找到下一个最大的数，加入有序序列的最前面，有序序列元素逐渐增加，无序序列元素逐渐减少
- 针对无序序列重复以上的步骤，直到无序序列没有元素，排序完成
代码：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void BubbleSort(vector<int> nums) {
int n=nums.size();
cout<<"Original Nums: ";
for (int i = 0; i < n; i++)
cout << nums[i] << ' ';
cout << endl;
cout<<"Nums Length: "<<n<<endl;
cout<<"BubbleSort: "<<endl;
for(int len=0;len<n;len++){
int swaped=0;
for(int i=0;i<n;i++){
if(i+1<n-len && nums[i]>nums[i+1]){
int tmp=nums[i+1];
nums[i+1]=nums[i];
nums[i]=tmp;
swaped=1;
}
}
cout << "Iteration "<<len+1<<": ";
for (int i = 0; i < n; i++)
cout << nums[i] << ' ';
cout << endl;
if(!swaped){
cout<<"Already sorted,stop earlly!"<<endl;
break;
}
}
cout << "Sorted Nums: "<<" ";
for (int i = 0; i < n; i++)
cout << nums[i] << ' ';
cout << endl;
cout<<"-------------------------------------------------"<<endl;
}
int main() {
vector<int> nums = {61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62};
BubbleSort(nums);
return 0;
}
代码运行结果：
Original Nums: 61 17 29 22 34 60 72 21 50 1 62
Nums Length: 11
BubbleSort:
Iteration 1: 17 29 22 34 60 61 21 50 1 62 72
Iteration 2: 17 22 29 34 60 21 50 1 61 62 72
Iteration 3: 17 22 29 34 21 50 1 60 61 62 72
Iteration 4: 17 22 29 21 34 1 50 60 61 62 72
Iteration 5: 17 22 21 29 1 34 50 60 61 62 72
Iteration 6: 17 21 22 1 29 34 50 60 61 62 72
Iteration 7: 17 21 1 22 29 34 50 60 61 62 72
Iteration 8: 17 1 21 22 29 34 50 60 61 62 72
Iteration 9: 1 17 21 22 29 34 50 60 61 62 72
Iteration 10: 1 17 21 22 29 34 50 60 61 62 72
Already sorted,stop earlly!
Sorted Nums: 1 17 21 22 29 34 50 60 61 62 72
-------------------------------------------------
时间复杂度： O(n²)
空间复杂度： O(1)
稳定性： 稳定
2）选择排序（Selection Sort）
思想： 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
算法描述：
- 初始状态：无序区为R[1…n]，有序区为空
- 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1…i-1]和R(i…n）。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录交换，使R[1…i]和R[i+1…n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区
- n-1趟结束，数组有序化了
代码：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void SelectionSort(vector<int> nums) {
int n=nums.size();
cout<<"Original Nums: ";
for (int i = 0; i < n; i++)
cout << nums[i] << ' ';
cout << endl;
cout<<"Nums Length: "<<n<<endl;
cout<<"SelectionSort: "<<endl;
for(int len=0;len<n-1;len++){
int pos=len;
for(int i=len+1;i<n;i++){
if(nums[i]<nums[pos]) {
pos=i;
}
}
int tmp=nums[len];
nums[len]=nums[pos];
nums[pos]=tmp;
cout << "Iteration "<<len+1<<": ";
for (int i = 0; i < n; i++)
cout << nums[i] << ' ';
cout << endl;
}
cout << "Sorted Nums: "<<" ";
for (int i = 0; i < n; i++)
cout << nums[i] << ' ';
cout << endl;
cout<<"-------------------------------------------------"<<endl;
}
int main() {
vector<int> nums = {61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62};
SelectionSort(nums);
return 0;
}
代码运行结果：
Original Nums: 61 17 29 22 34 60 72 21 50 1 62
Nums Length: 11
SelectionSort:
Iteration 1: 1 17 29 22 34 60 72 21 50 61 62
Iteration 2: 1 17 29 22 34 60 72 21 50 61 62
Iteration 3: 1 17 21 22 34 60 72 29 50 61 62
Iteration 4: 1 17 21 22 34 60 72 29 50 61 62
Iteration 5: 1 17 21 22 29 60 72 34 50 61 62
Iteration 6: 1 17 21 22 29 34 72 60 50 61 62
Iteration 7: 1 17 21 22 29 34 50 60 72 61 62
Iteration 8: 1 17 21 22 29 34 50 60 72 61 62
Iteration 9: 1 17 21 22 29 34 50 60 61 72 62
Iteration 10: 1 17 21 22 29 34 50 60 61 62 72
Sorted Nums: 1 17 21 22 29 34 50 60 61 62 72
-------------------------------------------------
时间复杂度： O(n²)
空间复杂度： O(1)
稳定性： 不稳定，解释如下：
假设有一个数组 [a, b, 1]，其中 a 和 b 相等且大于1
第一轮选择最小元素 1，将其与第一个元素 a 交换，数组变为 [1, b, a]
此时，原本在后面的 b 在排序后跑到了a 的前面，破坏了相等元素的相对顺序
因此，选择排序是不稳定的排序算法
3）插入排序（Insertion Sort）
思想： 将待排序元素插入到已排序序列的适当位置，类似于扑克牌整理
算法描述：
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个待插入的元素，它与从后向前扫描已经排序的元素序列，与其中的元素比较，直到找到合适的位置（前面的元素小于等于待插入的元素，后面的元素大于待插入的元素）
- 重复以上步骤
代码：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void InsertionSort(vector<int> nums) {
int n=nums.size();
cout<<"Original Nums: ";
for (int i = 0; i < n; i++)
cout << nums[i] << ' ';
cout << endl;
cout<<"Nums Length: "<<n<<endl;
cout<<"InsertionSort: "<<endl;
for(int len=1;len<n;len++){
int now_num=nums[len];
int i=len;
while(i>0 && now_num<nums[i-1]){
nums[i]=nums[i-1];
i--;
}
nums[i]=now_num;
if(len<n){
cout << "Iteration "<<len+1<<": ";
}
for (int i = 0; i < n; i++)
cout << nums[i] << ' ';
cout << endl;
}
cout << "Sorted Nums: "<<" ";
for (int i = 0; i < n; i++)
cout << nums[i] << ' ';
cout << endl;
cout<<"-------------------------------------------------"<<endl;
}
int main() {
vector<int> nums = {61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62};
InsertionSort(nums);
return 0;
}
代码运行结果：
Original Nums: 61 17 29 22 34 60 72 21 50 1 62
Nums Length: 11
InsertionSort:
Iteration 2: 17 61 29 22 34 60 72 21 50 1 62
Iteration 3: 17 29 61 22 34 60 72 21 50 1 62
Iteration 4: 17 22 29 61 34 60 72 21 50 1 62
Iteration 5: 17 22 29 34 61 60 72 21 50 1 62
Iteration 6: 17 22 29 34 60 61 72 21 50 1 62
Iteration 7: 17 22 29 34 60 61 72 21 50 1 62
Iteration 8: 17 21 22 29 34 60 61 72 50 1 62
Iteration 9: 17 21 22 29 34 50 60 61 72 1 62
Iteration 10: 1 17 21 22 29 34 50 60 61 72 62
Iteration 11: 1 17 21 22 29 34 50 60 61 62 72
Sorted Nums: 1 17 21 22 29 34 50 60 61 62 72
-------------------------------------------------
时间复杂度： O(n²)
空间复杂度： O(1)
稳定性： 稳定
4）希尔排序（Shell Sort）
思想： 希尔排序(Shell Sort)是插入排序的一种，它是针对直接插入排序算法的改进，又称缩小增量法，是第一个突破O(n²)的排序算法，将整个待排序序列按一定间隔分组，分割成若干个子序列，对每个子序列进行插入排序，然后逐步缩小间隔直至1，直至整个序列有序。
为什么先分段再插入排序就可以提升原本的插入排序的效率？
- 插入排序在处理大规模数据时，如果数据分布不均匀，需要进行大量的元素交换和移动，效率较低。但是插入排序在数据已经部分有序时效率很高，时间复杂度可以接近O(n)
- 希尔排序通过引入增量序列（gap），将数组分成若干子序列，对每个子序列进行插入排序。这样，元素可以在较大的步长下快速移动到接近最终位置，减少后续插入排序中的移动次数，这可以使得整个数组逐步趋于“基本有序”，从而在最后一步（gap=1）进行插入排序时，能够以较高的效率完成排序
算法描述：
- 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1
- 按增量序列个数k，对序列进行k 趟排序
- 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序
- 仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度
代码：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void ShellSort(vector<int> nums) {
int n=nums.size();
cout<<"Original Nums: ";
for (int i = 0; i < n; i++)
cout << nums[i] << ' ';
cout << endl;
cout<<"Nums Length: "<<n<<endl;
cout<<"ShellSort: "<<endl;
for(int gap=n/2;gap>0;gap/=2){
cout << "Gap: "<<gap<<endl;
for(int i=gap;i<n;i++){
int j=i;
int now_num=nums[i];
while(j-gap>=0 && now_num<nums[j-gap]){
nums[j]=nums[j-gap];
j-=gap;
}
nums[j]=now_num;
for (int i = 0; i < n; i++)
cout << nums[i] << ' ';
cout << endl;
}
cout<<"----------------------------------"<<endl;
}
cout << "Sorted Nums: "<<" ";
for (int i = 0; i < n; i++)
cout << nums[i] << ' ';
cout << endl;
cout<<"-------------------------------------------------"<<endl;
}
int main() {
vector<int> nums = {61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62};
ShellSort(nums);
return 0;
}
代码运行结果：
Original Nums: 61 17 29 22 34 60 72 21 50 1 62
Nums Length: 11
ShellSort:
Gap: 5
60 17 29 22 34 61 72 21 50 1 62
60 17 29 22 34 61 72 21 50 1 62
60 17 21 22 34 61 72 29 50 1 62
60 17 21 22 34 61 72 29 50 1 62
60 17 21 22 1 61 72 29 50 34 62
60 17 21 22 1 61 72 29 50 34 62
----------------------------------
Gap: 2
21 17 60 22 1 61 72 29 50 34 62
21 17 60 22 1 61 72 29 50 34 62
1 17 21 22 60 61 72 29 50 34 62
1 17 21 22 60 61 72 29 50 34 62
1 17 21 22 60 61 72 29 50 34 62
1 17 21 22 60 29 72 61 50 34 62
1 17 21 22 50 29 60 61 72 34 62
1 17 21 22 50 29 60 34 72 61 62
1 17 21 22 50 29 60 34 62 61 72
----------------------------------
Gap: 1
1 17 21 22 50 29 60 34 62 61 72
1 17 21 22 50 29 60 34 62 61 72
1 17 21 22 50 29 60 34 62 61 72
1 17 21 22 50 29 60 34 62 61 72
1 17 21 22 29 50 60 34 62 61 72
1 17 21 22 29 50 60 34 62 61 72
1 17 21 22 29 34 50 60 62 61 72
1 17 21 22 29 34 50 60 62 61 72
1 17 21 22 29 34 50 60 61 62 72
1 17 21 22 29 34 50 60 61 62 72
----------------------------------
Sorted Nums: 1 17 21 22 29 34 50 60 61 62 72
-------------------------------------------------
时间复杂度：
希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难计算，一般来说，最坏时间复杂度： O ( n 2 ) O(n^2) O(n2)，最好的时间复杂度 O ( n ) O(n) O(n)，平均时间复杂度有 O ( n 1.3 ) O(n^{1.3}) O(n1.3)
空间复杂度： O(1)
稳定性： 不稳定（希尔排序不稳定的原因在于分组插入排序，具体来说，希尔排序通过将数组分成若干子序列（基于增量序列），对每个子序列进行插入排序。虽然单次插入排序是稳定的（不会改变相同元素的相对顺序），但在希尔排序中，相同元素可能被分到不同的子序列中，并在各自的插入排序过程中移动，从而导致它们的相对顺序被打乱）
5）归并排序（Merge Sort）
思想： 一种基于分治法的高效排序算法，它的核心思想是将待排序的数组不断二分，递归地对每个子数组进行排序，最后将两个已排序的子数组合并成一个有序的整体
算法描述：
- 分解：将数组从中间分成两个子数组，递归地对每个子数组进行排序
- 合并：将两个已排序的子数组合并成一个有序的数组。合并过程通过比较两个子数组的元素，依次将较小的元素放入新数组中，直到所有元素合并完成
代码：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> mergesort(vector<int>& nums) {
int n=nums.size();
if(n==1) return nums;
int mid=n/2;
vector<int> left(nums.begin(),nums.begin()+mid);
vector<int> left_sorted=mergesort(left);
vector<int> right(nums.begin()+mid,nums.end());
vector<int> right_sorted=mergesort(right);
vector<int> merged_nums;
int i=0;
int j=0;
while(i<left_sorted.size() && j<right_sorted.size()){
if(left_sorted[i]<=right_sorted[j]){
merged_nums.push_back(left_sorted[i]);
i++;
}
else{
merged_nums.push_back(right_sorted[j]);
j++;
}
}
while(i<left_sorted.size()){
merged_nums.push_back(left_sorted[i]);
i++;
}
while(j<right_sorted.size()){
merged_nums.push_back(right_sorted[j]);
j++;
}
return merged_nums;
}
void MergeSort(vector<int> nums) {
int n=nums.size();
cout<<"Original Nums: ";
for (int i = 0; i < n; i++)
cout << nums[i] << ' ';
cout << endl;
cout<<"Nums Length: "<<n<<endl;
cout<<"MergeSortSort: "<<endl;
vector<int> merged_nums=mergesort(nums);
cout << "Sorted Nums: "<<" ";
for (int i = 0; i < n; i++)
cout << merged_nums[i] << ' ';
cout << endl;
cout<<"-------------------------------------------------"<<endl;
}
int main() {
vector<int> nums = {61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62};
MergeSort(nums);
return 0;
}
代码运行结果：
Original Nums: 61 17 29 22 34 60 72 21 50 1 62
Nums Length: 11
MergeSortSort:
Sorted Nums: 1 17 21 22 29 34 50 60 61 62 72
-------------------------------------------------
时间复杂度： 稳定的O(n*longn)
- 分解阶段每次将数组分成两半，递归地对每个子数组进行排序，递归的深度为 logn
- 每次合并两个有序子数组的时间复杂度为 O(n)，因为需要遍历所有元素进行比较和移动
- 递归树的每一层都需要 O(n) 的时间进行合并，递归树共有 logn 层，因此总时间复杂度为 O(nlogn)
空间复杂度： O(n)
因为归并排序在合并过程中需要使用一个与原始数组大小相同的临时数组来存储合并后的结果 O(n)。此外，递归调用栈会占用额外的空间，其空间复杂度为 O(logn)。因此，归并排序的总空间复杂度为 O(n)+O(logn)=O(n)
稳定性： 稳定
6）快速排序（Quick Sort）
思想： 一种基于分治法的高效排序算法，它的核心思想是将待排序的数组不断分割成独立的两部分，其中一部分的元素均比另一部分的元素都要小，递归地对每个子部分进行排序，以达到整个序列有序
算法描述：
- 选择基准值（Pivot）：从数组中选择一个元素作为基准值（通常选择第一个、最后一个或中间元素）
- 分区（Partition）：将数组重新排列，使得所有小于基准值的元素位于基准值的左侧，所有大于基准值的元素位于基准值的右侧。基准值最终位于其正确的位置
- 递归排序：对基准值左侧和右侧的子数组递归地执行上述步骤，直到子数组长度为1或0，此时数组已完全有序
具体实现：
选择基准值：从数组中选择一个基准值。
分区操作：
1） 初始化两个指针，i从左向右扫描i，j从右向左扫描
2）从左向右找到第一个大于或等于基准值的元素，从右向左找到第一个小于或等于基准值的元素
3）交换这两个元素，直到指针相遇
4）将基准值放置到其正确的位置，使得基准左边的值全部小于他，右边的值全部大于它递归排序：对基准值左侧和右侧的子数组分别递归执行上述步骤
代码：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> quicksort1(vector<int>& nums) {
int n=nums.size();
if(n<=1) return nums;
int pivot_num=nums[0];
int i=0;
int j=n-1;
while(i<=j){
while(i<=j && nums[i]<=pivot_num) i++;
while(i<=j && nums[j]>pivot_num) j--;
if(i<=j){
int tmp=nums[j];
nums[j]=nums[i];
nums[i]=tmp;
i++;
j--;
}
}
int tmp=nums[j];
nums[j]=pivot_num;
nums[0]=tmp;
vector<int> left(nums.begin(),nums.begin()+j);
vector<int> right(nums.begin()+j+1,nums.end());
vector<int> left_sorted=quicksort1(left);
vector<int> right_sorted=quicksort1(right);
vector<int> merged_nums;
for(auto x:left_sorted) merged_nums.push_back(x);
merged_nums.push_back(pivot_num);
for(auto x:right_sorted) merged_nums.push_back(x);
return merged_nums;
}
void quicksort2(vector<int>& nums,int l,int r) {
int n=r-l+1;
if(n<=1) return ;
int pivot_num=nums[l];
int i=l+1;
int j=r;
while(i<=j){
while(i<=j && nums[i]<=pivot_num) i++;
while(i<=j && nums[j]>pivot_num) j--;
if(i<=j){
int tmp=nums[j];
nums[j]=nums[i];
nums[i]=tmp;
i++;
j--;
}
}
int tmp=nums[j];
nums[j]=pivot_num;
nums[l]=tmp;
quicksort2(nums,0,j-1);
quicksort2(nums,j+1,r);
return ;
}
void QuickSort(vector<int> nums) {
int n=nums.size();
cout<<"Original Nums: ";
for (int i = 0; i < n; i++)
cout << nums[i] << ' ';
cout << endl;
cout<<"Nums Length: "<<n<<endl;
cout<<"QuickSort: "<<endl;
//vector<int> merged_nums=quicksort1(nums);
quicksort2(nums,0,n-1);
cout << "Sorted Nums: "<<" ";
for (int i = 0; i < n; i++)
cout << nums[i] << ' ';
cout << endl;
cout<<"-------------------------------------------------"<<endl;
}
int main() {
vector<int> nums = {61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62};
QuickSort(nums);
return 0;
}
代码运行结果：
Original Nums: 61 17 29 22 34 60 72 21 50 1 62
Nums Length: 11
QuickSort:
Sorted Nums: 1 17 21 22 29 34 50 60 61 62 72
-------------------------------------------------
时间复杂度：
- 最优情况（Best Case）：当每次分区操作都能将数组均匀地分成两部分时，快速排序的性能最好。这种情况下，递归树的深度为 O(logn)，每次分区的时间复杂度为 O(n)，因此最优情况下的时间复杂度为 O(nlogn)
- 最坏情况（Worst Case）：最坏情况发生在每次分区操作都导致极不均衡的分区时，例如数组已经有序或逆序。这种情况下，递归树的深度为 O(n)，每次分区的时间复杂度为 O(n)，因此最坏情况下的时间复杂度为 O(n *n )
- 平均情况（Average Case）：在平均情况下，即输入数据的分布是随机的，快速排序的时间复杂度仍然为 O(nlogn)。这是因为每次分区操作大致能将数组分成两个大小相近的子数组，递归树的深度保持在 O(logn) 范围内。
空间复杂度： O(n)
快速排序是一种原地排序算法，不需要额外的存储空间来存储数据，但递归调用栈会占用额外的空间，在最优和平均情况下，快速排序的递归树深度为 O(logn)，因此空间复杂度为 O(logn)，在最坏情况下，例如数组已经有序或逆序时，递归树的深度为 O(n)，空间复杂度退化为 O(n)
稳定性： 不稳定
7）堆排序（Heap Sort）
待补充
8）计数排序（Counting Sort）
待补充
9）桶排序（Bucket Sort）
待补充