专栏首页大龄码农常用排序算法

常用排序算法

冒泡排序(Bubble Sort)

冒泡排序是一种极其简单的排序算法,也是我所学的第一个排序算法。它重复地走访过要排序的元素,依次比较相邻两个元素,如果他们的顺序错误就把他们调换过来,直到没有元素再需要交换,排序完成。这个算法的名字由来是因为越小(或越大)的元素会经由交换慢慢“浮”到数列的顶端。

  冒泡排序算法的运作如下:

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

  由于它的简洁,冒泡排序通常被用来对于程序设计入门的学生介绍算法的概念。冒泡排序的代码如下:

#include <stdio.h>
// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- 如果能在内部循环第一次运行时,使用一个旗标来表示有无需要交换的可能,可以把最优时间复杂度降低到O(n)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定
void Swap(int A[], int i, int j)
{
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}
void BubbleSort(int A[], int n)
{
    for (int j = 0; j < n - 1; j++)         // 每次最大元素就像气泡一样"浮"到数组的最后
    {
        for (int i = 0; i < n - 1 - j; i++) // 依次比较相邻的两个元素,使较大的那个向后移
        {
            if (A[i] > A[i + 1])            // 如果条件改成A[i] >= A[i + 1],则变为不稳定的排序算法
            {
                Swap(A, i, i + 1);
            }
        }
    }
}
int main()
{
    int A[] = { 6, 5, 3, 1, 8, 7, 2, 4 };    // 从小到大冒泡排序
    int n = sizeof(A) / sizeof(int);
    BubbleSort(A, n);
    printf("冒泡排序结果:");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
    return 0;
}

  上述代码对序列{ 6, 5, 3, 1, 8, 7, 2, 4 }进行冒泡排序的实现过程如下

  使用冒泡排序为一列数字进行排序的过程如右图所示:  

  尽管冒泡排序是最容易了解和实现的排序算法之一,但它对于少数元素之外的数列排序是很没有效率的。

选择排序(Selection Sort)

  选择排序也是一种简单直观的排序算法。它的工作原理很容易理解:初始时在序列中找到最小(大)元素,放到序列的起始位置作为已排序序列;然后,再从剩余未排序元素中继续寻找最小(大)元素,放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

  注意选择排序与冒泡排序的区别:冒泡排序通过依次交换相邻两个顺序不合法的元素位置,从而将当前最小(大)元素放到合适的位置;而选择排序每遍历一次都记住了当前最小(大)元素的位置,最后仅需一次交换操作即可将其放到合适的位置。

  选择排序的代码如下:

#include <stdio.h>
// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- O(n^2)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 不稳定
void Swap(int A[], int i, int j)
{
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}
void SelectionSort(int A[], int n)
{
    for (int i = 0; i < n - 1; i++)         // i为已排序序列的末尾
    {
        int min = i;
        for (int j = i + 1; j < n; j++)     // 未排序序列
        {
            if (A[j] < A[min])              // 找出未排序序列中的最小值
            {
                min = j;
            }
        }
        if (min != i)
        {
            Swap(A, min, i);    // 放到已排序序列的末尾,该操作很有可能把稳定性打乱,所以选择排序是不稳定的排序算法
        }
    }
}
int main()
{
    int A[] = { 8, 5, 2, 6, 9, 3, 1, 4, 0, 7 }; // 从小到大选择排序
    int n = sizeof(A) / sizeof(int);
    SelectionSort(A, n);
    printf("选择排序结果:");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
    return 0;
}

  上述代码对序列{ 8, 5, 2, 6, 9, 3, 1, 4, 0, 7 }进行选择排序的实现过程如右图  

  使用选择排序为一列数字进行排序的宏观过程:  

选择排序是不稳定的排序算法,不稳定发生在最小元素与A[i]交换的时刻。

比如序列:{ 5, 8, 5, 2, 9 },一次选择的最小元素是2,然后把2和第一个5进行交换,从而改变了两个元素5的相对次序。

