本文共 2158 字，大约阅读时间需要 7 分钟。

所有查找中Hash查找效率最高，在所有排序中，快速排序的效率也是最高的。

采用递归函数的方法来实现快速排序！

• 先把递归框架搭建起来！！！
• 递归框架，首先确定终止条件，那就是当 low >= hight的时候！！！
• 然后确定递归操作，已经知道每一次拆分会产生两个区间，又要对两个区间各自进行拆分！
• 对于拆分操作，输入的是列表和low、hight，返回的是拆分好后，基准值的下标！！！
• 对于拆分出来的两个区间的再次拆分，根据上次拆分的基准值下标来确定这两个区间的low、hight
• 在拆分的时候，low和hight都往中间靠拢，最后low和hight是要重合的，这个重合的位置就是基准值要存放的位置，也是要返回的位置.
• 外层的循环在内层循环中还要考虑。
• 当low与hight交换之后，接着从另一端开始继续遍历
• 判断的时候是利用基准值tmp判断，交换的时候却是low和hight位置上的交换

代码

#include 
   
    #include 
    
     #include 
     
      int quick_sort(int *, int , int);int partion(int *, int, int);int main(int argc, const char* argv[]){
           int i, n;        printf("input the num:");        scanf("%d", &n);        int *num = (int*)malloc(sizeof(int) * n);         srand((unsigned)time(NULL));        for (i = 0; i < n; i++) {
                   num[i] = rand() % 100;        }           printf("the rand num is:");        for (i = 0; i < n; i++) {
                   printf("%2d ", num[i]);        }           puts("");        quick_sort(num, 0, n-1);        printf("quick_sort num :");        for (i = 0; i < n; i++) {
                   printf("%2d ", num[i]);        }           puts("");        free(num);        return 0;}int quick_sort(int *num, int low, int hight){
           int i; //记录基准值下标        if (num == NULL) {
                   printf("num is NULL!\n");                return -1;         }           if (low >= hight)                return 0;            i = partion(num, low, hight);    //拆分操作        quick_sort(num, 0, i - 1);       //左区间排序        quick_sort(num, i + 1, hight);   //右区间排序        return 0;}int partion(int *num, int low, int hight){
           int tmp = num[low];    //基准点要先保存好        while (low < hight) {
                   while ((low < hight) && (tmp <= num[hight])) {
    //始终与基准值比较                        hight--;                }                    num[low] = num[hight];                         //找到要交换的就之间交换                    while ((low < hight) && (tmp >= num[low])) {
      //交换之后就从另一端开始比较                        low++;                }                   num[hight] = num[low];        }           num[low] = tmp;     //low hight重合的时候就是说基准值的位置             return low;        //返回基准值的最终位置}
     
    
   

转载地址：http://atwzi.baihongyu.com/