排序算法(二)——交换排序(冒泡排序+快速排序)

冒泡排序

算法分析

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

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

  以下列序列为例:

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 = 628 > 23 == true 且该值处于基准值右侧,则无序移动。j--,继续比较下一个值。19 > 23 == false,则将该值与基准值交换,使得该值位于基准值的左侧,且同时保证了基准值的右侧都是大于基准值的元素。此时,序列变为:

  19 13 49 6 31 23 28

  基准值被移动到右侧,进行进行左侧元素的比较。令左侧指针为 i = 019 < 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 函数。