当前位置：首页 > news >正文

【10种排序算法总结】C++实现

news 来源：原创 2024/5/20 7:16:35

说明：

假设排序后的序列均为升序序列
待排序序列的元素均为int型
文章内容为个人的学习整理，如有错误，欢迎指正！

文章目录

- 1. 快速排序
- 2. 归并排序
- 3. 冒泡排序
- 4. 插入排序
- 5. 希尔排序
- 6. 选择排序
- 7. 堆排序
- 8. 基数排序
- 9. 计数排序
- 10. 桶排序
- 一道LeetCode题目

1. 快速排序

算法描述：从序列中选定一个枢轴元素pivot，并将左侧大于pivot的元素移动到pivot的右侧，将右侧小于pivot的元素移动到pivot的左侧。递归处理左右子序列。

//划分，left和right界定了此次划分的范围
int Partition(vector<int>& nums, int left, int right){int pivotPos = rand()%(right-left+1) + left; //生成[left,right]之间的随机数int pivot = nums[pivotPos];//交换，得到哨兵swap(nums[left], nums[pivotPos]); //将pivot交换到最左边，并将其作为哨兵//开始交换两边的元素while(left<right){     //这里要注意，因为把最左侧元素作为哨兵，所以要县移动右指针   while(left<right && nums[right]>=pivot) right--;nums[left] = nums[right]; //把右边比pivot小的元素换到左边while(left<right && nums[left]<=pivot) left++;nums[right] = nums[left]; //把左边比pivot大的元素换到右边}nums[left] = pivot; //最后左右指针相遇，将pivot放到其最终位置return left;//返回pivot的最终位置
}
//快排(递归)，left和right界定了此次快排的范围
void QuickSort(vector<int>& nums, int left, int right){if(left >= right) return;//递归返回条件int pivotPos = Partition(nums, left, right);//获得第一次划分后pivot的位置QuickSort(nums, left, pivotPos-1); //递归处理左侧部分QuickSort(nums, pivotPos+1, right); //递归处理右侧部分
}

关于快排指针的移动次序和其他的快排写法，在这篇文章中有详细叙述：https://www.cnblogs.com/MAKISE004/p/16909610.html

2. 归并排序

2路归并
算法描述：依次划分序列直至所有子序列长度为1，依次归并前后相邻的两个子序列，使归并后的序列有序，直至所有的子序列归并完毕，得到整体有序的序列。

void MergeSort(vector<int>& nums, int left, int right){if(left>=right) return; // 递归返回条件int mid = (left+right)/2; // 从中间划分MergeSort(nums, left, mid); // 处理左子序列MergeSort(nums, mid+1, right); //处理右子序列Merge(nums, left, mid, right); // 归并
}
//归并
void Merge(vector<int>& nums, int left, int mid, int right){vector<int> temp;  // 辅助数组temp.clear();int i=left, j=mid+1; while(i<=mid && j<=right){if(nums[i] < nums[j]) temp.push_back(nums[i++]); else temp.push_back(nums[j++]);// 将较小值存入辅助数组中        }while(i<=mid) temp.push_back(nums[i++]); //复制左子序列剩余部分while(j<=right) temp.push_back(nums[j++]); // 复制右子序列剩余部分int length = right-left+1; //该归并段长度for(int i=0; i<length; i++) nums[left+i] = temp[i]; //将排好序的部分复制到原数组中
}

3. 冒泡排序

算法描述：（升序）依次比较相邻元素，依次将较大元素移动到数组末尾（大元素上浮）。

// 冒泡排序
void BubbleSort(vector<int>& nums){int n = nums.size();for(int i=0; i<n-1; i++){for(int j=0; j<n-1-i; j++){if(nums[j]>nums[j+1]) swap(nums[j], nums[j+1]);}}
}
//添加flag，减少比较次数
void BubbleSort2(vector<int>& nums){int n = nums.size();int flag = false; // 用来标记这一趟排序是否发生元素的交换for(int i=0; i<n-1; i++){flag = false;for(int j=0; j<n-1-i; j++){if(nums[j] > nums[j+1]){swap(nums[j], nums[j+1]);flag = true;}            }if(!flag) break; //若这一趟没有发生元素交换，可以提前终止算法}return;
}

