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,
-
max-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);
}
}
