7. 快速排序
7.1 快速排序思路
快速排序的基本思想是任取待排序序列的一个元素作为中心元素(可以用第一个，最后一个，也可以是中间任何一个)，习惯将其称为pivot，枢轴元素；
将所有比枢轴元素小的放在其左边；
将所有比它大的放在其右边；
形成左右两个子表；
然后对左右两个子表再按照前面的算法进行排序，直到每个子表的元素只剩下一个。
可见快速排序用到了分而治之的思想。
将一个数组分成两个数组的方法为：
先从数组右边找到一个比枢轴元素小的元素，将数组的第一个位置赋值为该元素；
再从数组的左边找到一个比枢轴元素大的元素，将从上面取元素的位置赋值为该值；
依次进行，直到左右相遇，把枢轴元素赋值到相遇位置。
总结：快排算法可以看作是对冒泡排序的一种优化，其中采用了分而治之和递归的思想，极大的优化了时间复杂度。
7.2 视图分析
第一步：确定左右指针位置和轴心数。
第二步：分别找到左右方不符合要求的数，构建中间变量进行交换。
第三步：左指针与右指针重合或左指针大于右指针，证明第一遍寻找结束，跳出循环。
第四步：分别进入左递归和右递归。
第五步：递归结束，得到的就是正确排序。
注意：递归的左边界和右边界问题。左递归的左边界是数组的左边界，右边界是第一遍循环结束时的右指针；右递归的右边界是数组的右边界，左边界是第一遍循环结束的左指针。这样做是因为指针重合的位置已经确定，左右指针已分别错开作为下一组新数组的边界条件。
7.2 代码实现
public static int[] quickSort(int[] nums,int left,int right) {
int indexL = left; //
int indexR = right;
int pivot = nums[(indexL+indexR)/2];
int temp = 0;
while (indexL < indexR) {
while (nums[indexL] < pivot) {
indexL += 1;
}
while (nums[indexR] > pivot) {
indexR -= 1;
}
temp = nums[indexL];
nums[indexL] = nums[indexR];
nums[indexR] = temp;
if (indexL >= indexR) {
break;
}
// 有很多朋友对这个地方不太理解
// 如果交换的数与轴心数一致，但又不进行移位的话，那么一旦排序进入到最后环节，即这个数和轴心数进行排序会进入到死循环
// 为什么要对相反的指针进行移位呢？
// 如何移动己方指针，那么这个数就有可能留在己方数组，而不会移动到正确的位置。
// 这是因为重合的位置不会改变，左边的数组元素不会进入到右边，右边也不会进入到左边，跳过这个相等数就极有可能将这个数留在了错误的位置上
if (nums[indexL] == pivot) {
indexR -= 1;
System.out.println(nums[indexL]);
}
if (nums[indexR] == pivot) {
indexL += 1;
System.out.println(nums[indexR]);
}
}
if (indexL == indexR) {
indexL += 1;
indexR -= 1;
}
if (indexL < right) {
quickSort(nums,indexL,right);
}
if (left < indexR) {
quickSort(nums,left,indexR);
}
return nums;
}
8. 归并排序
8.1 归并排序介绍
归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略。
8.2 归并排序之分
8.3 归并排序之治
8.4 代码实现
public static void mergeSort(int[] nums, int left, int right, int[] temp) {
if (left < right) {
int mid = (left + right)/2;
mergeSort(nums,left,mid,temp);
mergeSort(nums,mid+1,right,temp);
merge(nums,left,mid,right,temp);
}
//return nums;
}
public static void merge(int[] nums, int left, int mid, int right, int[] temp) {
int i = left;
int j = mid+1;
int t = 0;
while (i <= mid && j <= right) {
if (nums[i] <= nums[j]) {
temp[t] = nums[i];
t += 1;
i += 1;
}else {
temp[t] = nums[j];
t += 1;
j += 1;
}
}
while (i <= mid) {
temp[t] = nums[i];
t += 1;
i += 1;
}
while (j <= right){
temp[t] = nums[j];
t += 1;
j += 1;
}
t = 0;
int tempLeft = left;
System.out.println("tempLeft=" + tempLeft + "right=" + right);
while (tempLeft <= right) {
nums[tempLeft] = temp[t];
t += 1;
tempLeft += 1;
}
}
执行结果：
可以看出代码的具体排序顺序与次数，这也验证了分治的思想，先从大分小，再从小治大。
8.5 手写分析
手写分析图也很好的证实了分治的思想与具体的递归路径。