专栏文章

浅谈C++中的部分排序算法

FFengLing_
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minpw8u4
此快照首次捕获于
2025/12/02 06:25
3 个月前
此快照最后确认于
2025/12/02 06:25
3 个月前
查看原文

前言

排序是C++中不可或缺的一部分内容.在C++中,我们有多种方式来实现升序或降序的排序,这篇文章将介绍基础的排序算法.

目录

  1. 冒泡排序
  2. 选择排序
  3. 插入排序
  4. 希尔排序
  5. 归并排序
  6. 快速排序
  7. 计数排序

前置知识

原地排序算法
原地排序算法指的是在排序过程中,除了原始数据本身所占用的存储空间外,只需要固定数量的额外(辅助)存储空间(通常是几个变量)来完成排序的算法.换句话说,排序过程主要通过在原始数组内部通过交换或移动元素来完成,不依赖于与待排序数据量成比例的额外空间.
稳定性
如果待排序的序列中存在多个具有相同关键字的元素,在排序之后,这些相等元素的相对顺序是否保持不变.如果是,就代表这个排序算法具有稳定性,反之则不具有.

冒泡排序(Bubble Sort)

基本思想

重复地遍历待排序的序列,一次比较两个相邻的元素,如果它们的顺序错误就把它们交换过来.遍历序列的工作是重复地进行直到没有再需要交换,也就是说该序列已经排序完成.

步骤

  1. 比较相邻的元素.如果第一个比第二个大(升序情况),就交换它们两个.
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.这步做完后,最后的元素会是最大的数.
  3. 针对所有的元素重复以上的步骤,除了最后一个.
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较.

代码实现

CPP
#include<iostream>
using namespace std;
int a[1005];
int main(){
	int n,cnt = 0;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<n;i++){
		bool f=true;
		for(int j=1;j<=n-i;j++){
			++cnt;
			if(a[j]>a[j+1]){
				f=false;
				swap(a[j], a[j+1]);
			} 			
		}
		if(f)break;
	}
	cout<<cnt<<endl;
	for(int i=0; i<n; i++) cout << a[i] <<" ";
	return 0;
}

测试数据

输入

CPP
8
1 3 4 5 6 8 7 2

输出

CPP
1 2 3 4 5 6 7 8

复杂度及稳定性分析

时间复杂度
最佳情况(已有序): O(n)O(n)
最坏情况(逆序): O(n2)O(n^2)
平均: O(n2)O(n^2)
空间复杂度
O(1)O(1),属于原地排序算法
稳定性
稳定

选择排序(Selection Sort)

基本思想

首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾.以此类推,直到所有元素均排序完毕.

步骤

  1. 初始状态:无序区为 R[1…n]R[1 \dots n],有序区为空。
  2. 第 i 趟排序 (i=1,2,3…n−1)(i=1,2,3…n-1) 开始时,当前有序区和无序区分别为 R[1…i−1]R[1 \dots i-1] 和 R[i…n]R[i \dots n] .该趟排序从当前无序区中选出关键字最小的记录 R[k]R[k] ,将它与无序区的第1个记录 R[i]R[i] 交换.
  3. 这样,有序区增加了一个记录,无序区减少了一个记录.
  4. n−1n-1 趟结束,数组有序化了.

代码实现

CPP
#include<iostream>
using namespace std;
int a[1005];
int main(){
	int n,i,j;
	cin>>n;
	for(i=1;i<=n;i++)cin>>a[i];
	for(i=1;i<n;i++) 
		for(j=i+1;j<=n;j++) 
			if(a[i]>a[j])swap(a[i],a[j]);
	for(i=1;i<=n;i++)cout<<a[i]<<" ";
	return 0;
}

测试数据

输入

CPP
8
1 3 4 5 6 8 7 2

输出

CPP
1 2 3 4 5 6 7 8

复杂度及稳定性分析

时间复杂度
最佳情况(已有序): O(n2)O(n^2)
最坏情况(逆序): O(n2)O(n^2)
平均: O(n2)O(n^2)
空间复杂度
O(1)O(1),属于原地排序算法
稳定性
不稳定

插入排序(Insertion Sort)

基本思想

通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入.

