Problem sorting 排序算法

Input: $\langle a_1’, a_2’, \dots, a_n’ \rangle$

Output: $\langle \quad a_1’ \leq a_2’ \leq \dots \leq a_n’\rangle$

Insertion sort 插入排序 $Θ(n^2)$

排序步骤：

首先在数组中选择位置j的值为键值key(存在常量在循环后保持不变，即已经排序好的部分，每次循环的目的是为了完成增量)。
从键值的前一个位置开始，一步一步把前面的值抄到下一位上，直到找到此键合适的位置把键值插入。【注意：】外部循环从j开始到n，内部循环从j-1开始并递减至0

伪代码

  
INSERTION-SORT(A, n) or SORTS A[1,n]
    for j=2 to n
        do key = A[j]
            i = j - 1
            while i > 0 and A[i] > key
                do A[i+1] = A[i]
                    i = i - 1
                A[i+1] = key

java实现

  
def insertion_sort(A):
    for j in range(1, len(A)):  # 从第二个元素开始
        key = A[j]
        i = j - 1
        while i >= 0 and A[i] > key:
            A[i + 1] = A[i]
            i -= 1
        A[i + 1] = key

# 示例使用
arr = [5, 2, 4, 6, 1, 3]
insertion_sort(arr)
print(arr)  # 输出 [1, 2, 3, 4, 5, 6]

(分治法) Merge sort 归并排序 $Θ(nlgn)$

递归式

$T(n)= \left\{\begin{matrix} Θ(1),n=1 \\ 2T(n/2)+Θ(n) n>1 \end{matrix}}\right.$

伪代码

Merge-SORT(A, n) or SORTS A[1,n]

If n-1, done
拆分输入A[1,…,[n/2]] and A[[n/2]+1,…,n] (向上取整)
(关键！)把排好序的两个表归并
a. 两张已排序的列表中，最小元素是多少？
b. 将两个中较小的输出到最终的输出数组中
c. 继续比较两个中最小的数，然后继续输出到最终数组中…

【注意：】每一步都是固定数目的操作，和数组尺寸无关。

  
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)        # 合并已排序的两部分

MERGE(A, p, q, r)
    n1 = q - p + 1                 # 左半部分的元素个数
    n2 = r - q                    # 右半部分的元素个数
    Let L[0:n1-1] and R[0:n2-1] be new array   # 创建临时数组L和R

    for i = 1 to n1            # 将左半部分复制到临时数组L
        L[i] = A[p + i - 1]
    for j = 1 to n2            # 将右半部分复制到临时数组R
        R[j] = A[q + j]

    i = 1
    j = 1
    for k = p to r                # 合并L和R到原数组A
        if L[i] <= R[j]
            A[k] = L[i]
            i = i + 1
        else
            A[k] = R[j]
            j = j + 1

java实现

  
public class MergeSort {
    
    # 主排序方法
    public static void mergeSort(int[] arr) {
        if (arr.length > 1) {
            # 找到数组的中间点
            int mid = arr.length / 2;
            
            # 分割数组为两半
            int[] left = new int[mid];
            int[] right = new int[arr.length - mid];
            
            System.arraycopy(arr, 0, left, 0, mid);
            System.arraycopy(arr, mid, right, 0, arr.length - mid);
            
            # 递归排序左右两部分
            mergeSort(left);
            mergeSort(right);
            
            # 合并排序后的数组
            merge(arr, left, right);
        }
    }
    
    # 合并两部分
    private static void merge(int[] arr, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        
        # 比较并合并左右数组的元素
        while (i < left.length && j < right.length) {
            if (left[i] < right[j]) {
                arr[k++] = left[i++];
            } else {
                arr[k++] = right[j++];
            }
        }
        
        # 将左边剩余的元素加入
        while (i < left.length) {
            arr[k++] = left[i++];
        }
        
        # 将右边剩余的元素加入
        while (j < right.length) {
            arr[k++] = right[j++];
        }
    }

