Sort Integers II 464

Question

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].

Solution

quicksort，mergesort，heapsort。heapsort自己建heap的方法之后补上。

代码如下：

public class Solution {
    /**
     * @param A an integer array
     * @return void
     */
    public void sortIntegers2(int[] A) {
        // Write your code here
        if(A == null || A.length <= 1){
            return;
        }
        int n = A.length;

        //quick sort
        // quickSort(A, 0, n - 1);


        //merge sort
        // int[] temp = new int[A.length];
        // mergeSort(A, 0, n - 1, temp);


        //heap sort
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
        for(int i = 0; i < n; i++){
            heap.add(A[i]);
        }
        for(int i = 0; i < n; i++){
            A[i] = heap.poll();
        }
    }

    private void quickSort(int[] A, int start, int end){
        if(start >= end){
            return;
        }

        int pos = partition(A, start, end);
        quickSort(A, start, pos - 1);
        quickSort(A, pos + 1, end);
    }

    private int partition(int[] A, int start, int end){
        // int k = start + Math.random() * (end - start + 1);
        int pivot = A[end];
        while(start < end){
            while(start < end && A[start] <= pivot){
                start++;
            }
            A[end] = A[start];

            while(start < end && A[end] >= pivot){
                end--;
            }
            A[start] = A[end];
        }
        A[start] = pivot;
        return start;
    }

    //merge sort
    private void mergeSort(int[] A, int start, int end, int[] temp){
        if(start >= end){
            return;
        }

        int mid = (start + end) / 2;
        mergeSort(A, start, mid, temp);
        mergeSort(A, mid + 1, end, temp);
        merge(A, start, mid, end, temp);
    }

    private void merge(int[] A, int start, int mid, int end, int[] temp){
        int left = start;
        int right = mid + 1;
        int index = start;

        while(left <= mid && right <= end){
            if(A[left] < A[right]){
                temp[index++] = A[left++];
            }else{
                temp[index++] = A[right++];
            }
        }

        while(left <= mid){
            temp[index++] = A[left++];
        }

        while(right <= end){
            temp[index++] = A[right++];
        }

        for(int i = start; i <= end; i++){
            A[i] = temp[i];
        }
    }
}