步骤

  1. 从第一个元素开始,该元素可以认为已经被排序.
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描.
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置.
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置.
  5. 将新元素插入到该位置后.
重复步骤2~5。

代码实现

CPP
#include<iostream>
using namespace std;
const int N=1e3+10;
int n, a[N];
void Print(){
	for(int i=1; i<=n; i++) cout <<a[i] <<' ';
	cout <<endl;
} 
void insert_sort(int a[], int n){
	int i=0, j=0, temp=0;
	for(i=1; i<=n; i++){
		temp = a[i];
		for(j=i-1; j>0 && temp<a[j]; j--)
			a[j+1] = a[j];
		a[j+1] = temp;
	}
}

int main(){
	cin >> n;
	for(int i=1; i<=n; i++)
		cin >> a[i];
	insert_sort(a, n);
	Print(); 
	return 0;
}

测试数据

输入

CPP
8
1 3 4 5 6 8 7 2

输出

CPP
1 2 3 4 5 6 7 8

复杂度及稳定性分析

时间复杂度
最佳情况(已有序): O(n)O(n)
最坏情况(逆序): O(n2)O(n^2)
平均: O(n2)O(n^2)
空间复杂度
O(1)O(1),属于原地排序算法
稳定性
稳定

希尔排序(Shell Sort)

基本思想

希尔排序是插入排序的一种更高效的改进版本,也称为缩小增量排序.它通过将原始列表分割成多个子序列(由增量间隔决定)来工作,先对每个子序列进行插入排序,然后逐渐减小增量,再次进行排序,直至增量为1,对整个列表进行最后一次插入排序.

步骤

  1. 选择一个增量序列 t1,t2,...,tkt_1, t_2, ..., t_k ,其中 ti>tjt_i > t_j , tk=1t_k = 1.常用增量序列有 n/2,n/4,…,1n/2, n/4, \dots , 1(希尔增量).
  2. 按增量序列个数 k，对序列进行 k 趟排序。
  3. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理。

代码实现

CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,a[N];
int main(){
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	for(int dis=n/2;dis>0;dis/=2){
		int i,j,temp;
		for(i=dis;i<n;i++){
			temp=a[i];
			for(j=i;j>=dis&&a[j-dis]>temp;j-=dis){
				a[j]=a[j-dis];
			}
			a[j]=temp;
		}
	}
	for(int i=0;i<n;i++) cout<<a[i]<<' ';
	return 0;
}

测试数据

输入

CPP
8
1 3 4 5 6 8 7 2

输出

CPP
1 2 3 4 5 6 7 8

复杂度及稳定性分析

时间复杂度
依赖于增量序列的选择,范围在 O(nlog2n)O(n log²n) 到 O(n2)O(n²) 之间.使用希尔增量时最坏情况为 O(n2)O(n²).
空间复杂度
O(1)O(1)
稳定性
不稳定

归并排序(Merge Sort)

基本思想

采用分治法的一个典型应用.将已有序的子序列合并,得到完全有序的序列.即先使每个子序列有序,再使子序列段间有序.

步骤

  1. 分解：将序列递归地分成两半,直到每个子序列只有一个元素(自然有序)。
  2. 解决：递归地对两个子序列进行归并排序.
  3. 合并：将两个已排序的子序列合并成一个有序序列.

代码实现

CPP
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int a[N], b[N], n;

void merge_sort(int l, int r){
	if(l == r) return;
	int mid = (l+r) >> 1;
	merge_sort(l, mid);
	merge_sort(mid+1, r);
	int i = l, j = mid + 1, k = l;
	while(i <= mid && j <= r){
		if(a[i] < a[j]) b[k] = a[i], i++, k++;
		else b[k] = a[j], j++, k++;
	}
	while(i <= mid) b[k++] = a[i++];
	while(j <= r) b[k++] = a[j++];
	for(int i=l; i<=r; i++) a[i] = b[i]; 
}

int main(){
	cin >> n;
	for(int i=1; i<=n; i++) cin >> a[i];
	merge_sort(1, n);
	for(int i=1; i<=n; i++) cout << a[i] << ' ';
	return 0;
}

测试数据

输入

CPP
8
1 3 4 5 6 8 7 2

输出

CPP
1 2 3 4 5 6 7 8

