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];
}
}
}
