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

排序算法总结

ops 2025/9/3 12:37:38

在这里插入图片描述

在讲解排序算法之前，我们需要先了解一下排序
所谓排序，就是将数据按照我们的想法将其按照一定规律组合在一起
稳定性：一组数据中的数据是否在排序前后都保持的一定的前后顺序关系，比如在排序前a[3]=2 a[5]=2，这时他们有着前后的顺序关系，在排序后，扔保持着第一个2在第二个2的后面，这种就是稳定的，废话不多说，直接上干货

一、插入排序

思想：将待排序的数据插入到已排好的数据中去，比如我们在玩扑克牌时，我们抓起一张牌，就要选择一个合适的位置进行插入，使其保持有序，这样也方便我们出牌
插入某个数据时，将这个数据与其前一个位置的数据进行比较，如果小于前一个位置的数据，即a[i]<a[i-1]，让前一个位置的数据前后挪一个位置，待排序的数据继续和前一个位置进行比较，直到找到一个合适的位置，将其插入即可，（直接交换也可以，比较之后，符合要求直接交换）
请添加图片描述
不交换

void InsertSort(int* a, int n)
{for (int i = 0; i <= n - 2; i++){int end = i;int tmp = a[end + 1];while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;}
}```cpp
void InsertSort2(int* a, int n)
{for (int i = 0; i <= n - 2; i++){int end = i;int tmp = a[end + 1];while (end >= 0){if (tmp < a[end]){swap(a[end + 1], a[end]);end--;}else{break;}}}
}

1 元素集合越接近有序，直接插入排序算法的时间效率越高
2 时间复杂度O（N^2）
3 空间复杂度 O（1）
4稳定性：稳定

二、冒泡排序

思想：一组数据，每趟排一个数据，比如在排升序时，从数据的第二个位置开始进行比较，本数据和前一个数据进行比较，如果前一个数据大于本数据，两数据交换，一趟可以排一个数据，依次排序，当某一趟一个数据都没有交换时，说明数据已经有序，可以定义flag进行标记，如果已经有序，break即可

void BubbleSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){int flag = 0;for (int j = 1; j < n - i; j++){if (a[j - 1] > a[j]){swap(a[j - 1], a[j]);flag = 1;}}if (flag == 0) break;}
}

请添加图片描述
时间复杂度 O（N^2）
空间复杂度 O（1）
稳定性：稳定

三、选择排序

思想：遍历整个数据，找出其中的最大值和最小值，最大值与数据的最后一个位置的数据进行交换，最小值与数据的最左位置的数据进行交换，然后缩小区间（left++ ，right–），继续执行操作

void SelectSort(int* a, 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 (a[i] < a[mini]) mini = i;if (a[i] > a[maxi]) maxi = i;}swap(a[begin], a[mini]);if (maxi == begin){maxi = mini;}swap(a[end], a[maxi]);begin++;end--;}
}

请添加图片描述

时间复杂度O（N^2）
空间复杂度O（1）
稳定性：不稳定

四、堆排序

思想：堆排序是利用树，将数据建堆，然后根据情况向上或向下调整（升序建大堆，降序建小堆）

void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] > a[child]){child++;}if (a[child] > a[parent]){swap(a[child], a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
void HeapSort(int* a, int n)
{for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}
}

时间复杂度 O（N*logN）
空间复杂度 O（1）
稳定性：不稳定

五、希尔排序

思想：分组，组内排序，更改组的大小，无序->接近有序->有序

void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;for (int i = 0; i < n - gap; i += gap){int end = i;while (end >= 0){if (a[end + gap] < a[end]){swap(a[end + gap], a[end]);end -= gap;}else{break;}}}}
}

希尔排序是对直接插入排序的优化
当gap>1时都是预排序，目的是让数组更接近有序，gap=1时，数据已经接近于有序，效率就会高很多
一般gap/3+1
时间复杂度：一般我们认为是O（n^1.3）
空间复杂度O（1）
稳定性：不稳定

六、快速排序

快速排序是一个非常重要的排序算法，在很多语言的库中，排序函数的底层都是快速排序，这是一个很优秀，很值得我们去学习的方法，也是比较复杂的排序算法
思想：任取待排序元素序列中的元素作为基准值，按照该排序码将集合分为两个子序列，左子序列中所有的元素均小于基准值，右子序列中所有的元素均大于基准值，然后重复该过程

1 hoare 版本快排

在基准值的选取方面有很多方法，随机数选取，三数取中，固定第一个值就为基准值…等等
在数据小到一定范围时，这时候递归也已经很深，我们知道，递归可以理解一棵树，越到下面，叶子越多，所以可以利用其他简单的排序，比如插入排序，将这个小范围数据进行排序
如果升序：左找大于基准值的数，右找小于基准值的数，都找到后交换

void QuickSort1(int* a, int left, int right)
{//递归出口if (left >= right) return;if (right - left + 1 < 10){InsertSort(a, right - left + 1);}else{int begin = left, end = right;//int keyi = left;//int randi = rand() % (right - left+1);//随机数，尽量避免原数据有序，后达到最坏的效果，选出一个随机的数，与原left位置进行交换//									//继续下面逻辑//randi += left;//swap(a[left], a[randi]);int midi = GetMidi(a, left, right);swap(a[midi], a[left]);int keyi = left;while (left < right){while (left < right && a[right] >= a[keyi]){right--;}while (left < right && a[left] <= a[keyi]){left++;}swap(a[left], a[right]);}swap(a[keyi], a[left]);keyi = left;QuickSort1(a, begin, keyi - 1);QuickSort1(a, keyi + 1, end);}
}

请添加图片描述

2 前后指针法

初始时，基准值，prev都在数据起始位置，cur在后一个位置
cur不断向后进行遍历，当cur指向位置的数据小于基准值时，prev++，并交换两指针所指的数据，最后基准值数据与prev数据进行交换，递归基准值左右两个小区间的数据

void QuickSort2(int* a, int left, int right)
{if (left >= right) return;int prev = left;int keyi = left;int cur = left + 1;while (cur <= right){if (a[cur] >= a[keyi]){cur++;}else{prev++;swap(a[prev], a[cur]);cur++;}}swap(a[keyi], a[prev]);keyi = prev;QuickSort2(a, left, keyi - 1);QuickSort2(a, keyi+1, right);
}

请添加图片描述

3 分治快速排序

利用随机数取基准值，将数据分为三块，大于基准值，等于基准值，小于基准值

int GetRandomNum(vector<int>& nums, int left, int right)
{int r = rand();return (r % (right - left + 1) + left);
}
void qsort(vector<int>& nums, int l, int r)
{if (l > r) return;int key = GetRandomNum(nums, l, r);int n = nums.size();int left = l - 1, right = r + 1, i = l;while (i < right){if (nums[i] < key){swap(nums[++left], nums[i++]);}else if (nums[i] == key){i++;}else{swap(nums[--right], nums[i]);}}qsort(nums, l, left);qsort(nums, right, r);
}//分治法快速排序（随机数+数组分三块（小于，等于，大于））
void QuickSort3(vector<int>& nums)
{srand(time(NULL));qsort(nums, 0, nums.size() - 1);
}

4 非递归版快速排序

利用数据结构栈来代替递归，排序的左右区间不断入栈出栈

void QuickSortNonRe(int* a, int left, int right)
{stack<int> st;st.push(right);st.push(left);while (!st.empty()){int begin = st.top();st.pop();int end = st.top();st.pop();int prev = begin;int keyi = begin;int cur = begin + 1;while (cur <= right){if (a[cur] >= a[keyi]){cur++;}else{prev++;swap(a[prev], a[cur]);cur++;}}swap(a[keyi], a[prev]);keyi = prev;if (keyi + 1 < end){st.push(end);st.push(keyi+1);}if (begin < keyi - 1){st.push(keyi-1);st.push(begin);}}
}

时间复杂度O（N*logN）
空间复杂度O（logN）
稳定性：不稳定

七、归并排序

归并排序，分组，分组，再分组，合并，合并，再合并
需要利用额外空间，然后再拷贝回来

void _MergeSort(vector<int>& nums,int left,int right)
{if (left >= right) return;int mid = (left + right) >> 1;_MergeSort(nums, left, mid);_MergeSort(nums, mid+1, right);int cur1 = left, cur2 = mid + 1, i = 0;while (cur1 <= mid && cur2 <= right){tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];}while (cur1 <= mid) tmp[i++] = nums[cur1++];while (cur2 <= right) tmp[i++] = nums[cur2++];for (int i = left; i <= right; i++){nums[i] = tmp[i-left];}
}void MergeSort(vector<int>& nums)
{tmp.resize(nums.size());_MergeSort(nums, 0, nums.size() - 1);
}