Jackie's Blog
十大经典排序算法
Jackie
  2024-03-07   2025-05-04  4.4k 字  18 分钟

十大经典排序算法

可视化数据结构和算法

各个算法的时空复杂度及稳定性

  • 稳定：如果a原本在b前面，且a=b，排序之后a仍然在b的前面
  • 不稳定：如果a原本在b的前面，且a=b，排序之后a可能会出现在b的后面

image

村里有两只做事很稳的动物：插帽龟和统计鸡。插帽龟喜欢去插人家堆起来的帽子，统计鸡喜欢做加减乘除。但有天插帽龟挑选帽子插的时候，恩姓长老看见就慌了，恩老大喊：“快点归还给堆”

image

一、插入排序（Insertion Sort）

原理

这里主要针对直接插入排序。将元素与已经排序的有序序列比较，找到对应的位置插入

步骤

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

动画演示

image

代码实现

CPP 
void insert_sort()
{
    for (int i = 1; i < n; i ++ )
    {
        int x = a[i];
        int j = i-1;

        while (j >= 0 && x < a[j])
        {
            a[j+1] = a[j];
            j -- ;
        }
        a[j+1] = x;
    }
}

二、希尔排序（Shell Sort）

原理

希尔排序又叫缩小增量排序，也是一种插入排序方法（通常快于直接插入法），具体做法是将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序

步骤

  • 1.先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作
  • 2.当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成

对于增量的选定无一定论，但最后一个增量必须等于1，也就是说，每趟后一个增量是前一个增量的1/2

动画演示

image

代码实现

CPP 
void shell_sort()
{
    for (int gap = n >> 1; gap; gap >>= 1)
    {
        for (int i = gap; i < n; i ++ )
        {
            int x = a[i];
            int j;
            for (j = i; j >= gap && a[j-gap] > x; j -= gap)
                a[j] = a[j-gap];
            a[j] = x;
        }
    }
}

三、冒泡排序（Bubble Sort）

原理

通过无序区中相邻元素关键字间的比较和位置的交换，使关键字最小的元素像气泡一样浮到最顶部；接着对剩下的元素排序，使得第二小的元素到达顶部，同样的方法直到所有元素排序完成

步骤

  1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数
  3. 针对所有的元素重复步骤1~2，除了最后一个元素，直到排序完成

动画演示

image

代码实现

CPP 
void bubble_sort()
{
    for (int i = n-1; i >= 1; i -- )
    {
        bool flag = true;
        for (int j = 1; j <= i; j ++ )
            if (a[j-1] > a[j])
            {
                swap(a[j-1], a[j]);
                flag = false;
            }
        if (flag) return;
    }
}

四、快速排序（Quick Sort）

原理

一般选择将待排序序列分为两个序列，正中间的那个数作为关键字，然后两个指针一个从头到关键字遍历，遇到大于（小于）关键字的元素就停下来，另一个指针从尾到关键字遍历，遇到小于（大于）关键字的元素停下来，交换两个指针的元素完成排序；将序列递归分治按照前面的原理排序，直到序列有序

步骤

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

  1. 选取基准元素（pivot）
  2. 划分，根据选取的pivot将数组划分成小于pivot的部分和大于pivot的部分
  3. 递归求解小于pivot和大于pivot的部分

基准元素可以选择第一个元素或者最后一个元素即Lomuto Partition Scheme，但是这样划分成两部分的时候有一部分是空的，这样可能造成死循环；从中间划分可以保证两部分都不为空，即Hoare Partition Scheme

动画演示

image

代码实现

CPP 
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
  • 快速排序的边界问题

快排属于分治算法，最怕的就是n分成0和n，或n分成n和0，导致死循环

  1. 以j为划分时，x不能选q[r]（若以i为划分，则x不能选q[l]）

    假设x=q[r]

    关键句子quick_sort(q,l,j),quick_sort(q,j+1,r)
    由于j的最小值是l，所以q[j+1…r]不会造成无限划分

但q[l…j]（即quick_sort(q,l,j)）却可能造成无限划分，因为j可能为r

举例来说，若x选为q[r]，数组中q[l…r-1]<x，

那么这一轮循环结束时i=r,j=r，显然会造成无限划分

  1. do i++;while q[i]<x和do j–;whileq[j]>x不能用q[i]<=x和q[j]>=x

