1. HeapSort

1.1 Heaps

1. Conceptions

• length: the number of elements in the array A
• Heap size: valid elements in the array A

• Index
  

  

• heap property

  • max-heap: for every node other than the root,
  • min-heap: for every node other than the root,

• runs in time

• runs in linear time

• runs in time

• The, , , and procedures, which run in time, allow the heap data structure to implement a priority queue.

1.2 Maintaining the heap property

• 假设左子树和右子树都是满足性质

[算法] MAX-HEAPIFY最坏情况下子树大小2n/3的由来

public class MaxHeapify {

    private static void maxHeapify(int[] array, int root) {
        int left = left(root);
        int right = right(root);
        int largest = root;
        System.out.println("root is" + array[root]+ "left is " +left + "right is " + right);
        // compare the right and the root value
        if(left < array.length && array[left] > array[root]) {
            largest = left;
        }
        if(right < array.length && array[right] > array[largest]) {
            largest = right;
        }
        if(largest != root) {
            int temp = array[largest];
            array[largest] = array[root];
            array[root] = temp;
            maxHeapify(array, largest);
        }
    }

    private static void buildMaxHeap(int[] array) {
        for (int i = array.length / 2; i >= 1; i --) {
            maxHeapify(array, i);
        }
    }

    private static void heapSort(int[] array) {
        buildMaxHeap(array);
        for(int i = array.length - 1; i >= 1; i --) {
            int temp = array[i];
            array[i] = array[1];
            array[1] = temp;
            maxHeapify(array, 1);
        }
    }

    private static void swapTree(int[] array, int root) {
        System.out.println(root);
        int left = left(root);
        int right = right(root);
        if(root >= array.length|| left >= array.length - 1 || right >= array.length - 1) {
            return;
        }
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;

        swapTree(array, left);
        swapTree(array, right);
    }

    private static int parent(int root) {
        return Integer.valueOf(String.valueOf(Math.floor(root / 2)));
    }

    private static int right(int root) {
        return left(root) + 1;
    }

    private static int left(int i) {
        return 2 * i;
    }
    public static void main(String[] args) {
        int[] array = new int[]{0,3,4,2,3,2,1,5,2,1}; //头部的0是填充数据的

        heapSort(array);

        for(int i : array) {
            System.out.println(i);
        }
    }
}

2. Quick Sort

Worst-case Running Time:
Expected Running Time:

public class QuickSort {
    private static void quickSort(int[] array, int p, int r) {

        if(p < r) {
            int q = partition(array, p, r);
            quickSort(array, p, q - 1);
            quickSort(array, q + 1, r);
        }
    }

    private static int partition(int[] array, int p, int r) {
        int i = p - 1; //边界线
        int target = array[r]; //以array[r]当作比较值
        for(int j = p; j <= r - 1; j ++) {
            if(array[j] <= target) {
                i = i + 1;
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        array[r] = array[i + 1];
        array[i + 1] = target;

        return i + 1;
    }

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

        for(int i : array) {
            System.out.println(i);
        }
    }
}

2.1 Performance of Quick Sort

balanced or unbalanced determines its performance

• Running time is whenever the split has constant propotionality

2.2 Randomized Quick Sort

3. Sorting in Linear Time

3.1 Lower Bounds for Sorting

• all comparisons have the form

The decision-tree model

3.2 Counting Sort

public class CountingSort {
    private static int[] countingSort(int[] array, int max) {
        int[] C = new int[max];
        int[] ret = new int[array.length + 1];
        for (int i = 0; i < C.length; i ++) {
            C[i] = 0;
        }
        for (int j = 0; j < C.length; j ++) {
            C[array[j]] = C[array[j]] + 1;
        }

        for(int k = 1; k < C.length; k ++) {
            C[k] += C[k-1];
        }
        for(int m = C.length - 1; m >= 0; m--) {
            ret[C[array[m]]] = array[m];
            C[array[m]] -= 1;
        }

        return ret;
    }
    public static void main(String[] args) {
        int[] array = new int[]{2,3,1,4,3};
        int[] ret = countingSort(array, 5);

        for(int i : ret) {
            System.out.println(i);
        }
    }
}

3.3 Bucket Sort

public class BucketSort {
    private static int[][] bucketSort(int[] array) {
        int[][] retArray = new int[10][];
        for(int i = 0; i < array.length; i ++) {
            retArray[i] = new int[10];
        }
        for(int j = 0; j < array.length; j ++) {
            int[] n = retArray[(int) Math.floor(array[j])];
            for(int k = 0; k < n.length; k ++) {
                if(n[k] != 0) {
                    continue;
                } else{
                    n[k] = array[j];
                    break;
                }
            }
        }

        return retArray;
    }
    public static void main(String[] args) {
        int[] array = new int[]{2,3,1,4,3};
        int[][] retArray = bucketSort(array);
        for (int[] i: retArray) {
            for(int j: i) {
                System.out.println(j);
            }
        }
    }
}

3.4 Medians and Order Statistics

public class RandomSelect {
    private static int randomSelect(int[] array, int p, int r, int i){
        if(p == r) {
            return array[p];
        }
        int q = QuickSort.partition(array, p, r);
        int k = q - p + 1;
        if(i == k) {
            return array[q];
        }
        else if(i < k) {
            return randomSelect(array, p, q - 1, i);
        } else {
            return randomSelect(array, q + 1, r, i - k);
        }

    }
    public static void main(String[] args) {
        int[] array = new int[]{2,3,1,4,3};
        int k = randomSelect(array, 0, array.length - 1, 2);

        for(int i : array) {
            System.out.println(i);
        }

        System.out.println(k);
    }
}