    # 测试归并排序
    public static void main(String[] args) {
        int[] arr = { 38, 27, 43, 3, 9, 82, 10 };
        mergeSort(arr);
        
        # 输出排序后的数组
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

(分治法) Qucik sort 快速排序 $Θ(nlgn)$

Sorts in place

首先设定一个分界值，通过该分界值将数组分成左右两部分。
将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。
左边和右边的数据可以独立排序。
通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

伪代码

  
QUICK-SOTR(A,low,high)
    if low < high
        then p = Pratition(A,low,high)
        QUICK-SORT(A,low,p-1)
        QUICK-SORY(A,p+1,high)

  
#选择数组的第一个元素作为基准
Pratition(A,low,high)
    pivot = A[low]
    i = low 
    for j = low + 1 to high
        do if A[j] <= pivot
            then i = i + 1
                 exchange A[i] and A[j]
    exchange A[i] with A[low]
    return i
#选择数组的最后一个元素作为基准
Pratition(A,low,high)
    pivot = A[high]
    i = low 
    for j = low+1 to high
        if A[j] <= pivot
            i = i + 1
            exchange A[i] and A[j]
    exchange A[i+1] with A[high]
    return i 
#另一种方法
Pratition(A,low,high)
    pivot = A[low]
    while(low < high) then
        while(A[high] >= pivot) then
            high --;
        Swap(A,high,low)
        while(A[low] <= pivot) then
            low ++;
        Swap(A,low,high)
    return low   

Swap(A,low,high)
    tmp = A[low]  
    A[low] = A[high]
    A[high] = tmp

JAVA代码

  
public static void main(String[] args) {
	int[] array = { 9, 2, 4, 0, 4, 1, 3, 5 };
	quickSort(array, 0, array.length - 1);
	printArray(array);
}

/**
 * 快速排序
 * 
 * @param array
 *            待排序数组
 * @param start
 *            待排序子数组的起始索引
 * @param end
 *            待排序子数组的结束索引
 */
public static void quickSort(int[] array, int start, int end) {
	if (start < end) {
		int position = partition(array, start, end);
		quickSort(array, start, position - 1);
		quickSort(array, position + 1, end);
	}
}

/**
 * 重排array，并找出“临界”位置的索引
 * 
 * @param array
 *            待重排数组
 * @param start
 *            待重排子数组的起始索引
 * @param end
 *            待重排子数组的结束索引
 * @return
 */
public static int partition(int[] array, int start, int end) {
	int position = start - 1;
	int base = array[end];
	for (int i = start; i < end; i++) {
		if (array[i] <= base) {
			position++;
			int temp = array[position];
			array[position] = array[i];
			array[i] = temp;
		}
	}
	int temp = array[position + 1];
	array[position + 1] = array[end];
	array[end] = temp;
	return position + 1;
}

/**
 * 打印数组
 * 
 * @param array
 */
public static void printArray(int[] array) {
	for (int i : array) {
		System.out.print(i + "");
	}
	System.out.println();
}

随机快速排序（随机顺序or随机主元）

运行时间不依赖与输入序列的顺序

伪代码

  
RandomizedQuickSort(A, low, high)
    if low < high
        pivotIndex = Random(low, high)        # 随机选择一个索引在 [low, high] 范围内
        exchange A[low] and A[pivotIndex]     # 交换随机选择的元素与A[low]
        pivotNew = Partition(A, low, high)    # 使用原Partition函数进行分割
        RandomizedQuickSort(A, low, pivotNew - 1)   # 递归排序左子数组
        RandomizedQuickSort(A, pivotNew + 1, high)  # 递归排序右子数组

线性时间排序 $Θ(nlgn)$

只通过比较（大于，小于，等于）决定排序顺序

Counting Sort 计数排序 O(k+n)

  
COUNTING-SORT(A, n, k)
    let B[1:n], C[0:k] be new arrays
    for i = 1 to k
        do C[i] = 0 //C[i]用于记录某些数值出现的频率
    for j = 1 to n
        do C[A[j]] = C[A[j]] + 1 //递增表示A[j]的计数值
    // C[i] 给出等于数值i的元素的数量.
    for i = 1 to k
        do C[i] = C[i] + C[i - 1] 
    // C[i] now contains the number of elements less than or equal to i.
    // Copy A to B, starting from the end of A
    for j = n downto 1
        do B[C[A[j]]] = A[j]
        do C[A[j]] = C[A[j]] - 1 // to handle duplicate values

Radix sort 基数排序 O(n)

线性时间内处理大规模排序

  
RADIX-SORT(A, n, d)
    for i = 1 to d
        use a stable sort to sort array A[1:n] on digit i
    #RADIX-SORT并没有指明其中使用的稳定排序是什么，一般使用COUNTING-SORT。

Bucket sort 桶排序 O(n)

桶排序假设输入数据服从均匀分布。假设输入数据均匀独立分布在区间[0,1)上，桶排序将区间[0,1)分成n个大小相等的子区间，称这些子区间为桶(bucket)。

  
BUCKET-SORT(A, n)
    let B[0 : n - 1] be a new array
    for i = 0 to n - 1
        make B[i] an empty list
    for i = 1 to n
        insert A[i] into list B[⌊n · A[i]⌋]
    for i = 0 to n - 1
        sort list B[i] with insertion sort
    concatenate the lists B[0], B[1], ... , B[n - 1] together in order
    return the concatenated lists

课后题

查找问题(searching problem)

  
LINEAR-SEARCH(A,n,x)
    for i<-1 to n
        if x == A[i]
            return i
    return NIL

插入排序按升序

  
INSERTION-SORT(A,n)
    for j=2 to n
        do key = A[j]
            i = j - 1
            while i > 0 and A[i] < key
                do A[i+1] = A[i]
                    i = i - 1
                A[i+1] = key

哪些是稳定排序？

计数排序、

算法分析--排序算法

Problem sorting 排序算法

Insertion sort 插入排序 $Θ(n^2)$

排序步骤：

伪代码

java实现

(分治法) Merge sort 归并排序 $Θ(nlgn)$

递归式

伪代码

java实现

(分治法) Qucik sort 快速排序 $Θ(nlgn)$

伪代码

JAVA代码

随机快速排序（随机顺序or随机主元）

伪代码

线性时间排序 $Θ(nlgn)$

Counting Sort 计数排序 O(k+n)

Radix sort 基数排序 O(n)

Bucket sort 桶排序 O(n)

课后题

查找问题(searching problem)

插入排序按升序

哪些是稳定排序？

Further Reading

算法分析--基础知识

算法分析--顺序统计量

算法分析--哈希表