假设q[l…r]全相等

则执行完do i++;while(q[i]<=x);之后，i会自增到r+1

然后继续执行q[i]<=x判断条件，造成数组下标越界但这貌似不会报错但这貌似不会报错

并且如果之后的q[i]<=x此时i>r此时i>r条件也不幸成立，

就会造成一直循环下去亲身实验亲身实验，造成内存超限MemoryLimitExceeded

  1. if(i<j)swap(q[i],q[j])能否使用i<=j

可以使用if(i<=j)swap(q[i],q[j])
因为i=j时，交换一下q[i]，q[j]无影响，因为马上就会跳出循环了

  1. 最后一句能否改用quick_sort q,l,j−1,quick_sort q,j,r作为划分用i做划分时也是同样的道理，用i做划分时也是同样的道理，

    不能根据之前的证明，最后一轮循环可以得到这些结论

    j<=i和q[l…i-1]<=x,q[i]>=x和q[j+1…r]>=x,q[j]<=x

    所以，q[l…j-1]<=x是显然成立的，

    但quick_sort(q,j,r)中的q[j]却是q[j]<=x，这不符合快排的要求

    另外一点，注意quick_sort(q,l,j-1),quick_sort(q,j,r)可能会造成无限划分

    当x选为q[l]时会造成无限划分，报错为MLE，

    如果手动改为x=q[r]，可以避免无限划分

    但是上面所说的q[j]<=x的问题依然不能解决，这会造成WA WrongAnswer

  2. j的取值范围为[l…r-1]

    证明：

    假设j最终的值为r，说明只有一轮循环（两轮的话j至少会自减两次）

    说明q[r]<=x因为要跳出do−while循环因为要跳出do-while循环

    说明i>=r（while循环的结束条件），i为r或r+1必不可能成立必不可能成立

    说明i自增到了r，说明q[r]>=x和q[l…r-1]<x，

    得出q[r]=x和q[l…r-1]<x的结论，但这与x=q[l+r>>1]矛盾

    反证法得出j<r

    假设j可能小于l说明q[l…r]>x，矛盾

    反证法得出j>=l

所以j的取值范围为[l…r-1]，不会造成无限划分和数组越界。

五、选择排序（Selection Sort）

原理

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

步骤

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

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

动画演示

image

代码实现

CPP 
void select_sort()
{
    for (int i = 0; i < n; i ++ )
    {
        int k = i;
        for (int j = i+1; j < n; j ++ )
        {
            if (a[j] < a[k])
                k = j;
        }
        swap(a[i], a[k]);
    }
}

六、堆排序（Heap Sort）

原理

堆是一种特殊的树形数据结构，即完全二叉树。堆分为大根堆和小根堆，大根堆为根节点的值大于两个子节点的值；小根堆为根节点的值小于两个子节点的值，同时根节点的两个子树也分别是一个堆

image

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：子结点的键值或索引总是小于（或者大于）它的父节点

步骤

  1. 构建堆：将待排序序列构建成一个堆H[0…n-1]，从最后一个非叶子结点开始，从左至右，从下至上进行调整。根据升序或降序需求选择大顶堆或小顶堆，此时的堆顶元素，为最大或者最小元素
  2. 把堆顶元素和堆尾元素互换，调整堆，重新使堆有序，此时堆顶元素为第二大元素
  3. 重复以上步骤，直到堆变空

动画演示

image

代码实现

CPP 
void down(int u)
{
    int t = u;
    if (u<<1 <= n && h[u<<1] < h[t]) t = u<<1;
    if ((u<<1|1) <= n && h[u<<1|1] < h[t]) t = u<<1|1;
    if (u != t)
    {
        swap(h[u], h[t]);
        down(t);
    }
}

int main()
{
    for (int i = 1; i <= n; i ++ ) cin >> h[i];
    for (int i = n/2; i; i -- ) down(i);
    while (true)
    {
        if (!n) break;
        cout << h[1] << ' ';
        h[1] = h[n];
        n -- ;
        down(1);
    }
    return 0;
}

七、归并排序（Merge Sort）

原理

该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2路归并

步骤

  1. 把长度为n的输入序列分成两个长度为n/2的子序列
  2. 对这两个子序列分别采用归并排序
  3. 将两个排序好的子序列合并成一个最终的排序序列

