Sort Integers II

Given an integer array, sort it in ascending order. Use quick sort, merge sort, heap sort or any O(nlogn) algorithm.

分析

Quick Sort

index 0 1 2 3 4 5 6 7 8 9 10 11 12 13

A(key=3)4 1 2 1 5 1 3 2 3 6 2 1 4 3

1 3 1 2 1 5 1 3 2 3 6 2 1 4 4

2 3 1 2 1 1 1 3 2 3 6 2 5 4 4

3 3 1 2 1 1 1 3 2 3 6 2 5 4 4

j i

public class Solution {
    /**
     * @param A an integer array
     * @return void
     */
    public void sortIntegers2(int[] A) {
        // Write your code here
        quickSortHelper(A, 0, A.length - 1);
    }
    private void quickSortHelper(int[] A, int left, int right) {
        if(left >= right)
            return;
        int i = left, j = right;
        int key = A[left + (right - left) / 2];
        while(i <= j){
            while(i <= j && A[i] < key) ++i;
            while(i <= j && A[j] > key) --j;
            if(i <= j){
                int tmp = A[i];
                A[i++] = A[j];
                A[j--] = tmp;
            }
        }
        quickSortHelper(A, left, j);
        quickSortHelper(A, i, right);
    }
}

Merge Sort

public class Solution {
    /**
     * @param A an integer array
     * @return void
     */
    public void sortIntegers2(int[] A) {
        // Write your code here
        int[] tmp = new int[A.length];
        mergeSortHelper(A, tmp, 0, A.length - 1);
    }
    private void mergeSortHelper(int[] A, int[] tmp, int left, int right) {
        if(left >= right) return;
        int mid = left + (right - left) >> 1;
        mergeSortHelper(A, tmp, left, mid);
        mergeSortHelper(A, tmp, mid + 1, right);
        merge(A, tmp, left, mid, right);
    }
     
    private void merge(int[] A, int[] tmp, int left, int mid, int right){
        int i = left, j = mid + 1, index = left;
        while(i <= mid || j <= right){
            int a, b, min;
            a = (i <= mid) ?A[i] : Integer.MAX_VALUE;
            b = (j <= right) ? A[j] : Integer.MAX_VALUE;
            min = (a <= b) ?A[i++] : A[j++];
            tmp[index++] = min;
        }
        for(int k = left; k <= right; k++){
            A[k] = tmp[k];
        }
    }
}

null