quickSort AND mergeSort AND quic

quickSort
快排在于一次把所有【大于pivot的值和小于pivot的值】都交换了，所以要用到while，用left和right指针控制交换的元素

public class Solution {

    public void sortIntegers2(int[] A) {
        // write your code here
        if (A == null || A.length == 0) {
            return;
        }
        quickSort(A, 0, A.length - 1);
    }
    
    private void quickSort(int[] A, int start, int end) {
        //递归出口 没有这个会爆栈，因为出不来了
        //注意是 >=, 其实>在quickSort里也可以因为是left++,right--是一个一个移动的
        //而mergeSort用mid = (start + end) / 2控制，涉及了舍位
        if (start >= end) {
            return;
        }
        
        int left = start;
        int right = end;
        int pivot = A[(start + end) / 2];
        //  pivot两边等于也要交换，避免效率低下
        while (left <= right) {
            while (left <= right && A[left] < pivot) {
                left++;
            }
            while (left <= right && A[right] > pivot) {
                right--;
            }
            //时刻记住left <= right，而且是if条件，因为经过上面的while loop,两个交错是很有可能
            if (left <= right) {
                int temp = A[left];
                A[left] = A[right];
                A[right] = temp;
                left++;
                right--;
            }
        }
        
        quickSort(A, start, right);
        quickSort(A, left, end);
    }
}

quickSeleck(找第K大元素)

class Solution {
    /*
     * @param k : description of k
     * @param nums : array of nums
     * @return: description of return
     */
    public int kthLargestElement(int k, int[] nums) {
        // qucik select
        if (nums == null || nums.length < k) {
            return 0;
        }
        //nums.length的话数组越界
        return quickSelect(nums, 0, nums.length - 1, k);
    }
    
    private int quickSelect(int[] nums, int start, int end, int k) {
        //出口
        if (start == end) {
            return nums[start];
        }
        
        int i = start, j = end;
        int pivot = nums[(start + end) / 2];
        //当这个循环退出的时候一定是i > j
        while (i <= j) {
            while (i <= j && nums[i] > pivot) {
                i++;
            }
            while (i <=j && nums[j] < pivot) {
                j--;
            }
            if (i <= j) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                i++;
                j--;
            }
        }
        //这里这里，从while循环出来时，j < i 了
        //.....j?i....OR .....ji.....
        //j和i中间有可能有 有可能没有
        //这里的k - 1是带数带出来的假设start = j,都进这个条件了，肯定是找这个区间第一大的数，即k = 1，但是start + k = j的话,左右两边去掉start和j得出k = 0，与假设不符，所以说 判断条件是start + k - 1 <= j
        //还有一种（k - 1）的解释方法：因为K并不是zero-based,而start 是zero-based,所以需要k - 1; 如果k是zero-based，那么就是start + k <= j
        if (start + k - 1 <= j) {
            return quickSelect(nums, start, j, k);
        }
        if (start + k - 1 >= i) {
          //start     i
            //1234567|8
            //从1到8有（8 - 1 + 1 = 8）个数，而8前面有8 - 1 = 7个数
            
            return quickSelect(nums, i, end, k - (i - start));
        }
        //这里属于这种情况.....j?i....
        return nums[j + 1];
    }
};

mergeSort

public class Solution {
    /*
     * @param A: an integer array
     * @return: 
     */
    public void sortIntegers2(int[] A) {
        if (A == null || A.length == 0) {
            return;
        }
        
        int[] temp = new int[A.length];
        mergeSort(A, 0, A.length - 1, temp);
    }
    
    private void mergeSort(int[] A, int start, int end, int[] temp) {
        //递归出口
        //而且一定要是>=就退出, 因为用Middle控制了start和end
        //mid涉及了舍位的问题
        if (start >= end) {
            return;
        }
        //思考 为什么这里就不需要start和end赋给left和right
        int middle = (start + end) / 2;
        int right = middle + 1;
        
        mergeSort(A, start, middle, temp);
        mergeSort(A, right, end, temp);
        
        merge(A, start, end, temp);
    }
    
    private void merge(int[] A, int start, int end, int[] temp) {
        //思考 为什么这里需要start和end赋给left和right
        int left = start;
        int middle = (start + end) / 2;
        int right = middle + 1;
        //因为是递归 所以要从递归的角度考虑初始值
        int index = start;
        
        while (left <= middle && right <= end) {
            if (A[left] < A[right]) {
                temp[index++] = A[left++];
            } else {//这里包含了等于的情况
                temp[index++] = A[right++];
            }
        }
        while (left <= middle) {
            temp[index++] = A[left++];
        }
        while (right <= end) {
            temp[index++] = A[right++];
        }
        //因为是递归 所以要从递归的角度考虑赋值范围, 这里是i <= end, start和end都要copy到temp[]里面
        for (int i = start; i <= end; i++) {
            A[i] = temp[i];
        }
    }
}