Problem
Given an integer array, sort it in ascending order. Use quick sort, merge sort, heap sort or any O(nlogn) algorithm.
Example
Given [3, 2, 1, 4, 5], return [1, 2, 3, 4, 5].
Note
考察对Heap Sort, Quick Sort, Merge Sort的掌握。
Solution
Merge Sort
public class Solution { public void sortIntegers2(int[] A) { if (A.length <= 1) return; int[] B = new int[A.length]; sort(A, 0, A.length-1, B); } public void sort(int[] A, int start, int end, int[] B) { if (start >= end) return; int mid = start + (end - start) / 2; sort(A, start, mid, B); sort(A, mid+1, end, B); merge(A, start, mid, end, B); } public void merge(int[] A, int start, int mid, int end, int[] B) { int i = start, j = mid+1, index = start; while (i <= mid && right <= end) { if (A[i] < A[j]) B[index++] = A[i++]; else B[index++] = A[j++]; } while (i <= mid) B[index++] = A[i++]; while (j <= end) B[index++] = A[j++]; for (int k = start; k <= end; k++) A[k] = B[k]; }} Heap Sort
public class Solution { private static int[] a; private static int n; private static int left; private static int right; private static int largest; public void sortIntegers2(int[] A) { a = A; buildheap(a); for(int i=n;i>0;i--){ exchange(0, i); n=n-1; maxheap(a, 0); } } public static void buildheap(int []a){ n=a.length-1; for(int i=n/2;i>=0;i--){ maxheap(a,i); } } public static void maxheap(int[] a, int i){ left=2*i; right=2*i+1; if(left <= n && a[left] > a[i]){ largest=left; } else{ largest=i; } if(right <= n && a[right] > a[largest]){ largest=right; } if(largest!=i){ exchange(i,largest); maxheap(a, largest); } } public static void exchange(int i, int j){ int t=a[i]; a[i]=a[j]; a[j]=t; }} Quick Sort
public class Solution { public void sortIntegers2(int[] A) { if (A.length <= 1) return; quicksort(A, 0, A.length-1); } public void quicksort(int[] A, int start, int end) { if (start >= end) return; int mid = start+(end-start)/2; int pivot = A[mid], i = start, j = end; while (i <= j) { while (i <= j && A[i] < pivot) i++; while (i <= j && A[j] > pivot) j--; if (i <= j) { int temp = A[i]; A[i] = A[j]; A[j] = temp; i++; j--; } } quicksort(A, start, j); quicksort(A, i, end); }}