1.经典快排

分析

思路和荷兰国旗问题中的预备题目一样。
1.首先在数组[l,r]中把最后一个元素作为num进行比较，得到两段区域，分别为小于等于最后一个数的区域和大于最后一个数的区域。
2.在上述第一段区域内，最后一个数的值为num保留不动，倒数第二个数重新命名为num，接着继续比较，不断迭代。
3.在上述1的第二段区域内，把最后一个数命名为num，接着继续比较，不断迭代。
4.迭代继续的条件是if(l<r)

核心代码

1.排序部分
返回值为x-1：返回小于等于范围内倒数第二个位置的位置，最后一个位置就是原来的num，下次直接用倒数第二个位置作为下一次的num。

int partition(int arr[],int l,int r)
{int num = arr[r];	//把最后一个数设为num进行比较int x = l-1;		    //x为小于等于的区域，设为区域之前一个位置int cur = l;		    //cur是当前遍历的指针while(cur < r+1)	//遍历所有位置{if(arr[cur]<=num){swap(arr[cur++],arr[++x]);}elsecur++;}return x-1;			}```
2.迭代部分
迭代的条件是在[l,r]范围内，如果越界表示不可继续分
```cpp
void quicksort(int arr[],int l,int r)
{if(l<r){int a = partition(arr,l,r);quicksort(arr,l,a);quicksort(arr,a+1,r);}
}

完整代码

#include<iostream>
#include<time.h>
#define length 10
using namespace std;//交换函数
void swap(int &a,int &b)
{int temp = a;a = b;b = temp;
}int partition(int arr[],int l,int r)
{int num = arr[r];	//把最后一个数设为num进行比较int x = l-1;		//x为小于等于的区域，设为区域之前一个位置int cur = l;		//cur是当前遍历的指针while(cur < r+1)	//遍历所有位置{if(arr[cur]<=num){swap(arr[cur++],arr[++x]);}elsecur++;}return x-1;			
}void quicksort(int arr[],int l,int r)
{if(l<r){int a = partition(arr,l,r);quicksort(arr,l,a);quicksort(arr,a+1,r);}
}int main()
{//准备随机数组int arr[length] ;srand((unsigned)time(NULL));cout<<"arr = ";for(int i = 0;i < length;i++){arr[i] = rand()%10;cout<<arr[i]<<" ";}cout<<endl;//意外情况直接返回(本题用不到)if (arr == NULL || length < 2) {return 0 ;}//核心quicksort(arr,0,length - 1);//结果输出cout<<"arr = ";for(int i = 0;i<length;i++){cout<<arr[i]<<" ";}cout<<endl;system("pause");return 0 ;
}

2.荷兰国旗改进的经典快排

分析

经典快排的缺点：每次只找出一个num进行排序，如果存在多个相同值的num还需要继续划分，多做了无用功。考虑如果使用荷兰国旗的排序方法，将相同的num一次找出来，那么时间复杂度的常数时间就可以缩短。

核心代码

荷兰国旗问题需要有两个指针记录小于num的范围和大于num的范围，考虑定义一个长度为2的数组记录下来，返回数组的指针用作下一步。

void quicksort(int arr[],int l,int r)
{int a[2] = {0};if(l<r){int *p = paitition(arr,l,r,a);quicksort(arr,l,*p);quicksort(arr,*(p+1),r);}
}

int* paitition(int arr[],int l,int r,int a[])
{int x = l-1;int y = r+1;int cur = l;int num = arr[r];while(cur<y){if(arr[cur]<num){swap(arr[cur++],arr[++x]);}else if(arr[cur]>num){swap(arr[cur],arr[--y]);}else{cur++;}}a[0] = x;a[1] = y;return a;
}

完整代码

#include<iostream>
#include<time.h>
#define length 20
using namespace std;void swap(int &a,int &b)
{int temp = a;a = b;b = temp;
}int* paitition(int arr[],int l,int r,int a[])
{int x = l-1;int y = r+1;int cur = l;int num = arr[r];while(cur<y){if(arr[cur]<num){swap(arr[cur++],arr[++x]);}else if(arr[cur]>num){swap(arr[cur],arr[--y]);}else{cur++;}}a[0] = x;a[1] = y;return a;
}void quicksort(int arr[],int l,int r)
{int a[2] = {0};if(l<r){int *p = paitition(arr,l,r,a);quicksort(arr,l,*p);quicksort(arr,*(p+1),r);}
}int main()
{//生成随机数组int arr[length];srand((unsigned)time(NULL));cout<<"arr = ";for(int i = 0;i<length;i++){arr[i] = rand()%10;cout<<arr[i]<<" ";}cout<<endl;quicksort(arr,0,length - 1);//打印结果cout<<"arr1 = ";for(int i = 0;i<length;i++){cout<<arr[i]<<" ";}cout<<endl;system("pause");return 0;
}

3.随机快排

分析

荷兰国旗改进的经典快排缺点在于使用最后一个数作为num，例如[1,2，3,4,5,6]中复杂度就很高，因为此时复杂度就与数据状况有关了。
考虑：在数组中随机选一个数作为num，这样就可以绕开原始数据状况，复杂度变成长期的期望值。

核心代码

就一句num值使用随机初始化

int num = arr[l+rand()%(r-l+1)];

完整代码

#include<iostream>
#include<time.h>
#define length 20using namespace std;
void swap(int &a,int &b)
{int temp = a;a = b;b = temp;
}int* paitition(int arr[],int l,int r,int a[])
{int x = l-1;int y = r+1;int cur = l;int num = arr[l+rand()%(r-l+1)];while(cur<y){if(arr[cur]<num){swap(arr[cur++],arr[++x]);}else if(arr[cur]>num){swap(arr[cur],arr[--y]);}else{cur++;}}a[0] = x;a[1] = y;return a;
}void quicksort(int arr[],int l,int r)
{int a[2] = {0};if(l<r){int *p = paitition(arr,l,r,a);quicksort(arr,l,*p);quicksort(arr,*(p+1),r);}
}int main()
{//生成随机数组int arr[length];srand((unsigned)time(NULL));cout<<"arr = ";for(int i = 0;i<length;i++){arr[i] = rand()%100;cout<<arr[i]<<" ";}cout<<endl;quicksort(arr,0,length - 1);//打印结果cout<<"arr1 = ";for(int i = 0;i<length;i++){cout<<arr[i]<<" ";}cout<<endl;system("pause");return 0;
}

复杂度分析

时间复杂度为度O(NlogN)，额外空间复杂度O(logN)
1.对于长期选择来说，随机成中间的值可能性最大，分治思想T(n) = 2T(N/2) + O(n)，时间复杂度为度O(NlogN)。
2.随机查找时，二分多少次多少个断点，最好情况O(logN)，最差为O(N），概率上长期为O(logN)。