各类排序实现代码-C++版

60 阅读 0 评论 40 点赞

我是靠谱客的博主暴躁玫瑰，最近开发中收集的这篇文章主要介绍各类排序实现代码-C++版，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

冒泡排序

思想：每次把最大的值放在第N N-1 N-2...2个

时间复杂度 N平方，稳定排序

void BubbleSort(std::vector<int>& vec) {
if(vec.size() < 2){
return;
}
for(int i = 0; i < vec.size();i++){
for(int j = 0; j < vec.size() - i -1;j++)
if(vec[j] > vec[j+1])
std::swap(vec[j], vec[j+1]);
}
}

插入排序

类似于打牌，假设大小为一的数组已经有序，然后扩大数组下标，经过比较一次把值放进去。

时间复杂度N平方，稳定排序。它是N平方排序中常用的，在数据基本有序时，效果较好。

void InsertSort(std::vector<int>& vec) {
if(vec.size() < 2){
return;
}
for(int i = 1; i < vec.size();i++){
int cur = i;
while(cur-1 >= 0 && vec[cur-1] > vec[cur]){
std::swap(vec[cur], vec[cur-1]);
cur--;
}
}
}

快速排序

大学本科的时候一直没搞清楚如何快速排序，看了算法导论才明白其中的原理，其实就是分治思想。建议直接看原文，里面有理论的推导，不只是告诉你怎么做，而且告诉你为什么

快速排序最坏的情况就是已经有序，性能接近于插入排序。如果每次找到的pivot为最大值或者最小值，那么公式为 $t(n) = t(n-1) + o(n)$

int _PARTITION(vector<int> &A, int p, int r) {
int x = A[r];
int i = p - 1;
for (int j = p; j < r; j++) {
if (A[j] < x) {
i++;
std::swap(A[i], A[j]);
}
}
std::swap(A[i + 1], A[r]);
return i + 1;
}
void quicksort(vector<int> &A, int p, int r) {
if (p < r) {
int q = _PARTITION(A, p, r);
QuickSort(A, p, q - 1);
QuickSort(A, q + 1, r);
}
}

最喜欢的分区函数，来自于STL的实现，直观又有效，（根据个人喜好改变了部分代码）

int _parition(vector<int> &A, int left, int right){
int pivot = A[right];
int mostR = right;
right--;
while (true) {
while(A[left] < pivot) left++;
while (pivot < A[right]) right--;
if(!(left<right)) {
swap(A[left], A[mostR]);
return left;
}
std::swap(A[left], A[right]);
}
}

归并排序


void MergeSortArr(int arr[], int left, int mid, int right) {//该函数同于将两个有序列合并成一个有序列，同时当两个有序列都为同一个元素是一样可以处理
int i = left, j = mid + 1;//两个索引用来遍历两个有序列
int k = 0;//k用来遍历暂存数组temp
int temp[right - left + 1];//开一个数组暂时存放
while (i <= mid && j <= right) {//对两个有序列进行遍历排序，有一个序列遍历完成结束循环
if (arr[i] < arr[j])
temp[k++] = arr[i++];
else
temp[k++] = arr[j++];
}
while (i <= mid) {//将另外一个没有遍历完全的有序列全部插入到temp中
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
//！！这里需要注意循环的条件里面不能使用left因为left的值在改变
for (i = 0; i < k; i++)//将排好序的序列更新到目标数组中
arr[left++] = temp[i];
}
//递归方法
void MergeSort(int arr[], int left, int right) {
if (left == right)//如果两个划分为同一元素，递归结束
return;
int mid = (left + right) / 2;//对本个划分再次进行划分
MergeSort(arr, left, mid);//对左边的序列进行划分此条命令结束代表左边的序列已经有序
MergeSort(arr, mid + 1, right);//对右边的序列进行划分此条命令结束代表右边的序列已经有序
MergeSortArr(arr, left, mid, right);//和并两个序列
}

可以看到快速排序的递归部分其实是树的前序遍历，归并排序是后序遍历