关于快排的递归实现

• 1 引子
• 2 源码

自己以前写过一篇关于快速排序的blog,但是没采用递归,而且当时的blog是完全手写的.但是现在都用Emacs工作,所以就分开了.

虽然以前写过快排,但是过了一段时间再来写,虽然有递归的引子,但还是对递归的初始入口不会,始终不得其解,还是在参看了以前的代码才写了出来.

快速排序的递归实现:

 1:  #include <stdio.h>
 2:  #include <stdlib.h>
 3:  
 4:  /**
 5:    * 根据哨兵对数组进行划分,左小右大
 6:    * @param num   int*   待排序数组
 7:    * @param start int    待排序数组的起点
 8:    * @param end   int    待排序数组的终点
 9:    *
10:    * @return  int    进行完一次划分后,所选哨兵在数组中所在的索引,用来划分数组,左小右大
11:    */
12:  int quicksort(int* num,int start,int end)
13:  {
14:    int i = start,j = end;
15:    int temp = num[start]; //每次的哨兵选择待排序数组的第一个数
16:    while(i < j)
17:    {
18:        while(num[j] > temp && j > i)
19:            j--;
20:        if(j > i)
21:            num[i++] = num[j];
22:        while(num[i] < temp && j > i)
23:            i++;
24:        if(j > i)
25:        num[j--] = num[i];
26:    }
27:    num[i] = temp;
28:    return i; //哨兵的索引
29:  }
30:  
31:  /**
32:    * 递归调用实现排序
33:    * @param 同quicksort
34:    *
35:    */
36:  int sort(int* num,int start,int end)
37:  {
38:    int index;
39:    if(start < end)   //注意递归的入口
40:    {
41:        index = quicksort(num,start,end);
42:        sort(num,start,index-1);
43:        sort(num,index+1,end);
44:    }
45:    return 0;
46:  }
47:  
48:  int main()
49:  {
50:    int i,num[10] = {1,4,2,56,32,67,43,87,96,11};
51:  
52:    sort(num,0,9);
53:  
54:    for(i = 0; i < 10; i++)
55:        printf("%d ",num[i]);
56:    return 0;
57:  }

平均时间复杂度:O(nlog(n));