void Swap(int*a,int*b){ //第一种方法 int tmp=*b; *b=*a; *a=tmp; } void Swap(a,int left,int right){ //第二种方法，但是不好 int tmp=a[left]; a[left]=a[right]; a[right]=tmp; }
交换函数，避免代码重复写，导致代码冗余。（key和本文的keyi一个意思）
这里有个很重要的建议，交换还是建议拿第一个，因为换成数组有最重要的数组越界问题，而且很不容易去查看，所以一律推荐用第一个交换
//老版本快排 int Partion(int*a,int left,int right){ int keyi=left; while(left<right){ while(a[right]>=a[keyi]&&left<right){ -- right; （右边是找小，所以比他大的直接跳过） } while(a[left]<=a[keyi]&&left<right){ ++left;} Swap(&a[left],&a[right]); } Swap(&a[left],&a[keyi]); return left; }
快排排序思路
1.如果选最左边的做key，右边先走（这样会使相遇的时候数字小于key）
选择最右边做key,左边先走（相遇数字大于key）（右边做keyi，需要左边先走：为了保证相遇的时候大于keyi）
分为两个一个是L，一个是R，这里假设是左边作为key。
R先走，遇到比key小的（比key大就一直走）就停下，然后L开始走找到比Key大的就停下， 然后交换R和L，然后继续R开始继续找比他小的，然后停住，L开始走然后接着找大的，互相换位置，最后把key和a的L也就是剩下的那个，换位置。
注意一件事：上述代码一个最重要的就是：改了两天，连带问人，突然发现这里错误了
while(left<right){
while(a[right]>=a[keyi]&&left<right),因为有可能在下面这层循环中，right--和left++;
都有可能出现加冒了的情况。
Partion：这个函数是来干嘛的，我认为可以认为他是预排这种，在区间内部分有序，也就是这个一次后会变成3，1，2，5，4，6，9，7，10，8。在keyi之前都比keyi小，keyi之后都比他大。
void QuickSort(int*a,int left,int right){ if(left>=right) return ; int keyi=Partion(a,left,right); QuickSort(a, left, keyi-1); QuickSort(a, keyi+1, right); } int main(){ int a[10]={6,1,2,7,9,3,4,5,10,8}; QuickSort(a, 0, 9); for(int i=0;i<10;i++){ printf("%d",a[i]);} return 0; }
QuickSort:这个是递归，一次递归只能保证所谓的keyi在正确的位置，那么也就是我们只要保证在小区间内，分别确定好位置，也就是在多个相对有序，实现有序，先是0-9这个区间，然后
3，1，2，5，4，6，9，7，10，8 此时的keyi是5,然后是进入小区间0-4，再次进行排序
0 1 2 3 4 5 6 7 8 9 3为keyi那么，排好序的下一步结果是1，2，3，5，4
（下面的是序号） 0，1，2，3，4
也就是（此时要记住是主要的位置也就是left是0，keyi-1为1），然后将下标0-1排，3，4排，
0-1的区间右变为【0， -1】和【1，1】，然后慢慢返回。（这里说一下返回 5和4（不是下标）的情况，左边的5是keyi也是left，然后left++到了4的值，所以5和4互换。一次次的递归，这样就会使顺序变为有序。
讲讲快排的优点
1.只要你要排序的数字越乱越好，越乱越快，当keyi一直是中位数的时候最快
不断分为小区间，那么这个东西就很像我们之前的二分查找那种东西，O（n*logn)
logn层（二叉树哈）n个来调整
但是缺点也明显假如说数很整齐，图不补全了，毕竟没啥必要，切一块就明白，和没切没有区别，那就是说相当于还是一个一个排（而且用的是递归：肯定递归是比直接还是性能差那么一点，其次这么分会使递归次数太多，导致栈调用次数过多，会栈溢出。）
那么我们应该如何确保keyi一直是中位数呢：
int Middle(int*a,int left,int right){ int mid=left+(right-left)/2;//防止越界 int i=0; //非常重要的想法 int max1=a[left]>a[mid]?a[left]:a[mid]; max1=max1>a[right]?max1:a[right]; int min1=a[left]>a[mid]?a[mid]:a[left]; min1=min1>a[right]?a[right]:min1; int mid1=a[left]+a[right]+a[mid]-max1-min1; for(i=0;i<10;i++){ if(a[i]==mid1){ return i; break;} else{ continue; } } return 0; }
之前看视频中的讲解，取中太过浪费时间和消耗逻辑，不如这样，三个数相加减去最大和最小的就会剩下中间的，由于我们要求的是下标，所以要查找一下下标。然后返回相对应的下标。
这样就会尽量避免上面那种很少很少的分割这种情况。
调用的递归核心不变，但是调位置换为填坑法
int Partion2(int*a,int left,int right){ int mid=Middle(a, left, right); Swap(&a[mid],&a[left]); int key=a[left]; int pivot=left; while(left<right){ while(left<right&&a[right]>=key){ --right; } a[pivot]=a[right]; pivot=right; while(left<right&&a[left]<=key){ ++left; } a[pivot]=a[left]; pivot=left; }a[pivot]=key; return pivot; }
pivot为坑，选择最左边的第一个数据作为keyi和坑，然后R先走找小于keyi的，将坑和R换位置，L开始走，找大于keyi的，然后L和坑再次换位置
其实细细想一下，坑也就代表一个位置也不能说算是空，只能说算是（仍为原来的数，而不是空）被覆盖了，把值和下标都给找到的；R开始是找到5 然后坑到5这个位置，同时坑的下标变为7（原来5的位置），那么原先坑的的值变为5，也就是说换的是坑的位置，而不是坑的值，L在开始找到7，坑又和7换，换完7，再换4，后换9，最后换3，坑在3这个位置，然后坑和keyi换，返回坑的位置，其实自己一想和上面那种排序差不多含义，就是实现的方法思路有一丢丢不同。
方法3:前后指针法
int Partion3(int*a,int left,int right){ int keyi=left; int prev=left; int cur=prev+1; while(cur<=right){ if(a[cur]<a[keyi]&&++prev!=cur){ //(++prev!=cur是不让他和自己换，浪费时间 Swap(&a[cur],&a[++prev]); } ++cur; } Swap(&a[prev],&a[keyi]); return prev; }
cur遇到比keyi小的就停下来，++prev然后交换cur和prev的值， 刚开始cur和prev相差一个，然后cur开始，因为prev++后和cur相同，不交换，到了7以后就开始拉开身位了，cur到了3的位置，然后prev还是在2，prev++变为7，然后3和7换，cur到了4，4和9换，cur到5和7换（原来是3的位置），cur到8的位置走完，然后prev（最后在5（开始的3）的位置）和6换
小区间优化
void QuickSort(int*a,int left,int right){ if(left>right) return ; if(right-left<10){ Insertsort(a+left,right-left+1); } int keyi=Partion3(a,left,right); QuickSort(a, left, keyi-1); QuickSort(a, keyi+1, right); }
看这张图就可以知道，递归次数多是分散到各个小区间里，所以小区间会导致递归次数很多，所以我们将最底下那些递归次数最多的小区间，都换为（相对有一定顺序了）直接插入很好用。
非递归的快排（马上会把栈搞一手，学的时候还没有搞这个栈）
void QuickSortNonR(){ ST st; StackInit(&st); Stackpush(&st,left); StackPush(&st,right); while(!StackEmpty(&st)){ int end=StackTop(&st); （取当前栈顶数字） StackPop(&st); （删除当前栈顶数字 int begin=StackTop(&st); StackPop(&st); int keyi=Partion3(a,begin,end); if(keyi+1<end){ Stackpush(&st,end); （插入栈顶数字） } if(begin<keyi-1){ Stackpush(&st,begin); StackPush(&st,keyi-1); } } }
这是通过栈来进行操作，后进的会先出来，（说得都是下标）所以先插入0-9（这里有一个删除，但是删除之前存了他们的数）然后取出他们分别的下标0-9
然后要想从左边开始排就要，先插入6-9，然后插入0-4，对0-4，再次分开删除0-4换为（应该正常是分为3-4和0-1，然后0-1不进入栈顶）但是我们这个例子中因为keyi会有一点小区别，会0-3，0-2，0-1不进入栈顶走完
进入栈顶指的是最后两个if
总结：快排很好，真的蛮费劲的，一起加油
章诺楠yyds
