#创作计划#常见排序方法（会更新）
2025-06-07 09:42:43
发布于：浙江
368阅读
0回复
0点赞
注：本帖均已升序排列为例@AC君
由于作者忙于学业以及一些事，接下来的三个排序方法将在暑假更新（也可能提前）。
点个赞吧
第一种：冒泡排序
冒泡排序的基本思想：冒泡排序就是通过多趟“冒泡”逐步将最小值移动到数组的前端，之后将已排好的数字移出排序范围，重复操作。最后逐步把序列排好
这里我们用如下图表式（这里以无序序列为例，有点抽象，还请见谅）：
我们先比较最后两个数：
很明显，1比2小，所以不做任何交换。
接下来，我们比较3和1：
1比3小，所以我们让更小的1与3交换，使1到3的左边：
然后在比较一下1和4,1比四小，所以我们把更小的1挪到4的左边：
这样第一轮交换就结束了。我们把排好的数字移出范围，接着比较2和3……：
重复上述操作，最后冒泡排序完成：
代码实现：
#include <iostream>
using namespace std;
int main(){
int a;
cin >> a;
int sz[10086]={};
for(int i=1;i<=a;i++)
cin >> sz[i];
//排序中
for(int j=a-1;j>0;j--){
for(int i=1;i<=j;i++){
if(sz[i]>sz[i+1])
swap(sz[i+1],sz[i]);
}
}//输出
for(int i=1;i<=a;i++){
cout << sz[i]<<" ";
}
return 0;
}
冒泡排序的时间复杂度为
第二种，选择排序，这里也以无序序列为例：
选择排序的基本思想：通过遍历找到序列中的最小值，然后将最小值移动到序列最前端，把排好的数移出范围，重复上述操作，排序完成。
同样以图画为例：
首先遍历序列：
找到最小值1：
将最小值1移到最前边：
将排好的数移出排序范围，并重复上述操作：
……↓
代码：
#include <iostream>
using namespace std;
int main(){
int a;
cin >> a;
int sz[105]={};
for(int i=1;i<=a;i++)
cin >> sz[i];
//排序中……
for(int i=1;i<=a-1;i++){
int n=i;
for(int j=i+1;j<=a;j++){
if(sz[j]<sz[n]){
n=j;
}
}
swap(sz[n],sz[i]);
}//输出
for(int m=1;m<=a;m++)
cout <<sz[m]<<" ";
return 0;
}
选择排序时间复杂度为，与冒泡排序相同。
第三种，插入排序，实例同上：
插入排序思路：这里把插入数据与原有数据相比较，大于往右移，找到合适的位置；小于则向左移，找到合适的位置，之后插入进去。
首先插入数字“2”并标记为已排序：
接下来插入数字“1”并找到合适的位置。1比2小，放到2的左边一位：
继续插入……
排序完成。
代码：
#include <iostream>
using namespace std;
int main(){
int a;
cin >> a;
int sz[105]={};
for(int i=1;i<=a;i++){
cin >>sz[i];
}//排序
for(int i=2;i<=a;i++){
int n=sz[i];
int j=i-1;
while(sz[j]>n and j>=1){
sz[j+1]=sz[j];
j--;
}sz[j+1]=n;
}//输出
for(int i=1;i<=a;i++)
cout << sz[i]<<" ";
return 0;
}
时间复杂度与上述相同，均为
第四种，sort排序：
sort有三个参数分别为排序起始位置，排序结束的位置以及比较函数（可省略，省略后默认升序）。比较函数(cmp)是bool 类型。在定义参数是是这样定义的bool cmp(m a,m b)，这里m指要排序的类型，如果是结构体就写bool cmp(结构体名 a,结构体名 b)。升序就写return a<b，降序就写return a>b。
代码：
降序：
#include <bits/stdc++.h>
using namespace std;
bool cmp(int a,int b){
return a>b;
}
int main(){
int a;
cin >> a;
int sz[10086]={};
for(int i=1;i<=a;i++){
cin >>sz[i];
}sort(sz****z+a+1,cmp);
for(int i=1;i<=a;i++)
cout <<sz[i]<<' ';
return 0;
}
升序（这里比较函数可以省略）：
#include <bits/stdc++.h>
using namespace std;
bool cmp(int a,int b){
return a<b;
}
int main(){
int a;
cin >> a;
int sz[10086]={};
for(int i=1;i<=a;i++){
cin >>sz[i];
}sort(sz****z+a+1,cmp);
for(int i=1;i<=a;i++)
cout <<sz[i]<<' ';
return 0;
}
时间复杂度为
sort排序主要是快速排序，但因为快排的最坏复杂度是，所以为了维持的复杂度，加入了堆排序（）和插入排序（）。
第六种，桶排序：
桶排序的主要思想：我们可以设计出有限的桶，之后将所需排序的值放入桶中。桶内元素大于0是就输出桶的编号。里面有几就输出几次。
下面我们还是用图来描述：
这里我们用，序列中最大值为4，我们就设立从1到4个桶， 读取第一个元素放入桶中（一号桶元素加一）：
读取第二，三个元素（过程跳过），接下来读取两个“4”，由于有两个相同元素，所以我们在4号桶里放两个：
接下来进行输出，先输出前三个数：
最后，4号桶里元素为2，我们就输出两个四，排序完成：
代码实现（这里稍微优化了一下）：
#include <iostream>
using namespace std;
int main(){
int a;
cin >> a;
int sz[10086]={};
int n=-100;
//放入桶中
for(int i=1;i<=a;i++){
int x;
cin >> x;
sz[x]++;
n=max(x,n);
}//输出桶
for(int i=1;i<=n;i++){
for(int j=1;j<=sz[i];j++){
cout << i<<" ";
}
}
return 0;
}
时间复杂度：，由于桶排的时间复杂度（本代码）是由序列中最大的元素决定的，所以如果序列中元素较大，就不要使用桶排序。优化前是其中n是题目中所给的的最大值。像这样：。且桶排序不能处理序列中元素为负数的情况
第六种（重点），归并排序：
归并排序的思想：归并排序就是把一个无序序列进行分割，之后进行合并的排序算法。听着是不是很简单？实际一点也不简单。这里还是用序列来模拟。
首先我们把数据往下分（这里以二分为例），不需要管什么顺序：
再分：
现在我们已经分完了，接下来就是合并了。首先我们合并4与3，因为3比4小，所以先上3，右半边（既3所在处）没有数了，我们就把左半边（4所在处）的所有数拿上来：
接下来合并1和2，1比2小，先上1，左半边没有数了，把右半边所有数拿上去：
在合并序列3,4与序列1,2。1比3小，先拿1，并将比较箭头向后移：
比较3和2,2比三小，上二，并将箭头向后移：
此时右半边已经没有数了，我们就直接上左半边，排序完成：
代码实现：
首先对序列进行分割，每次分为左半边（l，mid）和右半边（mid+1，r），并进行递归，直到不能在分为止。既l==r：
void MergeSort(int l , int r)
{
//2.1、递归的结束条件:只有一个数，就不用再递归下去，直接返回
if(l==r){
return ;
}
//2.2、找到中间位置，递归处理左半部分，递归处理右半部分
int mid = (l + r) / 2;
MergeSort(l,mid);
MergeSort(mid+1,r);
}
接下来合并。一次比较连边的数，小的放入临时数组（temp）中，并将下标右移一位。当其中一个半边全部拿完时，把另一边的所有数上移：
void MergeSort(int l , int r){
int i = l, j = mid + 1, k = l;
while(i <=mid && j <= r)
{
if(a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
//3.1、判断两个序列是否有剩余，有剩余的，全部放入结果数组 temp
while(i <= mid)
temp[k++] = a[i++];
while(j <= r)
temp[k++] = a[j++];
//4、把结果数组 temp 重新赋给 a 数组
for(int i=l;i<=r;i++)
a[i]=temp[i];
}
最后将分割与合并合并，排序完直接输出：
#include<iostream>
using namespace std;
int n , a[1000005] , temp[1010];
void MergeSort(int l , int r){
//2.1、递归的结束条件:只有一个数，就不用再递归下去，直接返回
if(l==r){
return ;
}
//2.2、找到中间位置，递归处理左半部分，递归处理右半部分
int mid = (l + r) / 2;
MergeSort(l,mid);
MergeSort(mid+1,r);
//3、合并，两个序列分别为[l,mid] 和 [mid+1,r]，从最左边开始，依次比较，小的数放入结果数组temp，下标右移
int i = l, j = mid + 1, k = l;
while(i <=mid && j <= r)
{
if(a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
//3.1、判断两个序列是否有剩余，有剩余的，全部放入结果数组 temp
while(i <= mid)
temp[k++] = a[i++];
while(j <= r)
temp[k++] = a[j++];
//4、把结果数组 temp 重新赋给 a 数组
for(int i=l;i<=r;i++)
a[i]=temp[i];
}
int main()
{
//1、定义变量 n 和数组
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
//2、划分，左端点为 1，右端点为 n，递归处理
MergeSort(1 , n);
for(int i=1;i<=n;i++)
cout << a[i]<<" ";
return 0;
}
时间复杂度：且稳定。归并排序适合处理数据量较大的时候（例如）。同时，归并把一个大问题分为了许多个子问题，这种思想也叫。
第七种，快速排序：
快排的思想。与归并一样，都运用了的思想。快排主要是把序列分成（基准值也可叫枢轴）。之后将左右两个部分继续执行同样的操作。直到排序完成。接下来用序列来演示快排的过程。
首先选择基准值，这里随机选择了5。
然后将数分别插入，1比5小，把1放在5的左边：
接下来比较2和5,2比5小，放到5的左边。注意，这里不需要看顺序，否则就变成了插入排序。
插入数字12，比5大，放在5的右边
插入数字3，比5小，放在5的左边。第一轮快排完成：
接下来我们把基准值5先提出来，这样就分成了左右两个部分。我们先来排左边：这里以2为基准值，3比2小，放到2的右边；1比2小，放到2的右边：
这样左边就排好了。接下来排右边，右边只有1个数，所以无序排序。插入基准值5，排序结束：
代码实现（忘了从哪盗的模板了）：
重复执行把大于基准值的数一道右边，把小于基准值的数移到左边，并用递归继续执行：
void partition(int a[],int l,int r)
{
int x=a[l],i=l,j=r;
if(l>=r) return;
while(i<j)
{
while(i<j and a[j]>=x) j--;
a[i]=a[j];
while(i<j and a[i]<=x) i++;
a[j]=a[i];
}
a[i]=x;
partition(a,l,i-1);
partition(a,i+1,r);
}
整体代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3+10;
int a[N];
int n;
void partition(int a[],int l,int r)
{
int x=a[l],i=l,j=r;
if(l>=r) return;
while(i<j)
{
while(i<j and a[j]>=x) j--;
a[i]=a[j];
while(i<j and a[i]<=x) i++;
a[j]=a[i];
}
a[i]=x;
partition(a,l,i-1);
partition(a,i+1,r);
}
int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
partition(a,0,n-1);
for(int i=0;i<n;i++)cout << a[i]<<" ";
return 0;
}
时间复杂度：，但如果每一次都选择了最小的基准值，那么快排就退化成了选择排序或不引入随机化的话，时间复杂度就可能会指数级升高，最坏复杂度为。同时，在数据规模较大时，最好食用归并，快排容易崩。
第八种，堆排序：
整体思路：堆排序是利用了堆的特点，即为取出最小元素的时间复杂度为。
首先还是以图片为例。这里以序列为例（之前图片太丑了，稍稍优化了一下）：
按升序构建一个堆（之后就用圆圈代替了）：
取出堆的第一个元素，并重新构建堆（这里不多讲了哈）：
继续取出元素并重构堆……排序完成：
代码实现（呃不会写用ai了）：
先写一个构建堆的代码：
void heapify(vector<int>& arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
取出堆中元素：
void heapSort(vector<int>& arr) {
int n = arr.size();
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
组合起来即可。整体代码：
#include <iostream>
#include <vector>
using namespace std;
void heapify(vector<int>& arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(vector<int>& arr) {
int n = arr.size();
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
int main() {
vector<int> arr;
int n, num;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> num;
arr.push_back(num);
}
heapSort(arr);
for (int num : arr) cout << num << " ";
return 0;
}
懒人代码（堆排版，直接用STL容器+内置函数）：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void heapSort(vector<int>& arr) {
make_heap(arr.begin(), arr.end());
sort_heap(arr.begin(), arr.end());
}
int main() {
vector<int> arr;
int n, num;
cin >> n;
while(n--) {
cin >> num;
arr.push_back(num);
}
heapSort(arr);
for(const auto& x : arr) cout << x << " ";
return 0;
}
有帮助，赞一个