排序算法

前言

最近了解到一个项目，包含了技术面试必备的基础知识，感觉很不错，今天准备先学习一下其中的排序算法，并用python实现一下。

原文：https://cyc2018.github.io/CS-Notes/#/notes/%E7%AE%97%E6%B3%95%20-%20%E6%8E%92%E5%BA%8F

排序算法的成本模型是交换和比较次数。

选择排序

从数组中选择最小元素，将它与数组的第一个元素交换位置。再从数组剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。

选择排序需要 $~N^2/2$ 次比较和 $~N$ 次交换，它的运行时间与输入无关，这个特点使得它对一个已经排序的数组也需要这么多的比较和交换操作。

选择排序

时间复杂度：$O(n^2)$

1
2
3
4
5
def selection_sort(nums: List):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[j] < nums[i]:
                nums[j], nums[i] = nums[i], nums[j]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Selection<T extends Comparable<T>> extends Sort<T> {

    @Override
    public void sort(T[] nums) {
        int N = nums.length;
        for (int i = 0; i < N - 1; i++) {
            int min = i;
            for (int j = i + 1; j < N; j++) {
                if (less(nums[j], nums[min])) {
                    min = j;
                }
            }
            swap(nums, i, min);
        }
    }
}

冒泡排序

从左到右不断交换相邻逆序的元素，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。

在一轮循环中，如果没有发生交换，那么说明数组已经是有序的，此时可以直接退出。

作者这里介绍的标志位， 其实已经是冒泡排序的优化了，如果不优化就直接循环len次。

冒泡排序

最差时间复杂度为$O(N^2)$,最好为$O(N)$

1
2
3
4
5
6
7
8
9
10
def Bubble_sort(nums: List):
    iswaped = True
    i = 0
    while i < len(nums) - 1 and iswaped:
        iswaped = False
        for j in range(len(nums) - i - 1):
            if nums[j] > nums[j + 1]:
                iswaped = True
                nums[j], nums[j + 1] = nums[j + 1], nums[j]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Bubble<T extends Comparable<T>> extends Sort<T> {

    @Override
    public void sort(T[] nums) {
        int N = nums.length;
        boolean isSorted = false;
        for (int i = N - 1; i > 0 && !isSorted; i--) {
            isSorted = true;
            for (int j = 0; j < i; j++) {
                if (less(nums[j + 1], nums[j])) {
                    isSorted = false;
                    swap(nums, j, j + 1);
                }
            }
        }
    }
}

插入排序

每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左侧数组依然有序。

对于数组 {3, 5, 2, 4, 1}，它具有以下逆序：(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)，插入排序每次只能交换相邻元素，令逆序数量减少 1，因此插入排序需要交换的次数为逆序数量。

插入排序的时间复杂度取决于数组的初始顺序，如果数组已经部分有序了，那么逆序较少，需要的交换次数也就较少，时间复杂度较低。

  • 平均情况下插入排序需要 ~N2/4 比较以及 ~N2/4 次交换；
  • 最坏的情况下需要 ~N2/2 比较以及 ~N2/2 次交换，最坏的情况是数组是倒序的；
  • 最好的情况下需要 N-1 次比较和 0 次交换，最好的情况就是数组已经有序了。

插入排序，顾名思义，每次从要排序的元素视为新插入的，从右到左依次比较，如果比坐标的元素大，就交换。循环直到不会再小于左边的元素，因为所有左边的元素都是排好序的。

插入排序

1
2
3
4
5
6
7
def insertion_sort(nums: List):
    for i in range(1, len(nums)):
        for j in range(i, 0, -1):
            if nums[j] < nums[j - 1]:
                nums[j], nums[j - 1] = nums[j - 1], nums[j]
            else:
                break
1
2
3
4
5
6
7
8
9
10
11
12
13
public class Insertion<T extends Comparable<T>> extends Sort<T> {

    @Override
    public void sort(T[] nums) {
        int N = nums.length;
        for (int i = 1; i < N; i++) {
            for (int j = i; j > 0 && less(nums[j], nums[j - 1]); j--) {
                swap(nums, j, j - 1);
            }
        }
    }
}