4. 插入排序

算法描述：第i趟排序，序列L[0]~L[i-1]为有序子序列，将L[i]插入这个有序子序列中，经过n趟排序得到整体有序的序列。

void InsertSort(vector<int>& nums){int n = nums.size();for(int i=1; i<n; i++) { //i从1开始，默认nums[0]为一个有序子序列if(nums[i] >= nums[i-1]) continue; //若前后相邻的两个元素为非递减排列，直接插入int temp = nums[i];int j = i-1;while(j>=0 && nums[j]>temp) {nums[j+1] = nums[j];j--;    //从后往前找插入位置,并将元素后移}nums[j+1] = temp; //插入}return;
}//采用折半查找的思想来找第i个元素的插入位置
//折半插入排序仅减少了比较元素的次数，而元素的移动次数并未改变
void InsertSort2(vector<int>& nums){int n = nums.size();for(int i=1; i<n; i++) {// 从i=1开始，默认nums[0]是一个有序子序列if(nums[i] >= nums[i-1]) continue; //若前后相邻的两个元素为非递减排列，直接插入int left = 0, right = i-1;while(left<=right){int mid  = (left+right)/2;if(nums[mid] < nums[i]) left = mid+1;else right = mid-1;}int temp = nums[i];int index = right+1; // nums[i]插入的位置for(int j=i-1; j>=index; j--) nums[j+1] = nums[j];nums[index] = temp; // 插入}return ;
}

5. 希尔排序

算法描述：希尔排序是优化的插入排序。对于含有n个元素的待排序列，每次取一个小于n的整数作为步长（d），将序列分为若干子序列，所有距离为步长倍数的元素属于同一子序列。对每个子序列中的元素进行直接插入排序，得到分组内有序的子序列。之后减小d的值，重复执行分组和排序操作，直至d大小为1，此时得到整体有序的序列。

void ShellSort(vector<int>& nums){int n = nums.size();for(int d=n/2; d>=1; d=d/2){//根据步长分组，步长的变化情况为每次减少一半for(int i=0; i<d; i++){//依次处理每个分组// 对每个分组内的元素进行直接插入排序for(int j=i+d; j<n; j+=d){if(nums[j] >= nums[j-d]) continue;int temp = nums[j];int k = j-d;while(k>=0 && nums[k] > temp){nums[k+d] = nums[k];k -= d;}nums[k+d] = temp; // 插入元素}}}return;
}

这篇博文（地址）提到了希尔排序的另一种写法，是穿插处理分组的，而不是处理完第一个分组再处理下一个分组。

6. 选择排序

算法描述：第i趟排序，从L[i]及其之后的元素中选择最小值，并与L[i]交换

void SelectSort(vector<int>& nums) {int n = nums.size();int min_index= 0;for(int i=0; i<n-1; i++){min_index = i;for(int j=i+1; j<n; j++){if(nums[j] < nums[min_index]) min_index = j;}swap(nums[i], nums[min_index]);}return ;
}

7. 堆排序

void BuildMaxHeap(vector<int>& nums){int n = nums.size();for(int i = n/2; i>=0; i--){//从第一个非叶结点开始调整MaxHeapAdjust(nums, i, n);}return;}void MaxHeapAdjust(vector<int>& nums, int i, int n){for(int j=i*2+1; j<n; j=j*2+1){//j初始时指向第i个结点的左孩子int lchild=j, rchild=j+1;if(j+1<n && nums[rchild]>nums[lchild]) j++;//调整j使其指向左右孩子中的较大者if(nums[i] >= nums[j]) break;//说明从i结点往下的结点都符合大根堆的要求，提前结束筛选else{swap(nums[i],nums[j]);//否则交换元素值i = j;//同时修改i的指向，以便继续向下筛选}}return;}void HeapSort(vector<int>& nums){int n = nums.size();BuildMaxHeap(nums);for(int i=n-1; i>0; i--){            swap(nums[0], nums[i]);MaxHeapAdjust(nums, 0, i);//注意，i是下标，处理完第i个元素后，剩余的元素个数为(i-1)-0+1=i}}

8. 基数排序

//获取序列中的最大位数（个十百千）
int GetMaxDigit(vector<int>& nums){int maxdata = *max_element(nums.begin(), nums.end()); //获取序列中的最大值int maxdigit = 0;//通过获取最大值的最高位，就能获得整体的最高位while(maxdata){maxdata /= 10;maxdigit++;}return maxdigit;
}
void RadixSort(vector<int>& nums){int n = nums.size();int base = 1;int maxdigit = GetMaxDigit(nums);vector<int> temp(n, 0); //辅助数组vector<int> count(10, 0); //统计数组，记录每个数位出现的次数while(maxdigit--){ fill(count.begin(), count.end(), 0);//将count中所有元素置零for(int i=0; i<n; i++){int index = (nums[i]/base) % 10;count[index]++;}//计数累加，用于后续的排序for(int i=1; i<10; i++)count[i] = count[i] + count[i-1];//从后往前进行排序for(int i=n-1; i>=0; i--){int index = (nums[i]/base) % 10;temp[count[index] - 1] = nums[i];count[index]--;}base *= 10;copy(temp.begin(), temp.end(), nums.begin());//将第i趟排序的结果复制到原数组中}return;
}

9. 计数排序

算法思想：计数排序是一种非基于比较的排序算法，以空间换时间已达到排序的目的。
算法描述：假设由所有待排序元素组成的集合为S，S的大小为m，则定义一个大小为m的数组count，用来记录每个数字元素出现的次数。之后按照count下标顺序将数字元素放入原数组中即可。
注意：计数排序只能对整数进行排序；排序前需要确定数据的范围，若数据范围很大，则要开辟很大的空间。

void CountSort(vector<int>& nums){int n = nums.size();//根据最大元素和最小元素来确定数值的范围int maxdata = *max_element(nums.begin(), nums.end());int mindata = *min_element(nums.begin(), nums.end());vector<int> count(maxdata-mindata+1, 0); //创建count数组，初始元素均为0for(int i=0; i<n; i++)count[nums[i]]++; //根据count数组进行排序int i = 0;for(int data=mindata; data<=maxdata; data++){while(count[data]){ //当data出现的次数不为0nums[i++] = data;count[data]--;}}return;
}

10. 桶排序

算法思想：桶排序是一种非基于比较的排序算法，通过构建多个映射数据的桶，将数据映射到桶内，对桶内数据进行排序，以空间换时间来实现排序的目的，相当于计数排序的升级。
算法描述：对于n个待排数据，定义k个映射数据的桶，假定每个桶的大小为m（即数据范围是：0~ m-1; m~2m-1;以此类推），将数据元素nums[i]放到编号为nums[i]/m的桶中。再对桶内数据进行排序。

//假设数范围是[0,99]
const int N = 10; //假设桶的个数为10
const int m = 10; //假设桶的大小为10void BucketSort(vector<int>& nums){int n = nums.size();vector<vector<int>> bucket(N); //创建桶for(int i=0; i<n; i++)bucket[nums[i]/m].push_back(nums[i]); //将元素放入对应的桶中int k = 0;for(int i=0; i<N; i++){sort(bucket[i].begin(), bucket[i].end());//对桶内元素进行排序for(int j=0; j<bucket[i].size(); j++){nums[k++] = bucket[i][j]; //将桶内元素放入原数组}}
}