David Dong

David Dong

Java/C/C#/Python

Java/C/C#/Python

Dark Mode
Subscribe
Source Code
  • Home
    •
  • Archives
    •
  • Categories
    •
  • About
    •

    POST

    几种常见的排序算法

    Sep 19, 2016

    cover
    记得很多年以前，在我研究生毕业找工作那会儿，面试的时候被面试官问到过两次关于排序算法的问题。这件事至今给我的印象比较深刻，因为很少有在不同的面试过程中会被问到相同的问题。由此可见排序算法在面试中占有很大的比重，其实这也是考察程序员的一个基础。前几天在招聘的过程中又想起了这件事，觉得虽然这个问题比较基础，但是还是有必要整理总结一下的。

    大多数的人应该都能回答出冒泡排序和选择排序的算法，我想这可能是因为国内目前的教材中（比如「C语言编程基础」）这两种为例子的比较多的缘故吧。其实在后来的工作中了解到不止这两种算法，还有一些其他的算法也可以实现。当然能够回答出冒泡排序和选择排序也应该是合格的。下面我就来总结一下目前我所知道的常见的几种排序算法。

    1. 冒泡排序

    我们就从最常见的冒泡排序来说起。为了统一起见，本文的排序都是以从小到大的序列为准。文中的例子都以C语言代码编写，对python和Java的源码感兴趣的同学，可以在这里找到源码。

    冒泡排序规则是：从左到右，数组中相邻的两个元素进行比较，将较大的放到后面。
    按照这个原则，我们编写代码。

    C语言实现

    void sort_bubble(int *a, int num)
{

    int i = 0;
    int j = 0;
    int temp = 0;

    for (i = 0; i < num - 1; i++)
    {
        for (int j = 0; j < num - i - 1; j++)
        {
            if (a[j] > a[j + 1])
            {
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
        printData(a, num);
    }
}

    打印结果如下

    initial data:
17,6,19,45,1,2,23,5,4,11,3,
options:1
starting bubble sort...
6,17,19,1,2,23,5,4,11,3,45,
6,17,1,2,19,5,4,11,3,23,45,
6,1,2,17,5,4,11,3,19,23,45,
1,2,6,5,4,11,3,17,19,23,45,
1,2,5,4,6,3,11,17,19,23,45,
1,2,4,5,3,6,11,17,19,23,45,
1,2,4,3,5,6,11,17,19,23,45,
1,2,3,4,5,6,11,17,19,23,45,
1,2,3,4,5,6,11,17,19,23,45,
1,2,3,4,5,6,11,17,19,23,45,

    结果分析
    数组长度11，一共比较了10轮。第一轮比较结束后序列中最大数45从序列的最右边冒出来。第二轮比较后，所有数中第二大的那个数23就会浮到倒数第二个位置……就这样一轮一轮地比较，最后实现从小到大排序。

    轮次 比较次数 结果
    第1轮 10 6,17,19,1,2,23,5,4,11,3,45
    第2轮 9 6,17,1,2,19,5,4,11,3,23,45
    第3轮 8 6,1,2,17,5,4,11,3,19,23,45
    第4轮 7 1,2,6,5,4,11,3,17,19,23,45
    第5轮 6 1,2,5,4,6,3,11,17,19,23,45
    第6轮 5 1,2,4,5,3,6,11,17,19,23,45
    第7轮 4 1,2,4,3,5,6,11,17,19,23,45
    第8轮 3 1,2,3,4,5,6,11,17,19,23,45
    第9轮 2 1,2,3,4,5,6,11,17,19,23,45
    第10轮 1 1,2,3,4,5,6,11,17,19,23,45

    时间/空间复杂度
    由于我们要重复执行n次冒泡，每次冒泡要执行n次比较，也就是O(n^2)。 空间复杂度是O(n)。

    2. 选择排序

    选择排序规则是：从第一个位置开始比较，找出最小的，和第一个位置互换，开始下一轮。第二轮从第二个位置开始查找，然后找出剩余序列中最小的，和第二个位置互换，然后重复之前的操作，依次比较，直至所有数都排列完毕。

    C语言实现

    void sort_selection(int *a, int num)
{

    int i = 0;
    int j = 0;
    int temp = 0;
    int min;

    for (i = 0; i < num - 1; i++)
    {
        min = i;
        for (j = i + 1; j < num; j++)
        {
            if (a[j] < a[min])
            {
                min = j;
            }
        }
        temp = a[i];
        a[i] = a[min];
        a[min] = temp;
        printData(a, num);
    }
}

    打印结果

    initial data:
17,6,19,45,1,2,23,5,4,11,3,
options:2
starting selection...
1,6,19,45,17,2,23,5,4,11,3,
1,2,19,45,17,6,23,5,4,11,3,
1,2,3,45,17,6,23,5,4,11,19,
1,2,3,4,17,6,23,5,45,11,19,
1,2,3,4,5,6,23,17,45,11,19,
1,2,3,4,5,6,23,17,45,11,19,
1,2,3,4,5,6,11,17,45,23,19,
1,2,3,4,5,6,11,17,45,23,19,
1,2,3,4,5,6,11,17,19,23,45,
1,2,3,4,5,6,11,17,19,23,45,

    结果分析
    也是一共比较了10轮。第一轮比较结束后序列中最小数a[4] 和a[0]互换。第二轮从a[1]开始比较，因为a[0]已经是最小的数了，比较完成后，a[1]~a[10]中最小的数a[5]和a[1]互换。依次论推，直到把数据排列好。

    轮次 比较次数 结果
    第1轮 10 1,6,19,45,17,2,23,5,4,11,3
    第2轮 9 1,2,19,45,17,6,23,5,4,11,3
    第3轮 8 1,2,3,45,17,6,23,5,4,11,19
    第4轮 7 1,2,3,4,17,6,23,5,45,11,19
    第5轮 6 1,2,3,4,5,6,23,17,45,11,19
    第6轮 5 1,2,3,4,5,6,23,17,45,11,19
    第7轮 4 1,2,3,4,5,6,11,17,45,23,19
    第8轮 3 1,2,3,4,5,6,11,17,45,23,19
    第9轮 2 1,2,3,4,5,6,11,17,19,23,45
    第10轮 1 1,2,3,4,5,6,11,17,19,23,45

    时间/空间复杂度
    每次要找一遍最小值，最坏情况下找n次，这样的过程要执行n次，所以时间复杂度还是O(n^2)。空间复杂度是O(n)。

    3. 快速排序

    快速排序规则是：选择序列中的一个数为基准数，序列中的数逐个与之比较，小的放到它的左边，大的放大它的右边，然后再对左右区间递归执行上述步骤，直至整个序列有序。

    C语言实现

    void sort_quick(int *a, int start, int end)
{
    int i = start;
    int j = end;
    int temp = 0;
    int base = a[i];

    if (start < end)
    {
        while (i != j)
        {
            while (i < j && a[j] >= base)
                j--;

            while (i < j && a[i] <= base)
                i++;

            temp = a[i];
            a[i] = a[j];
            a[j] = temp;

            printData(a, end + 1);
        }

        a[start] = a[i];
        a[i] = base;

        sort_quick(a, start, i - 1);
        sort_quick(a, i + 1, end);
    }
}

    打印结果

    initial data:
17,6,19,45,1,2,23,5,4,11,3,
options:3
17,6,3,45,1,2,23,5,4,11,19,
17,6,3,11,1,2,23,5,4,45,19,
17,6,3,11,1,2,4,5,23,45,19,
17,6,3,11,1,2,4,5,23,45,19,
search done:5,6,3,11,1,2,4,17,23,45,19,
5,4,3,11,1,2,6,
5,4,3,2,1,11,6,
5,4,3,2,1,11,6,
search done:1,4,3,2,5,11,6,
1,4,3,2,
search done:1,4,3,2,
1,4,3,2,
search done:1,2,3,4,
1,2,3,
search done:1,2,3,
1,2,3,4,5,11,6,
search done:1,2,3,4,5,6,11,
1,2,3,4,5,6,11,17,23,19,45,
1,2,3,4,5,6,11,17,23,19,45,
search done:1,2,3,4,5,6,11,17,19,23,45,
after sort, data:
1,2,3,4,5,6,11,17,19,23,45,

    结果分析
    以17(a[0])做为基准数，先从序列尾部（右边）开始比较，大家可以思考一下为什么要先从右边开始，如果从左边开始会出现什么问题？ 右边第一个数字3(a[10])小于基准数，因此需要调换位置（需要调换到的目的位置要从头部开始查找），尾部的比较停止在这个位置，然后从头部开始比较（左边），寻找大于基准数的元素的位置，找到该位置后与刚才的元素3对调。我们看到找到的是元素19（a[2]）,将a[2]与a[10]对调。执行完这一步后序列元素如打印结果中第一行所示。

    序列 元素
    初始序列 17,6,19,45,1,2,23,5,4,11,3
    第一次交换后 17,6,3,45,1,2,23,5,4,11,19

    然后从尾部接着查找下一个小于基准数的元素，重复刚才的步骤,直到头尾部相遇为止。经过这一轮排序后，整个序列已经按照基准数分为了两组（如下），左边的小于基准数17,右边的大于基准数。最后将最后相遇的位置与a[0]对调。

    序列 元素
    初始序列 17,6,19,45,1,2,23,5,4,11,3
    第一轮交换后 5,6,3,11,1,2,4,17,23,45,19

    然后对左右两组分别递归调用排序，直到所有的数排列有序为止。

    时间/空间复杂度

    4. 插入排序

    插入排序规则是：对于每个未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

    C语言实现

    void sort_insert(int *a, int num)
{
    int i, j = 0;
    int temp;

    for (i = 1; i < num; i++)
    {
        if (a[i] < a[i - 1])
        {
            temp = a[i];
            for (j = i; j >= 0; j--)
            {
                if (j > 0 && a[j - 1] > temp)
                {
                    a[j] = a[j - 1];
                }
                else
                {
                    a[j] = temp;
                    break;
                }
            }
        }
        printf("search done:");
        printData(a,num);
    }
}

    打印结果

    initial data:
17,6,19,45,1,2,23,5,4,11,3,
options:4
starting insert sort...
search done:6,17,19,45,1,2,23,5,4,11,3,
search done:6,17,19,45,1,2,23,5,4,11,3,
search done:6,17,19,45,1,2,23,5,4,11,3,
search done:1,6,17,19,45,2,23,5,4,11,3,
search done:1,2,6,17,19,45,23,5,4,11,3,
search done:1,2,6,17,19,23,45,5,4,11,3,
search done:1,2,5,6,17,19,23,45,4,11,3,
search done:1,2,4,5,6,17,19,23,45,11,3,
search done:1,2,4,5,6,11,17,19,23,45,3,
search done:1,2,3,4,5,6,11,17,19,23,45,
after sort, data:
1,2,3,4,5,6,11,17,19,23,45,

    结果分析
    从a[0]开始，逐个与下个相邻元素比较，如果a[i]大于a[i+1]，那么就把a[i+1]放到a[i]之前的序列中进行排序。如第三轮中交换后元素1被交换到序列6,17,19,45中进行排序。依次重复，直到所有数都有序排列为止。

    序列 元素
    初始序列 6,17,19,45,1,2,23,5,4,11,3
    交换后 1,6,17,19,45,2,23,5,4,11,3

    时间/空间复杂度
    因为要选择n次，而且插入时最坏要比较n次，所以时间复杂度同样是O(n^2)。空间复杂度是O(n)。

    5. Shell排序

    Shell排序规则是：分组插入排序, 将数组按照一定步长分成几个子数组,对子数组（列）分别进行插入排序，重复这过程，不过每次用更小的步长-更长的列来进行。

    C语言实现

    void sort_shell(int *a, int num){

    int i,j = 0;
    int temp = 0;
    int scale = round(num);
    while(scale > 0){

        for(i=scale;i<num;i++){
            temp = a[i];
            j = i;
            while ( j >= scale && a[j-scale] > temp ){
                a[j] = a[j-scale];
                j = j - scale;
            }
            a[j] = temp;
        }
        scale = round(scale/2);
        printf("search done:");
        printData(a,num);
    }
}

    打印结果

    initial data:
17,6,19,45,1,2,23,5,4,11,3,
options:5
starting shell sort...
search done:17,6,19,45,1,2,23,5,4,11,3,
search done:2,6,5,4,1,3,23,19,45,11,17,
search done:1,3,2,4,5,6,17,11,23,19,45,
search done:1,2,3,4,5,6,11,17,19,23,45,
after sort, data:
1,2,3,4,5,6,11,17,19,23,45,

    结果分析
    以步长为5开始进行排序，可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：

    17|  6| 19| 45|  1
 2| 23|  5|  4| 11
 3|

    对这5列进行插入排序后，序列变为

     2|  6|  5|  4|  1
 3| 23| 19| 45| 11
17|

    将这5列连接在一起的原始序列为2,6,5,4,1,3,23,19,45,11,17,然后再对该序列以步长2排序。方法相同，排序完成后的数列为1,3,2,4,5,6,17,11,23,19,45。重复该步骤直到步长为1。

    时间/空间复杂度
    希尔排序的时间复杂度受步长的影响。

    文章目录


    Others

    相关文章

    继续阅读

    前一章
    聊一聊开源协议那些事
    后一章
    Use bcdedit.exe in Windows




    © 2012-2021 David Dong. All rights reserved.