第五课 基础排序总结

作者： 作者的头像   huolong , 时间：2023-01-11 20:04:30 , 所有人可见, 阅读  21

排序算法分类：

常见的排序算法主要可以分为两类：

基于比较的排序：冒泡排序、选择排序、插入排序、快速排序、Shell排序、归并排序、堆积排序，其最坏情况下时间复杂度的不可能突破 $O(nlogn)$

简略证明：

对于 $n$ 个元素的序列，总共有 $n!$ 中排列方式，只有一种是我们最终需要的结果（假设没有重复元素）。基于比较排序每进行一次比较后假设我们得到$A[i] \lt A[j]$，那么我们可以将$n!$中方案中所有$A[i] \gt A[j]$的排列都删除，最好的情况下，恰好$A[i] \lt A[j]$的排列组合方式和$A[i]>A[j]$的排列组合方式具有相同的数量，这样无论比较结果如何，我们都可以去除一半的排列组合方式。 总共有$n!$中方案，每次最多能够减去一半的方案，那么经过多少次比较能够使得只剩下一种方案呢？ 由 $2^k>=n!$，得到 $k=log_2n!=log(n)+log(n-1)+…+log(2)+log(1)～O(nlogn)$

非基于比较的排序：基数排序、计数排序、桶排序。

基础排序

  • 冒泡
  • 选择
  • 插入

不同排序算法

下述所有算法都以升序为例，数组下标范围为$A[0,n−1]$

冒泡排序算法:

冒泡排序算法每次交换相邻的两个数，如果左边的数小于右边的数，那么交换这两个元素，经过第一趟交换后，最大的元素肯定在最右边的位置上，然后对前$n−1$个元素重复上述操作。

$i$指针控制每一趟交换的右边界，$j$指针控制每一趟交换中当前索引到的位置。

void BubbleSort(int n)
{
    for(int i = n - 1 ; i > 0; i --) //只要n-1趟
    {
        for(int j = 0 ; j < i ; j ++)
        {   //比较相邻元素，是否需要交换
            if(A[j] > A[j + 1])
                swap(A[j],A[j + 1]);
        }
    }
}

下面对其进行优化，设置一个标志，如果这一趟发生了交换，则为true，否则为false。明显如果有一趟没有发生交换，说明排序已经完成。

#include<iostream>
#include<algorithm>
using namespace std;

int A[5] = {2,1,3,4,5} ;
void BubbleSort(int n)
{
    bool is_f = true;//要排序
    int k = n; 
    while(is_f){
        is_f = false;
        for(int i=0; i<k-1;i++){
            cout << "比较哈 " << " "; //4 +3 第一趟排好后，第二趟进行检查 
            if(A[i] > A[i+1])  {
                cout << "交换哈 " ;//交换1次 逆序对的数量
                is_f = true;
                swap(A[i], A[i+1]); 
            }
        }
        k --;
    } 

}

void BubbleSort1(int n)
{
    for(int i = n - 1 ; i > 0; i --) //只要n-1趟
    {
        for(int j = 0 ; j < i ; j ++)
        {   //比较相邻元素，是否需要交换
            cout << "比较1 " ; // 4+3+2+1 都要比较 
            if(A[j] > A[j + 1]){
                cout << "交换1 " ; //交换1次 逆序对的数量 
                swap(A[j],A[j + 1]);
            }

        }
    }
}

int main() {
    BubbleSort(5);
    for(int i=0; i<5; i++){
        cout << A[i] << " ";
    }
    return 0;
}
选择排序：

选择排序算法每次在未排序的数字中选择最大的那个数字放在数组末尾。

i指针控制当前未排序数字的右边界，也是当前未排序数字中最大的元素应该放的位置，我们使用idx代表当前最大元素的下标。每次在比较的时候我们只更新下标，避免频繁的数组元素交换。

void SelectSort(int n)
{
    for(int i = 0; i < n ; i ++)
    {
        int k = i;
        for(int j = i ; j <n ; j ++)
        {
            if(A[j] < A[k])
                k = j;
        }
        if(k != i) swap(A[i],A[k]);
    }
}

插入排序： 插入排序每次排序第$k$个元素，此时前$k - 1$个元素已经从小到大排好序了，我们从已经排序好的元素从后往前遍历，找到第一个小于当前元素的位置，那么当前元素就应该插在当前元素的后面。

void InsertSort(int n)
{
    for(int i = 1 ; i < n ; i ++)
    {
        int k = A[i];
        int j = i-1;
        while(j>=0 && A[j] > k){
            A[j+1] = A[j];
            j--;
        }
       j++;
       A[j] = k;
    }
}

计数排序

  • 简单版 简单版计数排序是不稳定的。
#include<iostream>
using namespace std;
int a[100005];

