目录
一、快速排序
1、partition操作分析
0）首先如果区间内只有一个元素 那我们默认是有序的
1）从区间内（区间不代表整个数组，而是指[from,to]的数组片段）挑选一个privot，挑选方式随意
2) 遍历区间，每个元素都要和privot比较，小于等于privot的放左边，大于等于privot的放右边，区间遍历完成后数组被分为三部分 整个过程我们称之为parttion
3）递归地对左右区间进行parttion
ques：为什么这样的操作就可以使得数组有序？
ans：我们每次parttion都会确定privot的最终位置，相当于排序了一个元素，递归的处理就可以让每个元素都放在自己该放的位置，进而使得数组有序
ques：partition==快排？
ans：parttion不是快排，他只是快排中的一个步骤
2、partition之Hoare划分：
老规矩先上图：
hoare划分又被叫做左右指针法：
1）首先选一个基准值temp（一般来说不是最左就是左右）这里我们取左
2）定义指针left和right，left从左往右，找到比temp大的元素停下，right从右往左，找到比temp小的元素停下 此时left和right交换，继续寻找
3）直到left和right相遇，此时temp和left或者right交换即可
这里有一个小技巧，如果选取 左边为temp，就要right先动，如果选取右边为temp，就要left先动
为什么？
首先举一个反例：
数组【0，1，2，3，4】
我们选取0为temp，然后left从左往右，直到下标为3时和right相遇，此时交换0和4，数组排序错误
其次是我个人的理解：
在我们最后交换相遇点和最左边的值时，temp被交换到左边，为什么我们可以保证这个点一定小于temp呢？
正是因为right先动！
right停下来只有两种可能：
1）temp找到了一个小于temp的元素所以停下来
2）temp遇到了left，而left由于后动，所以left上的值是严格小于等于temp的
为什么left一定严格小于等于temp？
两种可能：
1）left没动过，那么left就是temp
2）left动过，而由于left和right交换过，所以left当前的值一定小于temp
代码如下：
private static int partition(long[] nums, int start, int end) {
long temp=nums[start];
int left=start;//left的初始位置
int right=end;//right的初始位置
while (left<right){//循环的条件，left==right时退出
while (nums[right]>=temp&&left<right){
right--;
}
while (nums[left]<=temp&&left<right){//为什么多加了一个left<right
left++; //因为我们循环的过程中left和right在不断变化，有可能不满足大的循环条件
}//两个循环结束，找到了一大一小进行交换
swap(nums,left,right);
}
//大的循环退出说明left和right相遇，交换temp和left即可
swap(nums,start,left);
return right;//其实返回left和right都可以
}
private void swap(int[] nums, int left, int randomIndex) {
int temp=nums[left];
nums[left]=nums[randomIndex];
nums[randomIndex]=temp;
}3、parttion之挖坑法
上图：
1）还是选择基准值，我们依旧选择左边，用变量temp保存基准值，并在原temp位置留下一个坑
2） 定义指针left和right，right先动，找到一个比temp小的元素，把这个元素入坑，然后在right的位置上留下一个坑，此时left开始动，找到一个大于temp的元素入坑，left开始作为坑 动right
3）如此循环往复，直到left和right相遇，把temp入坑
挖坑法代码实现：
private static int partition(long[] nums, int start, int end) {
long temp=nums[start];//基准值的选取
int left=start;
int right=end;
while (left<right){
while (nums[right]>=temp&&left<right){
right--;
}
swap(nums,left,right);//right填坑
while (nums[left]<=temp&&left<right){
left++;
}
swap(nums,left,right);//left填坑
}
nums[left]=temp;//最后temp填坑
return left;
}
private void swap(int[] nums, int left, int randomIndex) {
int temp=nums[left];
nums[left]=nums[randomIndex];
nums[randomIndex]=temp;
}4、parttition之前后指针法
我们首先定义一个指针s和指针i
做如下定义：
[start，s)? ? ?<=temp
[s,i)? ? ? ? ? ? >=temp
[i,end)? ? ? ? 还没有比较过的元素
我们首先选取最后一个元素为temp，然后指针i不断向后移动，如果当前元素小于temp，交换nums【s】和nums【i】，s++（因为s之前的元素必须都是小于temp的）? 如果大于 等于s不动，i还是继续++，直到i等于end
交换s和temp，由于s之前严格小于temp，所以我们经过一次parttion能够确定temp的最终位置
代码实现：
private static int partition(long[] nums, int start, int end) {
long temp=nums[end];
int s=start;
for (int i=start;i<end;i++){
if (nums[i]<temp){
swap(nums,i,s);
s++;
}
}
swap(nums,end,s);
return s;
}
private void swap(int[] nums, int left, int randomIndex) {
int temp=nums[left];
nums[left]=nums[randomIndex];
nums[randomIndex]=temp;
}5、快速排序代码实现及其优化：
有了parttion操作，快速排序就很简单了，只需要递归的使用怕parttiion方法，确定每一个小区间即可
public static void quickSort(long[] nums,int left,int right){
if (left>=right){
return ;
}
int privot=partition(nums,left,right);
quickSort(nums,left,privot-1);
quickSort(nums,privot+1,right);
}但是我们思考：如果一开始地选取privot的操作选的是最小或者最大值，那么我们每次费尽千辛万苦只能确定privot的一侧，这就会造成递归树倾斜，使得时间复杂度为O(N^2)
因此我们对已有的快排进行优化：
1）在待排序元素较少的情况下，插排的效率是很高的，因此我们可以在元素数量到达某一个临界点时就采用插入排序
2）parttion算法优化：1、找到==privot的值，下次分割时跳过这些相等的数
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2、三指针，分别记录数组中? 左 ，中，右，三个下标，找到数值大小中间的元素，作为基准值 ，我们就可以有效避免待排序数组有序或者逆序这种最差情况
选取priovt的操作很多人都采用了随机生成数字的方式，但由于生成随机数的代价本身就很高，我们采用三数取中更为便捷！
private static int partition(long[] nums, int start, int end) {
int left=start;
int right=end;
int mid=left+(right-left)/2;
if ((nums[left]<=nums[mid]&&nums[mid]<=nums[right])||(nums[right]<=nums[mid]&&nums[mid]<=nums[left])){
swap(nums,right,mid);
}
if ((nums[mid]<=nums[left]&&nums[left]<=nums[right])||(nums[right]<=nums[left]&&nums[left]<=nums[mid])){
swap(nums,left,right);
}
// if ((nums[mid]<=nums[right]&&nums[right]<=nums[left])||(nums[left]<=nums[right]&&nums[right]<=nums[mid])){
// swap();
// }
long temp=nums[end];
int s=start;
for (int i=start;i<end;i++){
if (nums[i]<temp){
swap(nums,i,s);
s++;
}
}
swap(nums,end,s);
return s;
}6、快速排序时间性能分析
?
空间复杂度关乎递归树的高度
最好是logn? 最差是 n
二、归并排序
归并排序的本质也是一种分治算法
把一个大区间分为两个小区间，如果让两个小区间分别有序，那我们就可以通过合并数组的方式使之全部有序
?合并两个数组：
? 完整代码：
public static void mergeSort(long nums[],int start,int end){
if (start==end){//只有一个元素，默认有序
return;
}
int left=start;
int right=end;
int mid=left+((right-left)>>1);
mergeSort(nums,left,mid);
mergeSort(nums,mid+1,end);
merge(nums,left,mid,right);
}
private static void merge(long[] nums, int l, int mid, int r) {
int p1=l;
int p2=mid+1;
int i=0;
long[] help=new long[r-l+1];//新数组长度等于原来两数组长度之和
while (p1<=mid&&p2<=r){
help[i++]=nums[p1]<=nums[p2]?nums[p1++]:nums[p2++];
}
//一个数组取完了
while (p1<=mid){
help[i++]=nums[p1++];
}
while (p2<=r){
help[i++]=nums[p2++];
}//最后把这个数组的值再赋给原数组
for (int j=0;j<i;j++){
nums[l+j]=help[j];
}
}