快速排序

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);
}

1. 传入递归函数的first和last是每次递归子数组的首尾下标，只不过第一次传入的数组是整个数组而已。
2. 递归终止条件蕴含的信息就是：只要first<=last就可以继续执行函数体的内容。
3. 两边各找一个不满足左小右大的数，进行交换。
4. 假定序列为偶数个且一开始大的全在前面，小的全在后面。在循环中，当i和j相邻是最后一轮交换，此时已经是大的全在后面，小的全在前面的状态了。然后再进入循环时，j自减到与i重合，就跳出大循环了，这也是为什么大循环里面每个步骤都套了一层i<j。然后此时的状态是i和j都指向小的一半的最后一个，所以是将arr[i]扔到前半部分而不是后半部分至于为什么扔到第一个而不怕覆盖，是因为在第一个一开始本身值就是key，在与key的比较中没有动它就直接指针右移了，所以最后这个位置和key保存的信息是重复的，覆盖它也没关系。最后两key插到两半序列的中间，它左边是小数，右边是大数。