排序算法（二）——交换排序（冒泡排序+快速排序）
#Algorithm#排序算法#冒泡排序#快速排序 2018-04-04

冒泡排序

算法分析

冒泡排序可能是排序算法中最简单最好理解的算法了。

以正序排序为例，该算法从序列头部开始，每次将当前元素与下一个元素进行比较，若下一个元素小于该元素，则交换位置。依次递增迭代指针，直至序列尾部。这“一趟”操作过后，序列中最大的值就冒到了序列尾部。

以下列序列为例：

1
50 13 55 97 27 38 49 65

从下标为 0 的元素 50 开始，与 13 进行比较，13 < 50 == true，则交换位置。序列变为：

1
13 50 55 97 27 38 49 65

下标加 1，继续上述操作：55 < 13 == false，则不执行交换操作。下标加 1，重复上述操作，直至序列尾部，则完成“一趟”冒泡。序列变为：

1
13 50 55 27 38 49 65 97

继续从头进行冒泡操作，每次都将剩余元素中最大的元素冒泡到尾部。直至一趟下来未发生位置交换，则说明序列已有序。

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const bubbleSort = array => {
    // 使用 exchange 记录发生交换的位置
    let exchange = array.length - 1;

    // 若上一趟未发生交换，则说明序列已有序，算法结束
    while (exchange !== 0) {
        // 暂存上次交换位置，交换位置之后的序列已经有序，则跳过比较。
        let end = exchange;
        exchange = 0;

        for (let j = 0; j < end; j++) {
            if (array[j] > array[j + 1]) {
                [array[j], array[j + 1]] = [array[j + 1], array[j]];  // 交换位置
                exchange = j; // 记录交换位置
            }
        }
    }
}

上述代码对冒泡算法的基本算法进行了一些优化。使用一个变量记录上一趟冒泡的最后交换位置，该位置之后的元素未发生交换，即说明该位置之后的序列已经有序。则在此趟冒泡中不需要对后面有序的子序列进行操作了。当上一躺未发生交换时，则说明序列已经有序，结束循环。

快速排序

算法分析

快速排序（快排）着眼于解决冒泡排序位置交换次数太多的问题。希望通过一次进行长距离的交换从而减少交换次数。

快排又称为分区交换排序，其基本思想是：首先选一个轴值（pivot，即比较的基准值），每次都将序列划分为两部分，左侧记录的关键码均小于基准值，右侧记录的关键码均大于基准值。然后对左右两部分分别重复上述划分操作，直至序列整体有序。

显然快排是一个递归的过程。

一次划分算法

由于快排是一个递归过程，我们先分析对序列进行一次划分的一种算法思路。

该示例算法，选取序列第一个元素为基准值。从序列两侧交替与该基准值比较，进行相应的位置移动。直至所有的值都移动到了合适的位置（小于基准值的移动到基准值左侧，反之右侧）。

以下面序列为例，具体解释一下算法过程。

23 13 49 6 31 19 28

首先选取第一个元素 23 作为基准值。先从右侧进行比较，令右侧指针为 j = 6，28 > 23 == true 且该值处于基准值右侧，则无序移动。j--，继续比较下一个值。19 > 23 == false，则将该值与基准值交换，使得该值位于基准值的左侧，且同时保证了基准值的右侧都是大于基准值的元素。此时，序列变为：

19 13 49 6 31 23 28

基准值被移动到右侧，进行进行左侧元素的比较。令左侧指针为 i = 0，19 < 23 == true，且位于基准值左侧，无需操作。i++，13 < 23 == true，无需操作。继续比较下一个值，49 < 23 == false，则将 49 与基准值交换，使得该值位于基准值的右侧，且保证了基准值左侧都是小于基准值的元素。此实，序列变为：

19 13 23 6 31 49 28

交替进行右侧扫描，上次 j = 5，则对 j = 4 的元素进行比较，31 > 23 == true，无需操作。j--，6 > 23 == false，则交换位置，序列变为：

19 13 6 23 31 49 28

此时，基准值左侧的值均小于基准值，右侧的值均大于基准值，完成一次划分。

一次划分示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const partition = (arr, first, end) => {
    let i = first
    let j = end
    while (i < j) {
        while (i < j && arr[i] <= arr[j]) j--
        if (i < j) {
            [arr[i], arr[j]] = [arr[j], arr[i]]
            i++
        }
        while (i < j && arr[i] <= arr[j]) i++
        if (i < j) {
            [arr[i], arr[j]] = [arr[j], arr[i]]
            j--
        }
    }
    return i;
}

该示例代码，左右依次与基准值进行比较并交换位置，以保证每次交换后都能使得操作过的值处于合适的位置。同时当左右指针指向同一个值时，说明循环结束。

快速排序算法

快排算法是一个递归的过程。首先将序列进行一次划分，然后分别对左右子序列进行递归的划分。直到子序列被划分为最小的长度，则所有的子序列都有序，则整个序列有序。

1
2
3
4
5
6
7
8
9
10
const quickSort = (arr, first, end) => {
    first = first === undefined ? 0 : first
    end = end === undefined ? arr.length - 1 : end

    if (first < end) {
        let pivot = partition(arr, first, end)
        quickSort(arr, first, pivot - 1)
        quickSort(arr, pivot + 1, end)
    }
}

总结

冒泡排序的时间复杂度为 O(n)，是稳定的排序方法。

快速排序的时间复杂度为 O(nlog2n)，是不稳定的排序方法。

正如其名，快排是迄今为止所有内排序算法中最好的一种，尤其适用于待排序记录个数很大且原始记录随机排列的情况。快排算法得到广泛应用，如 UNIX 系统的库函数中的 qsort 函数。