Processing math: 100%


排序算法的那些事儿

〇、

对于排序算法的考察是很基础的算法考察,而很多面试都会有手写代码的考察,因此这次总结中代码的实现用了伪代码。

可以了解到:

  1. 常见的排序算法
  2. 算法的实现

(最后来写这个引言,真是毫无生气啊……

一、

排序算法 时间复杂度 空间复杂度 是否稳定
冒泡排序 О(n2) О(1)
选择排序 О(n2) О(1)
插入排序 О(n2) О(1)
希尔排序 О(nlog2n) О(1)
归并排序 О(nlogn) О(n)
快速排序 О(nlogn) О(logn)
堆排序 О(nlogn) О(1)
计数排序 О(n+k) О(k)
基数排序 О(nk) О(n+k)

二、

一)冒泡排序(Bubble Sort)

冒泡排序是思想非常简单的排序算法:重复地比较相邻两个数据的大小,将较小的靠前,较大的靠后,将顺序错误的数据交换过来,直到没有再需要交换的数据为止。

冒泡排序还是原地算法(in-place algorithm),即不需要额外的辅助空间来进行转换的算法,包含了空间复杂度为О(1)的所有算法。

而“稳定”是指,对于数值相同的元素,其排列的顺序在经过排序后并没有发生改变,则称这样的排序算法是稳定的。

冒泡算法虽然简单,但在数列数据较大时很没有效率,因此唯一的用处大概就是学习算法课程的时候,经常被用来介绍算法的概念吧。

伪代码如下:

1
2
3
4
5
6
function bubble_sort (array, length):
var i, j
for i <- 0 to length-1:
for j <- 0 to length-1-i:
if array[j] > array[j+1]:
swap(array[j], array[j+1])

上面的pseudo-code只有循环判断过整个数列后才会停止,很可能在后面数列已经排序完成,却进行了许多无用的判断。为了优化此算法,可以加入判断条件,如果一次内循环没有交换过任何数据,即表明数列已经完成了排序。

1
2
3
4
5
6
7
8
9
10
11
12
function bubble_sort_withflag (array, length):
var i, j
bool flag
for i <- 0 to length-1:
flag <- false
for j <- 0 to length-1-i):
if array[j] > array[j+1]:
swap(array[j], array[j+1])
flag <- true

if (flag == false)
break

还可以继续优化算法,通过尝试已经大部分有序的数列(如2,3,4,5,1),冒泡算法依然要进行完整的循环。但如果此时能够反向的“冒泡”,即可一次循环就将数据“1”排到正确的位置上去。

这种改进的算法叫做鸡尾酒排序(Cocktail Sort),也叫定向冒泡排序,排序时将以两个方向在数列中进行排序,因此对于大部分有序的数列,时间复杂度会接近О(n2),当然平均复杂度依然是О(n2)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function cocktail_sort (array, length):
var left <- 0, right <- length - 1
bool flag
while left < right:
flag <- false
for var i <- left to right-1:
if array[i] > array[i + 1]:
swap(array[i], array[i + 1])
flag <- true
right--
for var j <- right to left+1:
if array[j] < array[i - 1]:
swap(array[i], array[i - 1])
flag <- true
left++
if (flag == false)
break

二)选择排序(Selection Sort)

选择排序的基本思想也很简单:首先在未排序序列中找到最小(或者最大)元素,存放到排序序列的起始(末尾)位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

选择排序的优势在于交换次数较冒泡排序更少,通常交换操作需要的CPU时间比比较操作的时间更多,因此选择排序是要优于冒泡排序的,但同样也是О(n2)的时间复杂度就是了;另外一个优势是原地操作,当空间复杂度要求较高时,可以考虑选择排序,但实际上可以使用的场合非常罕见了。

1
2
3
4
5
6
7
8
function selection_sort(array, length):
int min
for int i <- 0 to length-1:
min <- i
for int j <- i+1 to length:
if array[j] < array[i]:
min <- j
swap(array[min], array[i])

三)插入排序(Insertion Sort)

插入排序的基本思想是将序列划分为有序部分和未排序部分,对于未排序部分的数据,在有序部分从后向前扫描,找到正确的位置插入。

同时插入排序是在线算法,并不要求输入数据在开始运行前完备。

1
2
3
4
5
6
7
8
9
10
function insertion_sort(array, length):
int i, j
int temp
for i <- 1 to length-1:
temp <- array[i]
j <- i
while j > 0 and array[j-1]>temp:
array[j] <- array[j-1]
j--
array[j] <- temp

四)希尔排序(Shell Sort)

希尔排序是对插入排序的一种改进版本,也叫递减增量排序算法。其基本思想是:将全部元素分为几个区域,提升插入排序的性能(一次性让元素向着最终的位置前进一大步)。通过不断减少步长,到最后插入排序(步长为1时),数列几乎是已经排列好的了。

1
2
3
4
5
6
7
8
9
10
11
12
13
function shell_sort(array, length):
int i, j, step
int temp // element type in array
while step > 0:
for i <- step to length-1:
temp <- array[i]
j <- i
while j >= step and array[j - step] > temp:
array[j] <- array[j - step]
j <- j - step
array[j] <- temp
step <- step / 2

