代码实现在
https://gitee.com/imcheney/algorithm/blob/master/sort.py
1.1 Bubble-Sort(O(n^2))
Bubble-Sort(A) {
for (i=A.length-1 to 1)
for (j=1 to i)
if (A[j]>A[j+1])
swap A[j] and A[j+1]
}
1.2 Insertion-Sort(O(n^2))
Insertion-Sort(A) {
for i = 2 to A.length
j = i-1
key = A[i]
while (j>0 && A[j]>key)
A[j+1] = A[j]
j--
A[j+1] = key
}
2 Merge-Sort(O(nlgn))
Merge-Sort(A, p, r) {
if p<r
q = floor((r+p)/2)
Merge-Sort(A, p, q)
Merge-Sort(A, q+1, r)
Merge(A, p, q, r)
}
Merge(A, p, q, r) {
n1 = q-p+1
n2 = r-q
let L[n1+1] and R[n2+1] be new arrays
for (i = 1 to n1)
L[i] = A[p-1+i]
for (j = 1 to n2)
R[j] = A[q+j]
L[n1+1] = 99999 //代表无穷大的哨兵牌, 最后不输出
L[n2+2] = 99999
i = 1, j = 1
for (k=p to r)
if (L[i]<R[j])
A[k] = L[i]
i++
else
A[k] = R[j]
j++
}
3 Heap-Sort(O(nlgn))
Heap-Sort(A) {
A.heapsize = A.length
Build-Heap(A)
for (i = A.heapsize to 2)
swap A[i] with A[1]
A.heapsize--
Max-Heapify(A, 1)
}
Build-Heap(A) {
A.heapsize = A.length
for (i = floor(A.heapsize/2) to 1)
Max-Heapify(A, i)
}
Max-Heapify(A, i) {
l = Left(i) //求出左右子节点的index
r = Right(r)
largest = i
if (l<=A.heapsize && A[largest]<A[l])
largest = l
if (r<=A.heapsize && A[largest]<A[r])
largestIndex = r
if (largestIndex != i)
swap A[i] and A[largest]
Max-Heapify(A, largest)
}
4 Quick-Sort(theta(nlgn), best method usually)
Quick-Sort(A, p, r) {
if p<r
q = Partition(A, p, r)
Quick-Sort(A, p, q-1)
Quick-Sort(A, q+1, r)
}
Partition(A, p, r) {
q = RANDOM(p, r) //randomizing
swap A[q] with A[r]
i = p-1 //use i to mark the bound of smaller area
for j=p to r-1
if A[j] < A[r]
i++
swap A[j] with A[i] //make the smaller element in the smaller area
swap A[r] with A[i+1] //make the pivot A[r] be in the center
return i+1
}
5.1 Counting-Sort
//前提条件, A数组中的数∈[0, k], 即已知所有数字都小于等于k
Counting-Sort(A, B, k) {
let C[0..k] be a new array
for (i = 0 to k)
C[i] = 0
for (j = 1 to A.length)
C[A[j]]++ //after the for loop, C[i] contains the count number of elements whose value is i
for i = 1 to k
C[i] = C[i]+C[i-1] //C[i] contains the count number of elements whose value <= i
for j = A.length downto 1
B[C[A[j]]] = A[j]
C[A[j]]--
}
5.2 Radix-Sort
Radix-Sort(A, d) {
for i = 1 to d
**stable** sort Array A **on digit i**
}
5.3 Bucket-Sort
//前提条件: A数组中每个元素的值都是在[0, 1)区间产生的均匀分布的随机数
Bucket-Sort(A) {
n = A.length //A数组有多长, n就有多大
let B[0..n-1] be a new array //假设数组长度5, it will be like B[0], B[1]...B[4]
for i = 0 to n-1
make B[i] an empty list
for i = 1 to n
insert A[i] into list B[floor(n*A[i])] //e.g. A[3]= 0.66, 5*0.66 = 3.3, so it will be inserted to B[3]
for i = 0 to n-1
sort list B[i] with insertion sort //B[i]中内部插入排序一下;
concatenate the lists B[0], B[1], ..., B[n-1] together in order //按照顺序把这些都连接起来
}