动画演示

image

代码实现

CPP 
void merge_sort(int q[], int l, int r)
{
    //递归的终止情况
    if(l >= r) return;

    //第一步：分成子问题
    int mid = l + r >> 1;

    //第二步：递归处理子问题
    merge_sort(q, l, mid ), merge_sort(q, mid + 1, r);

    //第三步：合并子问题
    int k = 0, i = l, j = mid + 1, tmp[r - l + 1];
    while(i <= mid && j <= r)
        if(q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    while(i <= mid) tmp[k++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];

    for(k = 0, i = l; i <= r; k++, i++) q[i] = tmp[k];
}

tmp保存的是q[l…mid],q[mid+1…r]中从小到大排序的所有数

证明（第一个while循环）

循环不变式：tmp[0…k-1]保存上述俩数组中从小到大排序的最小k个数

1.初始

k=0,tmp[0…k-1]为空，显然成立

2.保持

假设某轮循环开始之前，循环不变式成立

若q[i]<=q[j],则tmp[k]=q[i]

其中q[i]<=q[i+1…mid],q[i]<=q[j]<=q[j+1…r]

∴q[i]是剩下的所有数中最小的一个

当q[i]>q[j]时，同理可以得到tmp[k]=q[j]是剩下数中最小的一个

∴tmp[k]是剩下数中最小的一个

∴k自增之后，下轮循环开始之前，tmp[0…k-1]保存从小到大排序的最小k个数

3.终止

i>mid或j>r

则q[l…mid]和q[mid+1…r]其中一个数组的数都已遍历

tmp[0…k-1]保存从小到大排序的最小k个数

八、基数排序（Radix Sort）

原理

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前

步骤

  1. 取得数组中的最大数，并取得位数
  2. arr为原始数组，从最低位开始取每个位组成radix数组
  3. 对radix进行计数排序（利用计数排序适用于小范围数的特点）

动画演示

image

代码实现

CPP 
int maxbit()
{
    int maxv = a[0];
    for (int i = 1; i < n; i ++ )
        if (maxv < a[i])
            maxv = a[i];
    int cnt = 1;
    while (maxv >= 10) maxv /= 10, cnt ++ ;

    return cnt;
}
void radixsort()
{
    int t = maxbit();
    int radix = 1;

    for (int i = 1; i <= t; i ++ )
    {
        for (int j = 0; j < 10; j ++ ) count[j] = 0;
        for (int j = 0; j < n; j ++ )
        {
            int k = (a[j] / radix) % 10;
            count[k] ++ ;
        }
        for (int j = 1; j < 10; j ++ ) count[j] += count[j-1];
        for (int j = n-1; j >= 0; j -- )
        {
            int k = (a[j] / radix) % 10;
            temp[count[k]-1] = a[j];
            count[k] -- ;
        }
        for (int j = 0; j < n; j ++ ) a[j] = temp[j];
        radix *= 10;
    }

}

九、计数排序（Counting Sort）

原理

核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数

步骤

  1. 找出待排序的数组中最大和最小的元素
  2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
  3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
  4. 反向填充目标数组：将每个元素i放在新数组的第Ci项，每放一个元素就将Ci减去1

动画演示

image

代码实现

CPP 
void counting_sort()
{
    int sorted[N];
    int maxv = a[0];
    for (int i = 1; i < n; i ++ )
        if (maxv < a[i])
            maxv = a[i];
    int count[maxv+1];
    for (int i = 0; i < n; i ++ ) count[a[i]] ++ ;
    for (int i = 1; i <= maxv; i ++ ) count[i] += count[i-1];
    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];
}

十、桶排序（Bucket Sort）

原理

遍历原始序列确定最大值maxval和最小值minval，并确定桶的个数n，然后将待排序集合中处于同一个值域的元素存入同一个桶中，在桶内使用各种现有的算法进行排序；最后按照从小到大的顺序依次收集桶中的每一个元素，即为最终结果

步骤

  1. 设置一个定量的数组当作空桶
  2. 遍历输入数据，并且把数据一个一个放到对应的桶里去
  3. 对每个不是空的桶进行排序
  4. 从不是空的桶里把排好序的数据拼接起来