int main(){

    int n; cin >> n;
    for(int i=0; i<n; i++){
        int x; cin >> x;
        a[x]++;
    }

    for(int i=0; i<100005; i++){
        if(a[i] >0){
            for(int j=0; j<a[i]; j++){
                cout << i<<' ';
            }
        }
    }

    return 0;
}
  • 稳定版
#include<iostream>
#include<cstdio>
using namespace std;
const int N =100005;
int a[N], sorted[N];
int count[200];
int n;
void counting_sort()
{
    for (int i = 0; i < n; i ++ ) count[a[i]] ++ ;
    for (int i = 1; i <200; i ++ ) count[i] += count[i-1];
    //for(int i=0; i<200; i++) cout << count[i] << ' ';
    for (int i = n-1; i >= 0; i -- )
    {
        sorted[count[a[i]]-1] = a[i];
        count[a[i]] -- ;
    }
    for (int i = 0; i < n; i ++ ) a[i] = sorted[i];
}
int main(){
    cin >> n;
    for(int i=0; i<n; i++) cin >> a[i];
    counting_sort();
    for(int i=0; i<n; i++) cout << a[i] << " ";
    return 0;
}

库函数

  1. sort和stable_sort

stable adj. 稳定的;稳固的;牢固的;稳重的;沉稳的;持重的;(化学状态或原子状态)稳定的

那stable_sort就是一个稳定的sort喽，所以stable_sort的用法与sort也基本相同，这里不再赘述 接下来，我们再来回顾一下什么是稳定排序，什么是不稳定排序：

稳定排序：排序前后两个相等的数相对位置不变，则算法稳定 非稳定排序：排序前后两个相等的数相对位置发生了变化，则算法不稳定

常用的排序算法中，根据排序算法的实现原理 ，我们可以以稳定性对它们分类：

稳定排序：冒泡排序，插入排序，归并排序（stable_sort的基本原理），基数排序 不稳定排序：快速排序（sort的基本原理），选择排序，shell希尔排序，堆排序

比如对于1 2 3 4 2这样一组数据，当我们使用不稳定排序算法进行排序时，不稳定排序算法不能保证两个2的先后顺序是否与输入时得顺序相同，虽然两个函数排序后的结果都是1 2 2 3 4，但两个2的先后顺序却不一定相同，这一问题在一些特殊情况下会对程序的最终结果产生一些影响，但如果只是简单的进行数字的排序，那么稳定性将毫无意义。 在时间复杂度方面，由于stable_sort原理是归并排序而sort是快速排序，所以stable_sort可能会稍稍慢那么一内内，但相差无几，所以基本不需要担心超时问题。

sort和stable_sort举例：

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

struct info{
    int no;
    int x;
} A[50];

int main() {

    int n;
    cin >> n ;

    for(int i=0; i<n; i++){
        int no; cin >>no;
        int x;  cin >> x;
        A[i].no = no;
        A[i].x = x;
    }

    /*
    stable_sort(A, A+n, [](info a, info b){
        return a.x > b.x ;
    }) ;
    */

    sort(A, A+n, [](info a, info b){
        return a.x > b.x ;
    }) ;

    for(int i=0; i<n; i++){
        cout << "no: " << A[i].no << " " << "x:" << A[i].x << endl;
    }
    return 0;
}
/*
17
1 99
2 95
3 95
4 97
5 98
6 95
7 96
8 96
9 97
10 99
11 98
12 100
13 98
14 99
15 97
16 100
17 97
*/
  1. sort自定义
  2. sort匿名

int a[5] = {2,1,3,4,5} ;
int cmp(int a, int b){
    return a > b;
}
int main() {
    sort(a, a+5) ;//默认从小到大 
    sort(a, a+5, cmp);// 自定义比较 从大到小 
    sort(a, a+5, [](int a, int b){
        return a > b;
    }); //匿名函数方式

    for(int i=0; i<5; i++) cout << a[i] << " "; 
    return 0;
}

稳定性

稳定性的概念

什么是排序的稳定性：如果元素大小相同，排序后的相对位置不变。

不稳定的有：

堆排序 快速排序 选择排序

稳定的有：

基数排序 冒泡排序 插入排序 归并排序 计数排序 桶排序

选择排序不稳定的原因

在每次将最小的元素拿到最前面和未排序的序列的第一个元素进行交换的时候发生了对原序列的破坏，失去了稳定性。 比如： 1 5 5 3

基础排序小结
排序方法 平均时间复杂度 最坏时间复杂度 稳定性 方式
冒泡排序 $O(n^2)$ $O(n^2)$ 稳定 基于比较
选择排序 $O(n^2)$ $O(n^2)$ 不稳定 基于比较
插入排序 $O(n^2)$ $O(n^2)$ 稳定 基于比较
计数排序 $O(n)$ $O(n)$ 稳定 不需要比较

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com