一次刷题

其实这篇文章主要是为了记录一下关于桶排序的,然后顺便也记录一下其他的排序算法。

说到桶排序还是因为有一次做一 acm 题,主要是对一堆数进行排序。当时觉得水题。。水题。。水水更健康,单身 20 年手速撸完一发冒泡,直接返回了个Time Limit Exceeded.

emoji-wtf.jpg

后来看了一下题解,发现很多人用Pascal写了桶排序 AC 了,当时也没看过关于桶排序,前段时间看了些资料,然后简单记录一下它的思想。

桶排

先上个图(截自《啊哈!算法》)

bucket-sort-analysis.png

思想:

  • 要求排序的数在[1, n]区间。
  • 开辟一个 n+1 大小的数组,每个元素就是一个空桶(a[n] = 0)。
  • 将要排序的数依次标记到与数组下标相同的位置(如数 x,使 a[x]得到一次标记,比如 a[x]++)。
  • 输出有标记的数值。

上图可以直观的看到其过程,下面是实现:

//bucketSort.cpp
#include<stdio.h>
int main()
{
    int i, j, a[10], t;

    for(i = 0; i < 10; i++)
        a[i] = 0;

    /* 输入并标记 */
    for(i = 0; i < 5; i++)
    {
        scanf("%d", &t);
        a[t]++;
    }

    /* 输出有标记的桶 */
    for(i = 0; i < 10; i++)
        for(j = 1; j <= a[i]; j++)
            printf("%d ", i);

    return 0;
}

这种排序虽然时间复杂度低,但是有很多缺点,如排列 1,1234567 则要一个 1234568 大小的数组,巨大的空间浪费,而且需要已知排列数的范围大小,还只能是整数。

冒泡排序

思想:每一次与向后相邻的一个数进行比较,如果大/小就交换位置,n 个数第一次则最多交换 n-1 次。

如小数向后冒泡:2 5 8 6 7

5 2 8 6 7//第一次比较交换

5 8 2 6 7//第二次比较交换

5 8 6 2 7

5 8 6 7 2

但是 n 个数排序只需要排 n-1 次,最后一个数自己就不用排序了。

注意单排序比较的次数为 n-i-1 次,但不一定会交换这么多次(最坏的情况下都要交换)。
需要进行排序的数的个数为 n-1,因为最后一个数不用排列了。

实现:

//bubbleSort.cpp
#include<stdio.h>
int main()
{
    int i, j, tmp, a[10] = {2, 1, 4, 6, 5, 7, 9, 8, 0, 3};

    for(i = 0; i < 9; i++) /* i只是为了标记还有多少个数需要冒泡 */
    {
        for(j = 0; j < 9 - i; j++) /* j每次从第一个相邻的数比较起,需要比较n-i-1次,因为后面的后面的数已经排列好了 */
        {
            if(a[j] > a[j+1]) /* 交换 */
            {
                tmp = a[j];
                a[j] = a[j+1];
                a[j+1] = tmp;
            }
        }
    }

    for(i = 0; i < 10; i++)
        printf("%d ", a[i]);

    return 0;
}

//////未完待续