参考书籍--《啊哈！算法》 作者：啊哈磊

首先提出一个问题：班内有5名同学，成绩分别为5，8，2，4，2分（满分10分），需要将成绩从小到大排序

桶排序(简化版)

时间复杂度O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.Scanner;

public class Bucket_sort {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        /**
         * 需要进行排序的数字范围在 0-5之间
         * */
        int[] a = new int[6];
        /**
         * 注意并非将数据存起来，而是在对应的“桶”内计数，最后统计出现次数
         * */
        for (int i = 0; i < n; i++) {
            int k = input.nextInt();
            a[k]++;
        }
        /**
         * 打印 内循环控制重复数据要重复读取
         * */
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < a[i] ; j++) {
                System.out.println(i);
            }
        }
    }
}

存疑一：这样成绩是按顺序存起来了，但是如果现在的情况是Lili 5分，Tony 8分，Joy 2分，Peter 3分，Ben 2分。如何在保证姓名和成绩对应的情况下排序呢？？ 另一方面，桶排序需要用到的“桶”的个数跟数据的最大值有关系，这里满分为10分只需要10个桶，但是如果数据量较少，但是数据的值较大的时候则会浪费大量空间。

冒泡排序算法

时间复杂度O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.util.Scanner;

public class Bubble_sort {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int[] a = new int[100];
        int n  =input.nextInt();
        /**
         * 输入n个数
         * */
        for (int i = 0; i < n; i++) {
            a[i] = input.nextInt();
        }
        /**
         * 冒泡排序核心算法
         * */
        for (int i = 0; i < n-1; i++) {
            for (int j = i+1; j < n; j++) {
                if (a[i] > a[j]) {
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                }
            }
        }
        /**
         * 打印
         * */
        for (int i = 0; i < n; i++) {
            System.out.print(a[i] + " ");
        }
    }
}

上面的冒泡排序为基本的算法，若想解决存疑一，只需要稍加变通即可实现

存疑二：冒泡排序解决了桶排序浪费空间的难题，但是这种排序算法采用双重循环，时间复杂度为指数级别，效率实在是不够好，有没有可以更快捷的方法呢？

快速排序

时间复杂度O(N·logN) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
import java.util.Scanner;

public class Fast_sort {
    static int n;
    static int[] a;
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        n = input.nextInt();
        a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = input.nextInt();
        }

        fastsort(0, n-1);
        /**
         * 打印
         * */
        for (int i = 0; i < n; i++) {
            System.out.print(a[i] + " ");
        }
    }
    public static void fastsort(int left, int right) {
        if (left > right) {
            return;
        }
        int temp = a[left];
        int i = left;
        int j = right;
        /**
         * i == j 的时候为“一趟”结束的时候
         * */
        while (i != j) {
            /**
             * 顺序一定要从j开始，
             * a[j]如果不小于temp则前进,a[i]如果不大于temp则前进
             *
             * */
            while (a[j] >= temp && i < j) {
                j--;
            }
            while (a[i] <= temp && i < j) {
                i++;
            }
            /**
             * 前进过程出现跳出while循环，则需要进行交换
             * */
            if (i < j) {
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
        /**
         * 基准归位
         * */
        a[left] = a[i];
        a[i] = temp;
        /**
         * 处理左侧
         * */
        fastsort(left, i-1);
        /**
         * 处理右侧
         * */
        fastsort(i+1, right);
    }
}

通过快速排序就可以很好的解决存疑二中没有解决的问题了，这种排序算法在时间和空间上都得到了一个很好的利用。

再来一个问题：给出一串数字，这些数字没有顺序，而且还有许多重复的，我们需要完成排序和去重两个步骤 那么问题可以通过两种方法解决 1）先去重，后排序 解决思路：利用桶排序，在往“桶”中添加的时候，不采用a[i]++;，而是a[i] = 1;这样即使是重复的也不会多次计数了。 2）先排序，后去重 解决思路：可以利用冒泡和快排，由于排序完的序列，重复值都会在一个区间内，这样在输出的时候加个if判断即可实现。

存疑三：若是数据值十分巨大，该如何选择算法？ 若数据量十分庞大，又该如何选择算法？

显然，对于数据值较大的题目，桶排序并不适合 而对于数据量较多的题目，冒泡排序要运行相当长的时间。所以快速排序真的是一个有效、方便的算法呢！！！