這里討論N(logN)的常見(jiàn)算法汤纸。

• Merge Sort
• Quick Sort
• Heap Sort

輸入暫時(shí)都是整型數(shù)組 int[]

Merge sort

public class MergeSort {
    private int[] mergeSort(int[] num, int start, int end) {
        if (num == null || num.length == 0) {
            return num;
        }
        if (start >= end) {
            return new int[]{num[start]}; // divide until only one element left (return condition for recursion)
        }
        int middle = start + (end - start) / 2; // in case of: start = 1, end = Integer.MAX_VALUE, (start + end) will be out of bound
        int[] left = mergeSort(num, start, middle);
        int[] right = mergeSort(num, middle + 1, end);
        return merge(left, right);
    }
    
    private int[] merge(int[] left, int[] right) {
        int[] temp = new int[left.length + right.length];
        int i = 0, j = 0, index = 0;
        while (i < left.length && j < right.length) {
            temp[index] = Math.min(left[i], right[j]);
            if (left[i] < right[j]) {
                i++;
            } else {
                j++;
            }
            index++;
        }
        while (i < left.length) {
            temp[index++] =  left[i++];
        }
        while (j < right.length) {
            temp[index++] = right[j++];
        }
        return temp;
    }
}

注意：

1. 當(dāng)divide到只剩下一個(gè)元素的時(shí)候（start 等于 end）挽荠，返回包含此元素的一個(gè)新數(shù)組。
2. 在取middle值的時(shí)候盼樟，不要使用(start + end) / 2渤昌，請(qǐng)使用模板：start + (end - start) / 2愁铺。防止有超出Integer范圍的情況余素。

Quick sort

public class QuickSort {

    public void quickSort(int[] num) {
        if (num == null || num.length == 0) {
            return;
        }
        sort(num, 0, num.length - 1);
    }

    private void sort(int[] num, int start, int end) {
        if (start >= end) {
            return;
        }
        
        int pivot = num[end];
        int i = start;
        int j = end - 1;
        while (i < j) {
            while (num[i] <= pivot && i < j) {
                i++;
            }
            while (num[j] > pivot && i < j) {
                j--;
            }
            swap(num, i, j);
        }
        // check pivot position
        if (num[i] > pivot) {
            swap(num, i, end);
        } else {
            i++;
        }
        sort(num, start, i - 1);
        sort(num, i + 1, end);
    }
    
    private void swap(int[] num, int i, int j) {
        int temp = num[i];
        num[i] = num[j];
        num[j] = temp;
    }
    
}

Quick sort 是 in-place，而merge sort是至少要花費(fèi)O(N)的空間镜沽。
注意：

1. recursion的終止條件為start跟end相遇敏晤。
2. 左邊是比pivot小，右邊比pivot大
3. 兩個(gè)指針一個(gè) ++缅茉，一個(gè) --

Heap Sort （待續(xù)）