复杂度及稳定性分析

时间复杂度
最佳情况(已有序): O(nlog⁡n)O(n \log n)
最坏情况(逆序): O(nlog⁡n)O(n \log n)
平均: O(nlog⁡n)O(n \log n)
空间复杂度
O(n)O(n)
稳定性
稳定

快速排序(Quick Sort)

基本思想

同样使用分治法.它从一个序列中选取一个元素作为“基准”,然后将序列重新排列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面.之后递归地对基准值左右两个子序列进行快速排序.

步骤

  1. 挑选基准值：从数列中挑出一个元素,称为“基准”.
  2. 分割：重新排序数列，所有比基准值小的元素放在基准前面,所有比基准值大的元素放在基准后面(相等的数可以到任一边.在这个分割结束之后)，对基准值的排序就已经完成.
  3. 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序.

代码实现

CPP
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n, a[N];

void qsort(int l, int r){
	if(l >= r) return;
	int i = l, j = r, k = l;
	while(i < j){
		while(i<j && a[j] >= a[k]) j--;
		while(i<j && a[i] <= a[k]) i++;
		swap(a[i], a[j]);
	}
	swap(a[k], a[i]); //swap(a[k], a[j]);
	qsort(l, i-1);
	qsort(i+1, r);
}

int main(){
	scanf("%d", &n);
	for(int i=1; i<=n; i++) scanf("%d", a+i);
	qsort(1, n);
	for(int i=1; i<=n; i++) printf("%d ", a[i]);
	return 0;
}

测试数据

输入

CPP
8
1 3 4 5 6 8 7 2

输出

CPP
1 2 3 4 5 6 7 8

复杂度及稳定性分析

时间复杂度
最佳情况(已有序): O(nlog⁡n)O(n \log n)
最坏情况(逆序): O(n2)O(n^2)
平均: O(nlog⁡n)O(n \log n)
空间复杂度
O(log⁡n)O(\log n)
稳定性
不稳定

计数排序(Counting Sort)

基本思想

对于给定的输入序列中的每一个元素 xx,确定该序列中值小于 xx 的元素的个数.利用这一信息,就可以直接将 xx 存放到最终输出序列的相应位置上.但此算法不能适用于有较大数据的排序.

步骤

  1. 找出待排序数组中的最大值和最小值
  2. 创建计数数组：长度为 max−min+1max - min + 1,初始化为0
  3. 统计每个元素出现的次数：遍历原数组,在计数数组中对应位置计数
  4. 将计数数组转换为前缀和数组：每个位置存储小于等于该索引值的元素个数
  5. 反向填充目标数组：从后往前遍历原数组,根据前缀和数组确定元素位置

代码实现

CPP
#include <iostream>
using namespace std;

void countingSort(int arr[], int n) {

    int minVal = arr[0], maxVal = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] < minVal) minVal = arr[i];
        if (arr[i] > maxVal) maxVal = arr[i];
    }
    
    int range = maxVal - minVal + 1;
    int count[range] = {0};
    
    for (int i = 0; i < n; i++) {
        count[arr[i] - minVal]++;
    }
    
    for (int i = 1; i < range; i++) {
        count[i] += count[i - 1];
    }
    
    int output[n];
    
    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i] - minVal] - 1] = arr[i];
        count[arr[i] - minVal]--;
    }
    
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

int main() {
    int n;
    
    cin >> n;
    
    int arr[n];
    
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    countingSort(arr, n);
    
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    
    return 0;
}

测试数据

输入

CPP
8
1 3 4 5 6 8 7 2

输出

CPP
1 2 3 4 5 6 7 8

复杂度及稳定性分析

下面的 kk 代表什么
kk 表示待排序数组中所有可能出现的不同整数的个数,即给定数据内((最大值−-最小值)+1+1.
时间复杂度
O(n+k)O(n+k)
空间复杂度
O(n+k)O(n+k)
稳定性
稳定

写在后面的话

后记
由于本蒟蒻才学C++没多久,这也是我写的第一篇文章,写的不是太好,请大家多多见谅 qwq.
广告及宣传
有需要的童鞋请联系:feng_ling@petalmail.com,标题请注明"广告及宣传".

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...