快速排序
C语言实现 从小到大排序
void swap(int* a,int* b){
int temp=*a;
*a=*b;
*b=temp;
}
void quickSort(int* arr,int first,int last){//递归时需要通过首尾下标确定子数组在原数组起始终止位置
if(first>last){//这里是递归的终止条件，所以传入的参数有关
return;
}
int i=first;
int j=last;
int key=arr[first];
/*针对整个传入的序列，将左边的大的与右边的小的不断交换*/
while(i<j){
while(arr[j]>=key&&i<j){
j--;
}
while(arr[i]<=key&&i<j){
i++;
}
//if(i<j){
swap(&arr[i],&arr[j]);//注意取地址
// }
}
//到这里已经形成了左半部分小，右半部分大，j也移动到与i重合的局面
arr[first]=arr[i];//将中间的数弄走
arr[i]=key;//最后就是将key放到了正确的位置
//可以直接swap(&arr[first],&arr[i]);
/*将左右两半子序列传进函数排序*/
quickSort(arr,first,i-1);
quickSort(arr,i+1,last);
}
- 传入递归函数的first和last是每次递归子数组的首尾下标，只不过第一次传入的数组是整个数组而已。
- 递归终止条件蕴含的信息就是：只要first<=last就可以继续执行函数体的内容。
- 两边各找一个不满足左小右大的数，进行交换。
- 假定序列为偶数个且一开始大的全在前面，小的全在后面。在循环中，当i和j相邻是最后一轮交换，此时已经是大的全在后面，小的全在前面的状态了。然后再进入循环时，j自减到与i重合，就跳出大循环了，这也是为什么大循环里面每个步骤都套了一层i<j。然后此时的状态是i和j都指向小的一半的最后一个，所以是将arr[i]扔到前半部分而不是后半部分至于为什么扔到第一个而不怕覆盖，是因为在第一个一开始本身值就是key，在与key的比较中没有动它就直接指针右移了，所以最后这个位置和key保存的信息是重复的，覆盖它也没关系。最后两key插到两半序列的中间，它左边是小数，右边是大数。