排序方法总结

1、冒泡排序法

思想：两重循环，相邻依次比较，满足大或者小（视乎从大到小还是从小到大）则交换值，直到外循环结束

        int n = nums.length;
        int temp = 0;
        for (int i = 0; i < n; i++) {
            for (int j = n - 1; j > i; j--) {
                if (nums[j - 1] < nums[j]) {
                    temp = nums[j - 1];
                    nums[j - 1] = nums[j];
                    nums[j] = temp;
                }
            }
        }

2、选择排序法

思想：两重循环，还是相邻比较，但满足条件也不马上交换，而是把下标记录，直到内循环中获得最小（大）的下标才进行交换，比冒泡快一点点

        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            int max = i;
            for (int j = i + 1; j < n; j++) {
                if (nums[max] < nums[j]) {
                    max = j;
                }
            }
            int temp = nums[i];
            nums[i] = nums[max];
            nums[max] = temp;
        }

3、快速排序

思想：(从整体到局部) 1、选参考点（一般为中点pivot）2、partition 就是两根指针算法交换 3、divide conquer 继续把两边的排序

warn：判断条件一定是left <= right 避免递归的时候两个部分有交集 而A[left] < pivot

public class Solution {
    /**
     * @param A an integer array
     * @return void
     */
    public void sortIntegers2(int[] A) {
        if (A == null || A.length == 0) {
            return;
        }
        quickSort(A, 0, A.length - 1);
    }
    private void quickSort(int[] A, int start, int end) {
        if (start >= end) {
            return;
        }
        int left = start, right = end;
        // mid point
        int pivot = A[(start + end) / 2];
        //partition
        while (left <= right) {
            while (left <= right && A[left] < pivot) {
                left++;
            }
            while (left <= right && A[right] > pivot) {
                right--;
            }
            if (left <= right) {
                int temp = A[left];
                A[left] = A[right];
                A[right] = temp;
                left++;
                right--;
            }
        }
        //divide conquer right < left
        quickSort(A, start, right);
        quickSort(A, left, end);
    }
}

2017-03-24

4、归并排序

思想：(从局部到整体) 1、开额外空间（与原数组一样长） 2、先divide conquer到两个数组 3、递归到最终两数组是有序的，所以进行一次merge two sorted array

warn：注意下标的选取

public class Solution {
    /**
     * @param A an integer array
     * @return void
     */
    public void sortIntegers2(int[] A) {
        if (A == null || A.length == 0) {
            return;
        }
        // O(n) extra space
        int[] temp = new int[A.length];
        mergeSort(A, 0, A.length - 1, temp);
    }
    private void mergeSort(int[] A, int start, int end, int[] temp) {
        if (start >= end) {
            return;
        }
        // divide conquer to two arrays
        mergeSort(A, start, (start + end) / 2, temp);
        mergeSort(A, (start + end) / 2 + 1, end, temp);
        //merge two sorted array
        mergeArray(A, start, end, temp);
    }
    private void mergeArray(int[] A, int start, int end, int[] temp) {
        // left array start point
        int leftIndex = start;
        int midIndex = (start + end) / 2;
        // right array start point
        int rightIndex = midIndex + 1;
        // temp array start point
        int index = start;
        while (leftIndex <= midIndex && rightIndex <= end) {
            if (A[leftIndex] < A[rightIndex]) {
                temp[index++] = A[leftIndex++];
            } else {
                temp[index++] = A[rightIndex++];
            }
        }
        while (leftIndex <= midIndex) {
            temp[index++] = A[leftIndex++];
        }
        while (rightIndex <= end) {
            temp[index++] = A[rightIndex++];
        }
        for (int i = start; i <= end; i++) {
            A[i] = temp[i];
        }
    }
}

2017-03-24