插入排序(Insertion Sort)

  插入排序是一种简单直观的排序算法。它的工作原理非常类似于我们抓扑克牌

  对于未排序数据(右手抓到的牌),在已排序序列(左手已经排好序的手牌)中从后向前扫描,找到相应位置并插入。

  插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

  具体算法描述如下:

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

  插入排序的代码如下:

#include <stdio.h>
// 分类 ------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- 最坏情况为输入序列是降序排列的,此时时间复杂度O(n^2)
// 最优时间复杂度 ---- 最好情况为输入序列是升序排列的,此时时间复杂度O(n)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定
void InsertionSort(int A[], int n)
{
    for (int i = 1; i < n; i++)         // 类似抓扑克牌排序
    {
        int get = A[i];                 // 右手抓到一张扑克牌
        int j = i - 1;                  // 拿在左手上的牌总是排序好的
        while (j >= 0 && A[j] > get)    // 将抓到的牌与手牌从右向左进行比较
        {
            A[j + 1] = A[j];            // 如果该手牌比抓到的牌大,就将其右移
            j--;
        }
        A[j + 1] = get; // 直到该手牌比抓到的牌小(或二者相等),将抓到的牌插入到该手牌右边(相等元素的相对次序未变,所以插入排序是稳定的)
    }
}
int main()
{
    int A[] = { 6, 5, 3, 1, 8, 7, 2, 4 };// 从小到大插入排序
    int n = sizeof(A) / sizeof(int);
    InsertionSort(A, n);
    printf("插入排序结果:");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
    return 0;
}

  上述代码对序列{ 6, 5, 3, 1, 8, 7, 2, 4 }进行插入排序的实现过程如下

  使用插入排序为一列数字进行排序的宏观过程:  

  插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,比如量级小于千,那么插入排序还是一个不错的选择。 插入排序在工业级库中也有着广泛的应用,在STL的sort算法和stdlib的qsort算法中,都将插入排序作为快速排序的补充,用于少量元素的排序(通常为8个或以下)。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 内存可见性和原子性:Synchronized和Volatile的比较

    【尊重原创,转载请注明出处】http://blog.csdn.net/guyuealian/article/details/52525724

    traffic
  • RocketMQ报错No route info of this topic解决方案

    (由于本次使用的老项目环境,并没有整合maven一起使用,是每个每个jar的慢慢找的,所以才会导致这个缺包的问题)

    traffic
  • JAVA 集合list,Map删除元素的方法总结

    这种方式的问题在于,删除某个元素后,list的大小发生了变化,而你的索引也在变化,所以会导致你在遍历的时候漏掉某些元素。比如当你删除第1个元素后,继续根据索引访...

    traffic
  • 常用排序算法总结(1)

    朱晓霞
  • 深入理解排序算法

    [本篇博文会对常见的排序算法进行分析与总结,并会在最后提供几道相关的一线互联网企业面试/笔试题来巩固所学及帮助我们查漏补缺。项目地址:https://githu...

    sunsky
  • 桶排序及其应用

    桶排序是计数排序的扩展版本,计数排序可以看成每个桶只存储相同元素,而桶排序每个桶存储一定范围的元素,通过映射函数,将待排序数组中的元素映射到各个对应的桶中,对每...

    用户3467126
  • [图解] 桶排序

    桶排序是一种排序的思想,其实现包括计数排序和基数排序两种,冒泡排序、选择排序、插入排序、归并排序、快速排序和堆排序都是基于比较的排序,而桶排序提出了一种新的思路...

    CoderJed
  • 基础排序算法

    使用比较运算符” < ”和” > ”,将相容的序放到输入中,且除了赋值运算符外,这两种运算是仅有的允许对输入数据进行的操作,在这些条件下...

    我是一条小青蛇
  • 八大排序算法的Python实现

    本文主要介绍了常见的8大排序算法基本概念以及其Python实现方式,如果你是Java程序员,也可以看看之前我们介绍的Java程序员必须掌握的8大排序算法。

    哲洛不闹
  • 经典排序之 插入排序

    Author: bakari  Date: 2012.7.21 排序算法有很多种,每一种在不同的情况下都占有一席之地。关于排序算法我分“经典排序之”系列分别述之...

    CloudDeveloper

扫码关注云+社区

领取腾讯云代金券