复习了下快速排序的写法和原理，其实现在看起来并没有很难，缩减代码后更是显得非常简略。
快排的基本思想是随意选择数组中一个数字作为标记值，然后将范围内所有大于标记值的数放在标记值位置的右边，所有小于标记值的数放在标记值的左边。做这个操作的范围不断缩小，最后递归到单个数字上，使得所有范围内的值都符合其左边值比自己小，右边值比自己大。
首先未处理的数组我们可以看成这样【假设定第一个数字为标记值，未排序的数字标记为“乱”】：
标记值、乱、乱、乱、乱、乱、乱、乱、乱
那么我们取出标记值，然后依次和所有“乱”做比较，比较后得知“乱”与标记值的关系，重新交换位置，整理得：
【小、小、小】、标记值、【大、大、大、大、大】
这样我们就通过以上操作排列正确了标记值的位置。
于是现在不明确位置的，相对位置确定，具体位置未知的数，就是标记值左边所有比其小的数，和右边所有比其大的数。
于是可以发现，我们要进行排序的数列变成了两段，且长度更小了
然后除去标记值不考虑【因为他已经排完了】单独考虑剩下两段数列的排序，我们又可以当成一个新的序列去排，同样的，回到第一步，选取新序列的标记值，并使得其所在序列中比其小的值放左边，比其大的值放右边。以这样的方式确定第二个值，第三个值…..的位置
不断递归下去，当左右两边选择的标准值的下标位置不满足【左<右】时，说明所有值都排列正确了。
具体操作过程，当选择了一个位置的值作为标准值后，我们不考虑该值，设定两个指针分别从最左和最右向中间遍历，如左边指针，向右移动，找到第一个大于等于标准值的数，而右边指针，向左移动，找到第一个小于标准值的数，交换两值位置，这样就使得两个数的相对位置满足“分别处于标准值两边”的要求了。
交换之后，在此基础上，继续两端指针向内移动，找到下一个比标准值大和小的值，使其交换到正确的相对位置。
直到，左边指针移动 到了右边指针的右部，或右边指针移动到了左边指针的左部，说明目前为止，序列的整体排列时符合某个位置上左边所有数都小于标准值，右边所有数都大于标准值的。那么具体是哪个位置呢?
可以知道，移动过度的左指针将找到一个被右指针遍历过的数，这个数就是从左往右数目前第一个大于等于标准值的数，而右指针的将指向，从右往左数，第一个小于标准值的数，那么 结果显而易见，如果我们选择的标准值在序列的左边，那么要使其与右指针的位置交换，因为交换后，一个小于标准值的数将被放到标准值的左边，是符合条件的，若选择的标准值在右边，与右指针指向的数交换，将导致一个小于标准值的数放到了其右边，之前做的操作就白费了。
因此视情况而定，将标准值与左右两指针中正确的一个进行交换，即可形成一步正确的安插标准值的操作，并为之后的递归操作提供条件。
///快速排序
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=1e5+7;
int a[maxn];
int partition(int *a,int left,int right)///参数为，被排序的数组，需要排序的左右边界
{
int l=left,r=right+1,flag=a[left];//三个参数，分别表示，起始左指针，起始右指针，标准值确定
while(true)
{
while(a[++l]<flag);///从左往右数寻找第一个比标准值大的数
while(a[--r]>flag) if(r==left)break;///从右往左数，寻找第一个比标准值小的数
if(l<r)swap(a[l],a[r]);///当两指针相对位置不正确时，退出交换
else break;
}
swap(a[left],a[r]);///交换找到的两数，一次操作完成
return r;//返回安插正确的标准值的位置，作为将序列分成左右两部分继续递归的分界
}
void quickSort(int *a,int left,int right)///快排的基本函数，不断递归的是序列的左右两部分长度
{
if(left<right)///递归出口为边界分段错误
{
int p=partition(a,left,right);///此处是排序操作
quickSort(a,left,p-1);///递归的是对序列的分段
quickSort(a,p+1,right);
}
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1; i<=n; i++) scanf("%d",&a[i]);
quickSort(a,1,n);
for(int i=1;i<=n;i++)printf("%d%c\n",a[i],i==n?'\n':' ');
}补充一点就是，此处写的快排默认是 【双路快排】 ，因为 单路快排太简朴了，实用性不高。单路相比双路其实是在相同的思想上实现方法的的不同，此处双路是从两头同时向中间移动指针，并交换，而单路就比较蠢了，从左往右移动一个指针，然后比较指针上的值与标准值大小，然后又有个指针对小于标准值的位置进行标记，若是大于标准值的，则直接指针后移，否则与大于标准值的第一个数字进行交换，然后小于标准值位置指针后移。大于标准值指针也后移。这样就带来一个问题，同样是分成两段，一些等于标准值的数就被严格规定分到大于标准值或者小于标准值的分组里了。
当被选择的标准值存在很多时，或者存在很多相同的数时，这样分类挑拣的方法很容易使某一边的元素过多，并且在递归中重复多次被遍历到，复杂度会退化成N^2的。
因此优化方法即使用双路快排，很平均的将严格大于小于的元素分开，并把相同元素平均的分发到两边中。就如上面介绍的实现方法一样，因为左右两个指针在向内移动的过程中不断交换，最后总要移动到某个中点【指值大小的中点，而非位置】，那么相同大小的值会被平均的分开到左右两段上，而不是全部归到一段。
而三路快排就比较厉害了，处理的问题同样是，多个相同值时如何解决。三路快排直接在双路快排基础上，中间多加一个分段，也就是所有相同值放在中间分段，那么就会出现多个指针，分别表示，排序范围的左右边界，大于标准值的左边界，小于标准值的右边界，以及正在遍历数的指针。这样就将原数组分成三段，递归排序时，只需将不包括相同值的范围边界作为参数传递下去即可，即，相同值不必多次遍历了。
再补充一种Python实现快排的代码,风格非常Pythonic,易于理解
def quicksort(array):
less = [];
greater = [];
if len(array) <= 1:
return array
pivot = array.pop()
for x in array:
if x <= pivot:
less.append(x)
else:
greater.append(x)
return quicksort(less) + [pivot] + quicksort(greater)归并排序之前的博客里有写过，，，，再写一下以示致敬，这个真的很有合并链表的感觉，其实就是先分段成小份小份的小份，最后到底层递归出口后，回并起来，开始执行类似合并链表的操作。
取递归时被分开的两段序列，按比较大小的形式归并成一个序列上，使得归并的新序列有序，接着继续拿出两段新的有序序列进行新的归并，妙不可言！
https://blog.csdn.net/kuronekonano/article/details/80589132 之前详细说明归并排序的传送门
///归并排序
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=1e5+7;
int a[maxn],n;
void Meg(int l,int mid,int r)//治
{
int i=l,j=mid+1,k=0,temp[maxn];
while(i<=mid&&j<=r) a[i]<a[j]?temp[k++]=a[i++]:temp[k++]=a[j++];
while(i<=mid) temp[k++]=a[i++];///合并结束，将剩余较长的部分接到尾部
while(j<=r) temp[k++]=a[j++];
for(int i=l,k=0;i<=r;k++,i++) a[i]=temp[k];///临时数组放回原数组
}
void Msort(int l,int r)//分
{
if(l<r)
{
int mid=(l+r)/2;
Msort(l,mid);
Msort(mid+1,r);
Meg(l,mid,r);
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
Msort(1,n);
for(int i=1;i<=n;i++)printf("%d%c",a[i],i==n?'\n':' ');
}
