快速排序的递归实现

快速排序是对冒泡排序的一种改进。它的基本思想是：通过一次排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归或者非递归进行，以此达到整个数据变成有序序列。

下面是快速排序的递归实现：

view sourceprint?01 #include "stdafx.h" 

02   

03 #define LIST_INIT_SIZE 100    //顺序表初始大小 

04 #define LISTINCREMENT 10    //顺序表增量 

05 typedef int ElemType;    //顺序表元素类型 

06 typedef struct        //顺序表结构 

07 { 

08     ElemType *elem; 

09     int length; 

10     int listsize; 

11 }SqList; 

12 //初始化顺序表 

13 int InitList_Sq(SqList &L)         

14 { 

15     L.elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); 

16     if(!L.elem) return -1; 

17     L.length = 0; 

18     L.listsize = LIST_INIT_SIZE; 

19     return 0; 

20 } 

21 //创建顺序表 

22 int CreatList_Sq(SqList &L) 

23 { 

24     InitList_Sq(L); 

25     int i = 1; 

26     while(scanf("%d",&L.elem[i]) != EOF) 

27     { 

28         i++; 

29     } 

30     L.length = i - 1; 

31     return 0; 

32 } 

33 //一趟快速排序 

34 int Partition(SqList &L,int low,int high) 

35 { 

36     L.elem[0] = L.elem[low]; 

37     int pivotkey; 

38     pivotkey = L.elem[low]; 

39     int temp; 

40     while(low < high) 

41     { 

42         while(low < high && L.elem[high] >= pivotkey) --high;; 

43         L.elem[low] = L.elem[high]; 

44         while(low < high && L.elem[low] <= pivotkey) ++low; 

45         L.elem[high] = L.elem[low]; 

46     } 

47     L.elem[low] = L.elem[0]; 

48       

49     return low; 

50 } 

51 //递归实现快速排序 

52 void QuickSort(SqList &L,int low,int high) 

53 { 

54     if(low < high) 

55     { 

56         int pivotloc = Partition(L,low,high); 

57         QuickSort(L,low,pivotloc - 1); 

58         QuickSort(L,pivotloc + 1,high); 

59     } 

60 } 

61 int _tmain(int argc, _TCHAR *argv[]) 

62 { 

63     SqList L; 

64     CreatList_Sq(L); 

65     QuickSort(L,1,L.length); 

66     for(int i = 1; i <= L.length; i++) 

67     { 

68         printf("%d ",L.elem[i]); 

69         if(LIST_INIT_SIZE == i) printf("\n"); 

70     } 

71     char ch = getchar(); 

72       

73     return 0; 

74 }

快速排序的非递归算法：

view sourceprint?01 #include <iostream> 

02 #include <stack> 

03 using namespace std; 

04 template <class T> 

05 int partition(T a[],int low,int high) 

06 { 

07  T v=a[low]; 

08  while(low<high) 

09  {   

10   while(low<high && a[high]>=v) high--; 

11   a[low]=a[high]; 

12   while(low<high && a[low]<=v) low++; 

13   a[high]=a[low]; 

14  } 

15  a[low]=v; 

16  return low; 

17    

18 } 

19    

20 template <class T> 

21 void QuickSort(T a[],int p,int q) 

22 { 

23  stack<int> st; 

24  int j; 

25  do{ 

26       while(p<q) 

27       { 

28          j=partition(a,p,q);    

29          if( (j-p)<(q-j) ) 

30          { 

31             st.push(j+1); 

32             st.push(q); 

33             q=j-1; 

34          } 

35          else

36          { 

37            st.push(p); 

38            st.push(j-1); 

39            p=j+1; 

40          }    

41       } 

42   if(st.empty()) return; 

43   q=st.top();st.pop();   

44   p=st.top();st.pop();   

45   //cout<<endl<<"p:"<<p<<" "; 

46   //cout<<"q:"<<q<<endl; 

47  }while(1); 

48 } 

49   

50 void main() 

51 { 

52  //int a[7]={7,6,5,4,3,2,1}; 

53  //int a[7]={1,2,3,4,5,6,7}; 

54  int a[7]={3,5,2,3,66,225,1}; 

55  for(int i=0;i<7;i++) 

56   cout<<a[i]<<" "; 

57  QuickSort(a,0,6); 

58  cout<<endl; 

59  for(int i=0;i<7;i++) 

60   cout<<a[i]<<" "; 

61 }