一次刷题

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

说到桶排序还是因为有一次做一 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;
}

//////未完待续