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

胡佳露 18/05/08 17:00:42

桶排序


  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;
}

总结:

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


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

这里写图片描述

作者:qq_36573828 发表于 2018/05/08 17:00:42 原文链接 https://blog.csdn.net/qq_36573828/article/details/80242428
阅读:16