桶排序是一种用空间换取时间的排序。桶的个数和大小都是我们人为设置的，而每个桶又要避免空桶的情况，所以我们在使用桶排序的时候即需要对待排序数列要求偏均匀，又要要求桶的设计兼顾效率和空间；数要相对均匀分布，桶的个数也要合理设计。在设计桶排序时，需要知道输入数据的上界和下界

动画演示

image

代码实现

CPP 
//桶排序 
void BucketSort(int a[], int n){
    int minval = a[0], maxval = a[0];
    for(int i = 0; i < n; i ++){//寻找原序列数组元素的最大值和最小值 
        minval = min(minval, a[i]);
        maxval = max(maxval, a[i]);
    }

    int bnum = 10;//桶中元素个数 
    int m = (maxval - minval) / bnum + 1;//桶的个数 
    vector< vector<int> > bucket(m);

    //收集,将元素入相应的桶中. 减偏移量是为了将元素映射到更小的区间内,省内存 
    for(int i = 0; i < n; i ++) bucket[(a[i] - minval) / bnum].push_back(a[i]);

    //将桶内元素排序 
    for(int i = 0; i < m; i ++) sort(bucket.begin(), bucket.end());

    //收集, 将各个桶中的元素收集到一起 
    for(int i = 0, k = 0; i < m; i ++){
        for(int j = 0; j < bucket[i].size(); j ++){
            data[k ++] = bucket[i][j];
        }
    }
}
 评论
评论插件加载失败
正在加载评论插件
  1. 十大经典排序算法
  2. 各个算法的时空复杂度及稳定性
  3. 一、插入排序（Insertion Sort）
    1. 原理
    2. 步骤
    3. 动画演示
    4. 代码实现
  4. 二、希尔排序（Shell Sort）
    1. 原理
    2. 步骤
    3. 动画演示
    4. 代码实现
  5. 三、冒泡排序（Bubble Sort）
    1. 原理
    2. 步骤
    3. 动画演示
    4. 代码实现
  6. 四、快速排序（Quick Sort）
    1. 原理
    2. 步骤
    3. 动画演示
    4. 代码实现
  7. 五、选择排序（Selection Sort）
    1. 原理
    2. 步骤
    3. 动画演示
    4. 代码实现
  8. 六、堆排序（Heap Sort）
    1. 原理
    2. 步骤
    3. 动画演示
    4. 代码实现
  9. 七、归并排序（Merge Sort）
    1. 原理
    2. 步骤
    3. 动画演示
    4. 代码实现
  10. 八、基数排序（Radix Sort）
    1. 原理
    2. 步骤
    3. 动画演示
    4. 代码实现
  11. 九、计数排序（Counting Sort）
    1. 原理
    2. 步骤
    3. 动画演示
    4. 代码实现
  12. 十、桶排序（Bucket Sort）
    1. 原理
    2. 步骤
    3. 动画演示
    4. 代码实现
  1. 十大经典排序算法
  2. 各个算法的时空复杂度及稳定性
  3. 一、插入排序（Insertion Sort）
    1. 原理
    2. 步骤
    3. 动画演示
    4. 代码实现
  4. 二、希尔排序（Shell Sort）
    1. 原理
    2. 步骤
    3. 动画演示
    4. 代码实现
  5. 三、冒泡排序（Bubble Sort）
    1. 原理
    2. 步骤
    3. 动画演示
    4. 代码实现
  6. 四、快速排序（Quick Sort）
    1. 原理
    2. 步骤
    3. 动画演示
    4. 代码实现
  7. 五、选择排序（Selection Sort）
    1. 原理
    2. 步骤
    3. 动画演示
    4. 代码实现
  8. 六、堆排序（Heap Sort）
    1. 原理
    2. 步骤
    3. 动画演示
    4. 代码实现
  9. 七、归并排序（Merge Sort）
    1. 原理
    2. 步骤
    3. 动画演示
    4. 代码实现
  10. 八、基数排序（Radix Sort）
    1. 原理
    2. 步骤
    3. 动画演示
    4. 代码实现
  11. 九、计数排序（Counting Sort）
    1. 原理
    2. 步骤
    3. 动画演示
    4. 代码实现
  12. 十、桶排序（Bucket Sort）
    1. 原理
    2. 步骤
    3. 动画演示
    4. 代码实现