思想：
一次快排：首先用一个临时变量保存arr[low]下标的值，然后从high开始向low遍历，找到小于arr[low]的值，赋值给arr[low]；然后从low开始向high遍历，找到比arr[high]大的值，赋值给arr[high],直到low与high相等，就将临时变量的值赋给它们相遇的位置，然后返回这个位置的下标。
int onceQuick(int *arr,int low,int high) { int tmp=arr[low]; while(low<high) { while(arr[high]>=tmp&&low<high) { high--; } arr[low]=arr[high]; while(arr[low]<=tmp&&low<high) { low++; } arr[high]=arr[low]; } arr[low]=tmp; return low; }（1）首先通过一次快排后可以找到一个位置将数组分为两部分，然后每个部分分别进行一次快排，从而变成递归实现。
void Quick(int *arr,int low,int high) { int mid=onceQuick(arr,low,high); if(mid-low>1) { Quick(arr,low,mid-1); } if(high-mid>1) { Quick(arr,mid+1,high); } }将给定数据逐次分为两部分，即就是分为logn组数据，每组分别有一个low和high。 （1）用额外数组的方式： 动态开辟一个大小为需要给定数组的sizeof（int）*（logn+1）*2的整形数组。 //大小计算方式：logn=(int)(log(double)n)/log((double)2) 初始low为0，high为len-1，将low与high依次保存在数组中。用一个top表示数组当前下标位置。进入一个条件为top的循环，首先将数组的最后一个数出给right，倒数第二个出给left，然后进行一次快排，mid接受返回值，然后判断：如果mid减left大于1，就将left，mid-1依次保存在数组中；如果right减mid大于1，就将mid+1，right依次保存在数组中，则只要数组中还有数据就会进行循环，进行一次快排。
void Quick1(int *arr,int low,int high) { int n=high-low+1; int x=(int)(log((double)n)/log((double)2))+1; int *data=(int *)malloc(sizeof(int)*x*2); assert(data!=NULL); int top=0; data[top++]=low; data[top++]=high; int left,right,mid; while(top) { right=data[--top]; left=data[--top]; mid=onceQuick(arr,left,right); if(mid==-1) { continue; } if(mid-left>1) { data[top++]=left; data[top++]=mid-1; } if(right-mid>1) { data[top++]=mid+1; data[top++]=right; } } }（2）用栈的方式： 初始low为0，high为len-1，将它们依次压栈。循环条件：只要栈不为空就继续，进入循环，将栈顶两个元素依次出给right，left，然后进行一次快排，mid接收返回值，然后判断如果mid减去left大于1，就将left，mid-1依次压栈；如果right减mid大于1，就将mid+1，right依次压栈，则只要栈不为空就会循环进行一次快排。
时间复杂度：O（nlogn）
空间复杂度： 非递归：O（（logn）*sizeof（int）*2 ） 递归：O（logn*44H）；
比较：如果空间不足时，递归会在调用过程中出错，而非递归就可以在一开始申请堆区空间时报错提醒。
快排优化： 找基准的位置： 1.三位数取中法，求第一个数，中间位置，最后一个数的中位数来划分。 2.当数据量小时：三位数取中+插入排序。 3.解决相等元素多的情况：三位数取中+插入排序+聚集相等元素。
思想： （1）取数字的位数作为关键字（即就是个位，十位，百位等）决定最外层循环的次数与本次循环的关键字。
void RadixSort(int *arr,int len) { int power=GetMaxFiguer(arr,len); for(int i=0;i<power;i++) { Radix(arr,len,i); } }（2）首先我们可以用队列来保存关键字的情况（这里因为是数字，取值范围是0~9，我们可以创建一个含有10个队列的数组）。首先我们需要求出关键字的情况（即个位上的数字），将源数据入到队列中与关键字相应的数字位中，循环遍历源数组，需要len-1次；结束后将队列中的数据重新赋给源数组，出队成功，则源数组向后走，失败则队列向后走。
static void Radix(int *arr,int len,int Figure) { Que tub[10]; for(int i=0;i<10;i++) { Init(&tub[i]); } int index; for(int i=0;i<len;i++) { index=GetFiguer(arr[i],Figure); Push(&tub[index],arr[i]); } int j=0; for(int i=0;i<len;) { if(Pop(&tub[j],&arr[i])) { i++; } else { j++; } } }时间复杂度：d（n+k）；d表示关键字的个数，k表示每个关键字的情况。
多关键字的排序，不需要两两比较的排序。
