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

· · 算法·理论

前言

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

目录

  1. 冒泡排序

  2. 选择排序

  3. 插入排序

  4. 希尔排序

  5. 归并排序

  6. 快速排序

  7. 计数排序

前置知识

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

冒泡排序(Bubble Sort)

基本思想

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

步骤

  1. 比较相邻的元素.如果第一个比第二个大(升序情况),就交换它们两个.

  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.这步做完后,最后的元素会是最大的数.

  3. 针对所有的元素重复以上的步骤,除了最后一个.

  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较.

代码实现

#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;
}

测试数据

输入

8
1 3 4 5 6 8 7 2

输出

1 2 3 4 5 6 7 8

复杂度及稳定性分析

时间复杂度

最佳情况(已有序): O(n)

最坏情况(逆序): O(n^2)

平均: O(n^2)

空间复杂度

稳定性

稳定

选择排序(Selection Sort)

基本思想

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

步骤

  1. 初始状态:无序区为 R[1 \dots n],有序区为空。

  2. 第 i 趟排序 (i=1,2,3…n-1) 开始时,当前有序区和无序区分别为 R[1 \dots i-1] 和 R[i \dots n] .该趟排序从当前无序区中选出关键字最小的记录 R[k] ,将它与无序区的第1个记录 R[i] 交换.

  3. 这样,有序区增加了一个记录,无序区减少了一个记录.

  4. ### 代码实现 ```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(n^2)$ >> >>最坏情况(逆序): $O(n^2)$ >> >>平均: $O(n^2)$ >> >空间复杂度 > >>$O(1)$,属于原地排序算法 > >稳定性 > >>不稳定

插入排序(Insertion Sort)

基本思想

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

步骤

  1. 从第一个元素开始,该元素可以认为已经被排序.

  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描.

  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置.

  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置.

  5. 将新元素插入到该位置后.

重复步骤2~5。

代码实现

#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;
}

测试数据

输入

8
1 3 4 5 6 8 7 2

输出

1 2 3 4 5 6 7 8

复杂度及稳定性分析

时间复杂度

最佳情况(已有序): O(n)

最坏情况(逆序): O(n^2)

平均: O(n^2)

空间复杂度

稳定性

稳定

希尔排序(Shell Sort)

基本思想

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

步骤

  1. 选择一个增量序列 t_1, t_2, ..., t_k ,其中 t_i > t_j , t_k = 1.常用增量序列有 n/2, n/4, \dots , 1 (希尔增量).

  2. 按增量序列个数 k，对序列进行 k 趟排序。

  3. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理。

代码实现

#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;
}

测试数据

输入

8
1 3 4 5 6 8 7 2

输出

1 2 3 4 5 6 7 8

复杂度及稳定性分析

时间复杂度

依赖于增量序列的选择,范围在 O(n log²n) 到 O(n²) 之间.使用希尔增量时最坏情况为 O(n²).

空间复杂度

O(1)

稳定性

不稳定

归并排序(Merge Sort)

基本思想

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

步骤

  1. 分解：将序列递归地分成两半,直到每个子序列只有一个元素(自然有序)。

  2. 解决：递归地对两个子序列进行归并排序.

  3. 合并：将两个已排序的子序列合并成一个有序序列.

代码实现

#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;
}

测试数据

输入

8
1 3 4 5 6 8 7 2

输出

1 2 3 4 5 6 7 8

复杂度及稳定性分析

时间复杂度

最佳情况(已有序): O(n \log n)

最坏情况(逆序): O(n \log n)

平均: O(n \log n)

空间复杂度

O(n)

稳定性

稳定

快速排序(Quick Sort)

基本思想

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

步骤

  1. 挑选基准值：从数列中挑出一个元素,称为“基准”.

  2. 分割：重新排序数列，所有比基准值小的元素放在基准前面,所有比基准值大的元素放在基准后面(相等的数可以到任一边.在这个分割结束之后)，对基准值的排序就已经完成.

  3. 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序.

代码实现

#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;
}

测试数据

输入

8
1 3 4 5 6 8 7 2

输出

1 2 3 4 5 6 7 8

复杂度及稳定性分析

时间复杂度

最佳情况(已有序): O(n \log n)

最坏情况(逆序): O(n^2)

平均: O(n \log n)

空间复杂度

O(\log n)

稳定性

不稳定

计数排序(Counting Sort)

基本思想

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

步骤

  1. 找出待排序数组中的最大值和最小值

  2. 创建计数数组：长度为 max - min + 1,初始化为0

  3. 统计每个元素出现的次数：遍历原数组,在计数数组中对应位置计数

  4. 将计数数组转换为前缀和数组：每个位置存储小于等于该索引值的元素个数

  5. 反向填充目标数组：从后往前遍历原数组,根据前缀和数组确定元素位置

代码实现

#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;
}

测试数据

输入

8
1 3 4 5 6 8 7 2

输出

1 2 3 4 5 6 7 8

复杂度及稳定性分析

::::info[下面的 k 代表什么]{open}

:::: >时间复杂度 > >>$O(n+k)

空间复杂度

O(n+k)

稳定性

稳定

写在后面的话

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