五)归并排序(Merge Sort)

归并排序的基本思想是采用分治法(Divide and Conquer),基于归并操作,首先与插入算法类似地将每个元素看作已经排好序的子序列,之后两两进行归并操作,直到完成序列的排序。

进行归并操作需要О(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
function merge_sort(arr, length):
int[] temp = arr
merge_sort_recursive(arr, temp, 0, length-1)

function merge_sort_recursive(arr, temp, left, right):
// 分割问题
if left >= right:
return
int mid <- (right - left) >> 1 + left
int l1 <- left, l2 <- mid+1
int r1 <- mid, r2 <- right
merge_sort_recursive(arr, temp, l1, r1)
merge_sort_recursive(arr, temp, l2, r2)
// 处理问题
int i <- left
while l1 <= r1 and l2 <= r2:
if arr[l1] < arr[l2]:
temp[i++] <- arr[l1++]
else:
temp[i++] <- arr[l2++]
while l1 <= r1:
temp[i++] <- arr[l1++]
while l2 <= r2:
temp[i++] <- arr[l2++]
for k <- left to right:
arr[k] <- temp[k]

六)快速排序(Quick Sort

快速排序,又称划分交换排序(partition-exchange sort),简称快排。都说是经常会被拿出来考的算法。基本思想也是使用了分治法,选定一个pivot值,将序列分为两个子序列,其中左侧的子序列全部小于pivot,右侧的子序列全部大于pivot,直到每个子序列只有一个数据排序完成。

由于使用递归,每次递归需要О(1)的额外空间,因此原地(in-place)的快速排序算法平均需要О(logn)的额外空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function quick_sort(arr, length):
quick_sort_recursive(arr, 0, length-1)

function quick_sort_recursive(arr, left, right):
if left < right:
int l <- left, r <- right, cur <- right
int pivot <- arr[right]
while l < r:
while l < r and arr[l] < pivot: l++
while l < r and arr[r] >= pivot: r--
arr[cur] <- arr[l]
arr[l] <- arr[r]
cur <- r
arr[cur] <- pivot
quick_sort_recursive(arr, left, cur-1)
quick_sort_recursive(arr, cur+1, right)

为了避免递归过深,在内省排序(introsort)算法中,当递归深度超过一定深度(深度为排序元素数量的对数值)后转为堆排序。2000年SGI的C++标准模板库中的不稳定排序算法就采用了Introsort。

七)堆排序(Heap Sort)

堆排序的基本思想是利用堆数据结构,利用最大堆调整,将数列保存到最大堆中,之后将根节点与堆尾互换完成排序。

最大堆调整(Max_Heapify)是将堆的末端子节点作调整,使得子节点永远小于父节点,以符合最大堆的结构要求。

将最大堆存入数组中,对于节点i与其相关节点之间的关系为(索引从1开始):节点i的父亲节点为i2,节点i的左子节点为2i,节点i的右子节点为2i+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function max_heapify(arr, start, end):
p <- start
c <- p * 2 + 1
while c <= end:
if c + 1 <= end and arr[c] < arr[c+1]:
c++
if arr[p] > arr[c]:
return
else:
swap(arr[p], arr[c])
p <- c
c <- p * 2 + 1

function heap_sort(arr, len):
for i <- len/2 to 0:
max_heapify(arr, i, len-1)
for i <- len-1 to 0:
swap(arr[0], arr[i])
max_heapify(arr, 0, i-1)

八)计数排序(Counting Sort)

计数排序与基数排序不同于上面的排序,并不是基于比较的排序算法,因此可以突破О(nlogn)的极限,称为线性时间排序算法。

计数排序的方法是使用一个额外的数组C,其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。

过程:

  1. 找出待排序的数组中最大和最小的元素
  2. 统计数组中每个值为i的元素出现的次数,存入数组C的第i项
  3. 对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加)
  4. 反向填充目标数组:将每个元素i放在新数组的第C[i]项,每放一个元素就将C[i]减去1
1
2
3
4
5
6
7
8
9
10
11
12
function counting_sort(arr, len):
m <- max(elements in arr)
counts <- new array(m + 1)
sorted <- new array(len)
for i <- 0 to m:
counts[i] <- 0
for i <- 0 to len:
connts[arr[i]]++
for i <- 1 to m:
counts[i] += counts[i-1]
for i <- len-1 to 0:
sorted[--counts[arr[i]]] = arr[i]

九)基数排序(Radix Sort)

基数排序的原理是将整数按位数切割成不同的数字,然后按每个位数分别比较,从低位到高位进行排序。

1
2
3
4
5
6
7
function radix_sort(arr, len):
m <- max_bit(arr)
radix <- 1
for i <- 0 to m-1:
counting_sort_by_bit(arr, len, radix)
radix <- 10*radix
return arr

三、

问题:

  1. 基于比较的排序算法的极限时间复杂度是?为什么?
  2. 从数组到链表时间复杂度显著增大的排序方法有哪些?