排序

堆排序

在排序算法中使用的是最大堆，最小堆通常在构造优先序列时使用。

保持堆的性质

  1. MAX-HEAPIFY(A,i)
  2. l=left(i);
  3. r=right(i);
  4. if l<=heap-size[A] and A[l]>A[i]
  5.     then largest = l
  6. else largest = i;
  7.     if r<=heap-size[A] and A[r]>A[largest]
  8.         then largest = r
  9. if(largest!=r)
  10.     then exchange A[i],A[largest]
  11.     Max-Heapify(A,largest)

建堆

可以自底而上地用MAX-HEAPIFY来将一个数组A[1…n]变成最大堆。

BUILD-MAX-HEAP(A)
heap-size[A] = length[A]
for i = length(A)/2 向上取整 downto 1
    do MAX-HEAPIFY(A,i)

堆排序算法

HEAPSORT(A)
BUILD-MAX-HEAP(A)
for i=length(A) down to 2
    do swap(A,l,i)
  heap-size[A] = heap-size[A]-1
  MAX-HEAPIFY(A,l)

线性时间排序

How Fast can we sort? depends on model of what you can do with the elements!
目前学习的插入排序、归并排序、快速排序以及堆排序都是基于 比较排序** **的算法。

排序算法的下界

比较排序可以被抽象地视为决策树。一棵决策树是一棵满二叉树，表示某排序算法作用于给定输入所作的所有比较，而控制结构、数据移动等都被忽略了。
Comparision Sorting: only use comparisons to determine the relative order of elements.
Runing time(#Comparisons)=length of path
Worst-case running time = height of tree
Lower bound on decision-tree sorting:
Any decision-tree sorting n elements has the height Day 5 - 图1

计数排序

基本思想 对每一个输入元素x，确定出小于x的元素个数。
前提 n个输入元素中的每一个都是0到k之间的整数。
在计数排序算法的代码中，我们假定输入是n个数的数组A，存放排序结果的B，以及提供临时存储区的C（0…k）

public void countingSort(int[] A, int[] B, k){
    //初始化
    int n = A.length;
    int[] C = new int[k];
    for(int i=0; i<n; i++){
        C[A[i]] = C[A[i]]+1;
    }
    for(int i=1; i<k; i++){
        C[i] = C[i-1]+C[i];
    }
    for(int i=n-1; i>=0; i--){
        B[C[A[i]]] = A[i];
        C[A[i]] = C[A[i]]-1;
    }
}

T(n) = Θ(n+k)

基数排序（Hallerith 1890）

从低位向高位依次排序， 要求按位排序要稳定
定理：给定n个d位数，每一个数位可以取k种可能的值，基数排序算法能以Θ(d(n+k))的时间正确地对这些数排序

桶排序

当 桶排序 的输入符合均匀分布时，既可以实现线性时间运行。与计数排序类似，桶排序也对输入作了某种假设，因而运行很快：计数排序假设 输入是一个由小范围内的整数构成 ，而桶排序则假设 输入有一个随机过程产生 ，该过程将元素均匀地分布在区间[0,1]上。

public static void bucketSort(int[] arr){
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for(int i = 0; i < arr.length; i++){
        max = Math.max(max, arr[i]);
        min = Math.min(min, arr[i]);
    }
    //桶数
    int bucketNum = (max - min) / arr.length + 1;
    ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
    for(int i = 0; i < bucketNum; i++){
        bucketArr.add(new ArrayList<Integer>());
    }
    //将每个元素放入桶
    for(int i = 0; i < arr.length; i++){
        int num = (arr[i] - min) / (arr.length);
        bucketArr.get(num).add(arr[i]);
    }
    //对每个桶进行排序
    for(int i = 0; i < bucketArr.size(); i++){
        Collections.sort(bucketArr.get(i));
    }
    System.out.println(bucketArr.toString());
}