希尔排序

对于大规模的数组，插入排序很慢，因为它只能交换相邻的元素，每次只能将逆序数量减少 1。希尔排序的出现就是为了解决插入排序的这种局限性，它通过交换不相邻的元素，每次可以将逆序数量减少大于 1。

希尔排序使用插入排序对间隔 h 的序列进行排序。通过不断减小 h，最后令 h=1，就可以使得整个数组是有序的。

希尔排序

希尔排序

时间复杂度$O(n^{1.3})$到$O(N^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
def shellSort(nums: List):
    h = 1
    while h < len(nums) / 3:
        h = h * 3 + 1
    while (h >= 1):
        #插入排序
        for i in range(1, len(nums)):
            for j in range(i, 0, -1):
                if nums[j] < nums[j - 1]:
                    nums[j], nums[j - 1] = nums[j - 1], nums[j]
                else:
                    break
        h = h / 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Shell<T extends Comparable<T>> extends Sort<T> {

    @Override
    public void sort(T[] nums) {

        int N = nums.length;
        int h = 1;

        while (h < N / 3) {
            h = 3 * h + 1; // 1, 4, 13, 40, ...
        }

        while (h >= 1) {
            for (int i = h; i < N; i++) {
                for (int j = i; j >= h && less(nums[j], nums[j - h]); j -= h) {
                    swap(nums, j, j - h);
                }
            }
            h = h / 3;
        }
    }
}


归并排序

归并方法

分治法的思想，归并方法将数组中两个已经排序的部分归并成一个。

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
def merge(nums:List,mid:int):
    """

    :param nums: 列表
    :param mid:分割位置
    """
    aux = []
    i = 0
    j = mid + 1
    for k in range(len(nums)):
        aux[k] = nums[k]
    for k in range(len(nums)):
        if i > mid:
            nums[k] = aux[j]
            j += 1
        elif j > len(nums):
            nums[k] = aux[i]
            i += 1
        elif aux[i] <= aux[j]:
            nums[k] = aux[i]
            i += 1
        else:
            nums[k] = aux[j]
            j += 1

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
public abstract class MergeSort<T extends Comparable<T>> extends Sort<T> {

    protected T[] aux;


    protected void merge(T[] nums, int l, int m, int h) {

        int i = l, j = m + 1;

        for (int k = l; k <= h; k++) {
            aux[k] = nums[k]; // 将数据复制到辅助数组
        }

        for (int k = l; k <= h; k++) {
            if (i > m) {
                nums[k] = aux[j++];

            } else if (j > h) {
                nums[k] = aux[i++];

            } else if (aux[i].compareTo(aux[j]) <= 0) {
                nums[k] = aux[i++]; // 先进行这一步，保证稳定性

            } else {
                nums[k] = aux[j++];
            }
        }
    }
}



自顶向下归并排序

将一个大数组分成两个小数组去求解。

因为每次都将问题对半分成两个子问题，这种对半分的算法复杂度一般为 $O(NlogN)$。这里太简单了就直接借用原作者的代码了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Up2DownMergeSort<T extends Comparable<T>> extends MergeSort<T> {

    @Override
    public void sort(T[] nums) {
        aux = (T[]) new Comparable[nums.length];
        sort(nums, 0, nums.length - 1);
    }

    private void sort(T[] nums, int l, int h) {
        if (h <= l) {
            return;
        }
        int mid = l + (h - l) / 2;
        sort(nums, l, mid);
        sort(nums, mid + 1, h);
        merge(nums, l, mid, h);
    }
}

自底向上归并排序

先归并那些微型数组，然后成对归并得到的微型数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Down2UpMergeSort<T extends Comparable<T>> extends MergeSort<T> {

    @Override
    public void sort(T[] nums) {

        int N = nums.length;
        aux = (T[]) new Comparable[N];

        for (int sz = 1; sz < N; sz += sz) {
            for (int lo = 0; lo < N - sz; lo += sz + sz) {
                merge(nums, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
            }
        }
    }
}

快速排序

基本思想

  • 归并排序将数组分为两个子数组分别排序，并将有序的子数组归并使得整个数组排序；
  • 快速排序通过一个切分元素将数组分为两个子数组，左子数组小于等于切分元素，右子数组大于等于切分元素，将这两个子数组排序也就将整个数组排序了。

快排

1
2
3
4
5
6
7
8
9
10
11
12
13
def quickSort(arr, low, high):
    '''

    :param arr: 列表
    :param low: 起始索引
    :param high: 结束索引
    :return: none
    '''
    if low < high:
        pi = partition(arr, low, high)

        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class QuickSort<T extends Comparable<T>> extends Sort<T> {

    @Override
    public void sort(T[] nums) {
        shuffle(nums);
        sort(nums, 0, nums.length - 1);
    }

    private void sort(T[] nums, int l, int h) {
        if (h <= l)
            return;
        int j = partition(nums, l, h);
        sort(nums, l, j - 1);
        sort(nums, j + 1, h);
    }

    private void shuffle(T[] nums) {
        List<Comparable> list = Arrays.asList(nums);
        Collections.shuffle(list);
        list.toArray(nums);
    }
}

切分函数

取 a[l] 作为切分元素，然后从数组的左端向右扫描直到找到第一个大于等于它的元素，再从数组的右端向左扫描找到第一个小于它的元素，交换这两个元素。不断进行这个过程，就可以保证左指针 i 的左侧元素都不大于切分元素，右指针 j 的右侧元素都不小于切分元素。当两个指针相遇时，将切分元素 a[l] 和 a[j] 交换位置。

切分函数

1
2
3
4
5
6
7
8
9
10
def partition(arr,low,high):
     i = low -1
     #j = high + 1
     v = arr[high]
     for j in range(low,high):
         if arr[j] <= v:
             i += 1
             arr[i],arr[j] = arr[j],arr[i]
     arr[i+1],arr[high] = arr[high],arr[i+1]
     return i+1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
private int partition(T[] nums, int l, int h) {
    int i = l, j = h + 1;
    T v = nums[l];
    while (true) {
        while (less(nums[++i], v) && i != h) ;
        while (less(v, nums[--j]) && j != l) ;
        if (i >= j)
            break;
        swap(nums, i, j);
    }
    swap(nums, l, j);
    return j;
}

性能分析

快速排序是原地排序，不需要辅助数组，但是递归调用需要辅助栈。

快速排序最好的情况下是每次都正好将数组对半分，这样递归调用次数才是最少的。这种情况下比较次数为 $CN=2CN/2+N$，复杂度为 $O(NlogN)$。

最坏的情况下，第一次从最小的元素切分，第二次从第二小的元素切分，如此这般。因此最坏的情况下需要比较$N2/2$。为了防止数组最开始就是有序的，在进行快速排序时需要随机打乱数组。

堆排序

堆

堆中某个节点的值总是大于等于（或小于等于）其子节点的值，并且堆是一颗完全二叉树，完全二叉树就是只有最后一层有叶子节点，而且叶子节点是靠左排列的。

堆可以用数组来表示，这是因为堆是完全二叉树，而完全二叉树很容易就存储在数组中。位置 k 的节点的父节点位置为 k/2，而它的两个子节点的位置分别为 2k 和 2k+1。这里不使用数组索引为 0 的位置，是为了更清晰地描述节点的位置关系。

堆

基本函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Heap:
    def __init__(self):
        self.data_list = []

    def isEmpty(self):
        if len(self.data_list) == 0:
            return True
        else:
            return False

    def size(self):
        return len(self.data_list)

    def swap(self, index_a, index_b):
        self.data_list[index_a], self.data_list[index_b] = self.data_list[index_b], self.data_list[index_a]

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
public class Heap<T extends Comparable<T>> {

    private T[] heap;
    private int N = 0;

    public Heap(int maxN) {
        this.heap = (T[]) new Comparable[maxN + 1];
    }

    public boolean isEmpty() {
        return N == 0;
    }

    public int size() {
        return N;
    }

    private boolean less(int i, int j) {
        return heap[i].compareTo(heap[j]) < 0;
    }

    private void swap(int i, int j) {
        T t = heap[i];
        heap[i] = heap[j];
        heap[j] = t;
    }
}


获取父节点

1
2
3
4
5
def get_parent_index(self, index):
    if index == 0 or index > len(self.data_list) - 1:
        return None
    else:
        return (index - 1) >> 1

上浮和下沉

在堆中，当一个节点比父节点大，那么需要交换这个两个节点。交换后还可能比它新的父节点大，因此需要不断地进行比较和交换操作，把这种操作称为上浮。

上浮

1
2
3
4
5
def swim(self, k):
    while (k > 1) and (k >> 1) < k:
        self.swap(k >> 1 , k)
        k = k >> 1

1
2
3
4
5
6
private void swim(int k) {
    while (k > 1 && less(k / 2, k)) {
        swap(k / 2, k);
        k = k / 2;
    }
}

类似地，当一个节点比子节点来得小，也需要不断地向下进行比较和交换操作，把这种操作称为下沉。一个节点如果有两个子节点，应当与两个子节点中最大那个节点进行交换。

下沉

1
2
3
4
5
6
7
8
9
10
11
12
def sink(self, index):
   total_index = self.size() - 1
   while True:
       maxvalue_index = index
       if 2 * index + 1 <= total_index and self.data_list[2 * index + 1] > self.data_list[maxvalue_index]:
           maxvalue_index = 2 * index + 1
       if 2 * index + 2 <= total_index and self.data_list[2 * index + 2] > self.data_list[maxvalue_index]:
           maxvalue_index = 2 * index + 2
       if maxvalue_index == index:
           break
       self.swap(index, maxvalue_index)
       index = maxvalue_index
1
2
3
4
5
6
7
8
9
10
11
12
private void sink(int k) {
    while (2 * k <= N) {
        int j = 2 * k;
        if (j < N && less(j, j + 1))
            j++;
        if (!less(k, j))
            break;
        swap(k, j);
        k = j;
    }
}

插入元素

将新元素放到数组末尾，然后上浮到合适的位置。

1
2
3
4
def insert(self,v):
    self.data_list.append(v)
    index = len(self.data_list) - 1
    self.swim(index)
1
2
3
4
5
public void insert(Comparable v) {
    heap[++N] = v;
    swim(N);
}

删除最大元素

从数组顶端删除最大的元素，并将数组的最后一个元素放到顶端，并让这个元素下沉到合适的位置。

其实就是删除堆顶。

1
2
3
4
5
6
def delMax(self):
    del_data = self.data_list[0]
    self.data_list[0] = self.data_list[-1]
    del self.data_list[-1]
    self.sink(0)
    return del_data
1
2
3
4
5
6
7
8
9
public T delMax() {
    T max = heap[1];
    swap(1, N--);
    heap[N + 1] = null;
    sink(1);
    return max;
}


堆排序

把最大元素和当前堆中数组的最后一个元素交换位置，并且不删除它，那么就可以得到一个从尾到头的递减序列，从正向来看就是一个递增序列，这就是堆排序。

　堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

构建堆

无序数组建立堆最直接的方法是从左到右遍历数组进行上浮操作。一个更高效的方法是从右至左进行下沉操作，如果一个节点的两个节点都已经是堆有序，那么进行下沉操作可以使得这个节点为根节点的堆有序。叶子节点不需要进行下沉操作，可以忽略叶子节点的元素，因此只需要遍历一半的元素即可。

堆排序

交换堆顶元素和最后一个元素

1
2
3
4
5
6
7
8
9
def heapSort(nums:List):
    heap = Heap()
    for i in range(len(nums)):
        heap.insert(nums[i])
    for i in range(heap.size()):
        print(heap.data_list[i])
    nums.clear()
    for i in range(heap.size()):
        nums.append(heap.delMax())
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
public class HeapSort<T extends Comparable<T>> extends Sort<T> {
    /**
     * 数组第 0 个位置不能有元素
     */
    @Override
    public void sort(T[] nums) {
        int N = nums.length - 1;
        for (int k = N / 2; k >= 1; k--)
            sink(nums, k, N);

        while (N > 1) {
            swap(nums, 1, N--);
            sink(nums, 1, N);
        }
    }

    private void sink(T[] nums, int k, int N) {
        while (2 * k <= N) {
            int j = 2 * k;
            if (j < N && less(nums, j, j + 1))
                j++;
            if (!less(nums, k, j))
                break;
            swap(nums, k, j);
            k = j;
        }
    }

    private boolean less(T[] nums, int i, int j) {
        return nums[i].compareTo(nums[j]) < 0;
    }
}

完整代码

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
68
69
70
71
from typing import List


class Heap:
    def __init__(self):
        self.data_list = []

    def isEmpty(self):
        if len(self.data_list) == 0:
            return True
        else:
            return False

    def size(self):
        return len(self.data_list)

    def swap(self, index_a, index_b):
        self.data_list[index_a], self.data_list[index_b] = self.data_list[index_b], self.data_list[index_a]

    def get_parent_index(self, index):
        if index == 0 or index > len(self.data_list) - 1:
            return None
        else:
            return (index - 1) >> 1

    def swim(self, index):
        parent = self.get_parent_index(index)
        # 循环，直到该元素成为堆顶，或小于父节点（对于大顶堆)
        while parent is not None and self.data_list[parent] < self.data_list[index]:
            # 交换操作
            self.swap(parent, index)
            index = parent
            parent = self.get_parent_index(parent)

    def sink(self, index):
        total_index = self.size() - 1
        while True:
            maxvalue_index = index
            if 2 * index + 1 <= total_index and self.data_list[2 * index + 1] > self.data_list[maxvalue_index]:
                maxvalue_index = 2 * index + 1
            if 2 * index + 2 <= total_index and self.data_list[2 * index + 2] > self.data_list[maxvalue_index]:
                maxvalue_index = 2 * index + 2
            if maxvalue_index == index:
                break
            self.swap(index, maxvalue_index)
            index = maxvalue_index



    def insert(self, v):
        self.data_list.append(v)
        index = len(self.data_list) - 1
        self.swim(index)

    def delMax(self):
        del_data = self.data_list[0]
        self.data_list[0] = self.data_list[-1]
        del self.data_list[-1]
        self.sink(0)
        return del_data


def heapSort(nums:List):
    heap = Heap()
    for i in range(len(nums)):
        heap.insert(nums[i])
    for i in range(heap.size()):
        print(heap.data_list[i])
    nums.clear()
    for i in range(heap.size()):
        nums.append(heap.delMax())

分析

一个堆的高度为 logN，因此在堆中插入元素和删除最大元素的复杂度都为 logN。

对于堆排序，由于要对 N 个节点进行下沉操作，因此复杂度为 NlogN。

堆排序是一种原地排序，没有利用额外的空间。

现代操作系统很少使用堆排序，因为它无法利用局部性原理进行缓存，也就是数组元素很少和相邻的元素进行比较和交换。

小结

排序算法的比较

算法 稳定性 时间复杂度 空间复杂度 备注
选择排序 × N2 1
冒泡排序 √ N2 1
插入排序 √ N ~ N2 1 时间复杂度和初始顺序有关
希尔排序 × N 的若干倍乘于递增序列的长度 1 改进版插入排序
快速排序 × NlogN logN
三向切分快速排序 × N ~ NlogN logN 适用于有大量重复主键
归并排序 √ NlogN N
堆排序 × NlogN 1 无法利用局部性原理

快速排序是最快的通用排序算法，它的内循环的指令很少，而且它还能利用缓存，因为它总是顺序地访问数据。它的运行时间近似为 ~cNlogN，这里的 c 比其它线性对数级别的排序算法都要小。

使用三向切分快速排序，实际应用中可能出现的某些分布的输入能够达到线性级别，而其它排序算法仍然需要线性对数时间。

Java的排序算法实现

Java 主要排序方法为 java.util.Arrays.sort()，对于原始数据类型使用三向切分的快速排序，对于引用类型使用归并排序。