Introduction to Algorithms--Sort problems

Posted on | In

(Pseudocode)

Insert Sorting

1
2
3
4
5
6
7
8
9
// from right to left
INSERTION(A)
for j=2 to A.length
	key = A[j]
	i=j-1
	while i>0 and A[i]>key
		A[i+1] = A[i]
		i = i-1
	A[i+1] = key

$O(n^2)$

Merge Sorting

分治模式：（归并排序）

分解：分解待排序的n个元素的序列各具n/2个元素的两个子序列

解决：使用归并排序递归的排序两个子序列

合并：合并两个已排序的子序列以产生已排序的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//A array; p, q, r index
Merge(A, p, q, r)
n1 = p - q + 1
n2 = r - q
let L[1..n1+1] and R[1..n2+1] be new arrays
for i=1 to n1
	L[i] = A[p+i-1]
for j=1 to n2
	L[j] = A[q+j]
L[n1+1] = infinity
R[n2+1] = infinity
i = 1
j = 1
for k=p to r
	if(L[i]<=R[i])
		A[k]=L[i]
		i = i+1
	else
		A[k]=R[j]
		j = j+1

避免在每个基本步骤必须检查堆是否为空，在每个堆的底部放置一张哨兵牌，此处使用infinity作为哨兵值，结果每当显露一张值为infinity的牌，他不可能为较小的值，除非两个堆都已显露出其哨兵牌

1
2
3
4
5
6
MERGE-SORT(A, p, r)
if p<r
	q = (p+r)/2 //向下取整
	MERGE-SORT(A, p, q)
	MERGE-SORT(A, q+1, r)
	MERGE(A, p, q, r)

$O(nlogn)$

Bubble Sorting

1
2
3
4
5
BUBBLESORT(A)
for i=1 to A.length-1
	for j=A.length downto i+1
		if A[j]<A[j-1]
			exchange A[j] with A[j-1]

$ O(n^2) $

Quick Sorting

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
public class MyClass {
    public static void main(String args[]) {
        /**
         * from console input an array
         */
        // int [] a=new int[10];
        // Scanner sc=new Scanner(System.in);
        // for(int i=0;i<a.length;i++){
        //     System.out.println("请输入一个数：");
        //     a[i]=sc.nextInt();
        // }
        int unsortedArray[] = new int[]{6, 5, 3, 1, 8, 7, 2, 4};
        int len = unsortedArray.length;
        quicksort(unsortedArray, 0, len-1);
        System.out.println("After sort:");
        for(int item:unsortedArray)
            System.out.print(item+" ");
    }
    static void quicksort(int[] array, int low, int high){
        if(low < high){
            int pi = partition(array, low, high);
            quicksort(array, low, pi-1);
            quicksort(array, pi+1, high);
        }
    }
    static int partition(int[] array, int low, int high){
        int pivot = array[low];
        int i = low;
        for(int j = low+1;j <= high;j++){
            if(array[j] <= pivot){
                i++;
                //swap a[i] with a[j]
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        //swap pivot with a[i]
        int temp = array[i];
        array[i] = array[low];
        array[low] = temp;
        
        return i;
    }
}

Time complexity:

$O(nlgn)$ average, $O(n^2)$ worst