桶排序、冒泡排序、选择排序、快速排序回顾

原 作者 胡佳露 | 发表于 | 分类于 2016级

桶排序

  1. 第一次了解桶排序的时候，是在C语言课本的一个题目。题目大概意思是要将三万个学生的成绩进行排名，分数从0分到100分。桶排序的时间复杂度时O(M+N)。所以就可以申请一个大小为100的为int类型的数组，然后将数组初始化为0，再将数组的下标看作为分数，把数组元素中存储的数值对应着获得该分数的人数，这样分数就自己在数组中有了排名，最后再用循环依次输出，只是输出的时候要看该分数有多少人获得，就重复输出多少次。

  2. 实现代码如下


#include<stdio.h>
int main()
{
    int score;
    int a[100];

    /*初始化数组 */
    for(int i=0; i<100; i++)
    {
        a[i] = 0;
    }

    /*输入学生成绩，加入有十个人的成绩*/
    for(int i=0; i<10; i++)
    {
        scanf("%d",&score);
        a[score]++;
    }

    for(int i=0; i<100; i++)
    {
        if(a[i]!=0)
        {
            for(int j=0; j<a[i]; j++)
            {
                printf("%d ",i);
            }
        }
    }
    printf("\n");
    return 0;
}

总结:
桶排序是最快最简单的排序，时间复杂度仅仅是O(m+n),但是桶排序很浪费空间，并且有局限性（比如只能输出整数，小数的话就不能使用桶排序）

冒泡排序

  1. 冒泡排序的基本思想就是比较两个相邻的元素，如果顺序错误就交换过来。假如有10个数字需要进行排序，那么大循环就要排n-1次（因为每次只能确定将一个数字归位）所以小循环要根据归位后的数字再进行相邻比较，就要比较n-1-i次。时间复杂度为O(n^2)。代码核心部分是两重循环。

  2. 代码

#include<stdio.h>
int main()
{
int t;
    int a[10];
    for(int i=0; i<10; i++)
    {
        scanf("%d",&a[i]);
    }
    int n = 10;
    /*冒泡排序*/

    for(int i=0; i<n-1; i++)
    {
        for(int j=0; j<n-i-1; j++)
        {
            if(a[j] > a[j+1])
            {
                t = a[j];
                a[j] = a[j+1];
                a[j+1] = t;
            }
        }
    }

    for(int i=0; i<n; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

总结：
冒泡排序每一大趟只能归位一个数，所以有n个数字的时候，需要进行(n-1)个数字进行归位。时间复杂度为O(N^2)。

选择排序

  1. 选择排序的原理是：首先在未排序的序列里找到最小(大)元素，放到序列的首端，再从剩余元素中找到最小(大)的元素，放到序列的尾端。依次循环，直到排序完成。

    选择排序的交换操作介于 0 和 (n - 1） 次之间。选择排序的比较操作为 n (n - 1） / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1） 次之间。
    比较次数O(n^2），比较次数与关键字的初始状态无关，总的比较次数N=(n-1）+(n-2）+…+1=n*(n-1）/2。交换次数O(n），最好情况是，已经有序，交换0次；最坏情况交换n-1次，逆序交换n/2次。交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。

  2. 代码


#include<stdio.h>
int main()
{
    int a[10];
int n,min,t;
    scanf("%d",&n);
    for(int i=0; i<n; i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=0; i<n-1; i++)
    {
        min = i;
        for(int j=i+1; j<n; j++)
        {
            if(a[j] < a[min])
            {
                min = j;
            }
        }
        if(min != i)
        {
            t = a[min];
            a[min] = a[i];
            a[i] = t;
        }
    }

    for(int i=0; i<n; i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
}

总结：
选择排序的交换次数比冒泡更少，所以相比冒泡时间更快。

快速排序

  1. 快速排序之前数据结构上过，但是没有实际上手代码。快速排序的话，比较跨度更大，相比冒泡更快。快速排序需要找一个基数，然后从一堆数据的前和后，分别检索，将比基数小的数字放在左边，比基数大的放在右边（若果是从小排到大的话）。相比冒泡排序，快速排序每次交换是跳跃式的，而冒泡只是相邻两个数字比较。平均时间复杂度为O(NlogN)。快速排序的思想是建立在二分法上的。
  2. 假如排序数列为 6 23 45 98 7 10，那么第一个数字为基数，基数就是6，然后从两端开始探测，先从10开始往左寻找小于6的数字，直到找到为止，再从6开始往右边探测，找到比6大的数字，然后进行交换，直到从左到右探测的标志点和从右向左的标志点相遇的时候，第一轮探测才结束，然后第二轮的时候，以6为分界点，将数列一分为二再同时进行第二轮探测，直到所有的数字都归位，排序结束。
  3. 代码

#include<stdio.h>
int a[1000];
void quicksort(int left, int right)
{
    /*递归结束*/
    if(left > right)
    {
        return;
    }
    int temp,t,i,j;
    temp = a[left];
    i = left;
    j = right;
    while(i != j)
    {
        //从最右边开始，与基数相比，要找出比基数小的，排在基数的左边，若比基数大，继续往左边检索
        while(a[j] >= temp && i < j)
        {
            j--;
        }
        //j检索结束后，i再开始检索比基数大的数字，比基数大的数字排在基数右边，若比基数小，继续向右边检索
        while(a[i] <= temp && i < j)
        {
            i++;
        }
        if(i < j)
        {
            t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }

    /*当i与j相遇的时机，基数归位结束，此时要交换基数的位置,temp相当于中间交换变量*/
    a[left] = a[i];
    a[i] = temp;

    /*再以二分法的思想，进行再次分别排序，利用递归*/
    quicksort(left,i-1);
    quicksort(i+1,right);
}

int main()
{
    int n;
    printf("please intput the count:\n");
    scanf("%d",&n);
    for(int i=0; i<n; i++)
    {
        scanf("%d",&a[i]);
    }
    quicksort(0,n-1);
    for(int i=0; i<n; i++)
    {
        printf("%d\t",a[i]);
    }
    printf("\n");
    return 0;
}

总结：

代码实现是通过递归实现的，所以要注意递归结束的条件。

排序方法挺多的，希望自己可以慢慢从思想上和代码中去领悟吧。。。。

这里写图片描述