1. 简单桶排序

对于要排序的数据, 其有范围在 n <= k <= m 之内, 则令有 m - n + 1 个桶, 然后对需要排序的 x 个数据, 依次遍历后, 装到对应的桶中, 最后再对桶进行遍历可得到排序后的数据.

比如有 [8, 5, 2, 3, 1, 5, 10] 这 7 个数据, 其值在 1 - 100 之间, 则有桶的个数为 100 个. 对数据进行遍历, 每次把数据装到桶中, 8 则装到 第 8 个桶, 依次进行. 最后再遍历这 100 个桶个分别有几个数据可得出排序后的序列.

对于 N 个数据, 其对应的范围为 M, 则需要初始化遍历 M 次, 然后再对数据序列遍历 N 次来排序, 简单桶排序的时间复杂度为 O(N+M)

对于小型的数据范围, 简单桶排序是一个非常快的算法, 而一但当数据量非常大, 或者范围非常大, 但有效数据只是很小的值, 比如范围为 1-1 亿, 数据只是为 [8, 5, 2, 3, ….] 这几个数时, 一样还需要 1 亿个桶, 但其中只用到了某几个桶而已, 这就造成了巨大的空间浪费, 而且所需要的时间也呈直线上升.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def randnumber():
    return [randint(0, 101) for n in range(20)]

def bucket_sort(data, max):
    print("Before:\t", data)
    sorted_data = [0] * (max + 1)
    for i in data:
        sorted_data[i] += 1
    data = [j for j in range(len(sorted_data)) for _ in range(sorted_data[j])]
    print("After:\t", data)

Before: [18, 97, 1, 59, 38, 70, 34, 32, 21, 80, 87, 33, 42, 49, 63, 99, 33, 5, 45, 39]

After: [1, 5, 18, 21, 32, 33, 33, 34, 38, 39, 42, 45, 49, 59, 63, 70, 80, 87, 97, 99]

2. 冒泡排序

冒泡排序的基本思想是: 每次都比较相邻的两个元素, 如果它们的顺序是错误的, 就交换位置.

比如对于 [8, 5, 2, 3, 1, 5, 10] , 要从小到大来排序的话, 从 8 开始比较, 8 > 5, 则交换变成 [5, 8, 2, 3, 1, 5, 10]. 再比较 8 > 2, 变成 [5, 2, 8, 3, 1, 5, 10], 一直比下去直到第一轮完成时 [5, 2, 3, 1, 5, 8, 10], 第一轮便确定了最大值在最右边. 第二轮再从 5 开始比较, 一直比较到 8, 便可确定第二大的数.

所以对于冒泡排序, 当有 n 个数时, 一共要比较 (n - 1 + n - 2 + … + 1) 次, 即该算法的时间复杂度为 O( n<sup>2</sup>)

1
2
3
4
5
6
7
def bubble_sort(data):
    print("Befor:\t", data)
    for i in range(1, len(data)):
        for j in range(len(data) - i):
            if data[j] > data[j + 1]:
                data[j], data[j + 1] = data[j + 1], data[j]
	print("After:\t", data)

Befor: [55, 4, 88, 68, 77, 49, 13, 14, 20, 69, 46, 54, 88, 41, 82, 47, 92, 27, 37, 2] After: [2, 4, 13, 14, 20, 27, 37, 41, 46, 47, 49, 54, 55, 68, 69, 77, 82, 88, 88, 92]

3. 快速排序

快速排序主要的思想是采用分而治之的思想, 每次选取一个数, 然后比较剩余的数值, 比选定的数小的放在左边, 大的放在右边. 这样一来, 左右两边的数都确定了比该数大或小, 然后再对左边和右边分别进行现样的操作, 直到左右两边都分到只有一个数的时, 这样排序便完成.

快速排序的内存优化方法在于, 在选定数之后, 从左边开始循环, 如果找一个比选定的数大的停止下来; 右边也是同样的循环, 直到找到比选定数小的, 这样交换两边找到的数, 交换之后再继续循环下来, 循环终止的条件是左右两边都指向同一个位置里的数据, 或者如果选定的数的位置为中间, 则循环到该位置. 如果选定的数为其他地方, 在循环停止后, 把选定的数移到分好类的数据中间.

快速排序时间复杂度, 最坏情况下为 O(n<sup>2</sup>), 平均时间复杂度为 O(nlog n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def quick_sort(data, left, right):
    if left >= right:
        return
    pivot = data[left]
    l, r = left, right
    while l < r:
        while data[r] >= pivot and r > l:
            r -= 1
        data[l] = data[r]

        while data[l] <= pivot and l < r:
            l += 1
        data[r] = data[l]
    data[l] = pivot

    quick_sort(data, left, l - 1)
    quick_sort(data, l + 1, right)

因为我们总是指定左边第一个为标杆数, 所以总是要先从右边开始查找, 这样才能保证在停止从左右两边查找时, 停止的位置总是小于(或大于, 当降序时)指定的数. 反之, 如果指定右边的数, 要先从左边先检查起.

递归版本的快排, 在数据量大的时候可能会爆栈, 解决办法是使用循环来代替递归, 或者使用尾递归

下面是一个用循环来实现的快排, 用栈来保存左右边界值

快排的时间复杂度能选择的标杆值 pivot 有很大的关系, 最好是能随机选择三个数, 排序后选择中间值

 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
public int partition(int[] arr, int left, int right) {
    if (left >= right) {
        throw new ArrayIndexOutOfBoundsException();
    }

    int start = left;
    int pivot = arr[start];
    while (left < right) {
        while (right > left && arr[right] < pivot) {
            right--;
        }

        while (left < right && arr[left] > pivot) {
            left++;
        }

        if (left < right) {
            int tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
            // 因为设定的是当该数 == pivot 时也是需要交换, 所以为避免死循环, 需要手动移位
            right--;
            left++;
        }
    }
    return left;
}

public void qsort(int[] arr) {
    Stack<Integer> stack = new Stack<>();
    stack.push(0);
    stack.push(arr.length - 1);
    while (!stack.empty()) {
        int high = stack.pop();
        int low = stack.pop();
        int pos = partition(arr, low, high);
        if (pos > low) {
            // push left
            stack.push(low);
            stack.push(pos);
        }
        if (pos + 1 < high) {
            //push right
            stack.push(pos + 1);
            stack.push(high);
        }
    }
}

Reference:

  1. http://www.yebangyu.org/blog/2016/03/09/quicksort/