<排序算法> 快速排序QuickSort

1.基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
2.代码实现：

 1 #include<iostream>
 2 using namespace std;
 3 
 4 void PrintArr(int arr[],int len);
 5 void QuickSort(int arr[],int begin,int end) //从小到大
 6 {
 7     if(arr == NULL || begin >= end)    return ;
 8     
 9     int key = arr[begin];
10     int i=begin,j=end;
11     while(1)
12     {
13         if(arr[j] < key && i < j)
14         {
15             int t = arr[j];
16             arr[j] = arr[i];
17             arr[i] = t;
18             i ++;
19         }
20         if(arr[j] > key && i < j)
21         {
22             j --;
23         }
24         if(arr[i] > key && i < j)
25         {
26             int t = arr[j];
27             arr[j] = arr[i];
28             arr[i] = t;
29             j --;
30         }
31         if(arr[i] < key && i < j)
32         {
33             i ++;
34         }
35         if(i == j) break;
36     }
37 
38     int mid = i;
39     QuickSort(arr,begin,mid);
40     QuickSort(arr,mid+1,end);
41 }
42 
43 void PrintArr(int arr[],int len)
44 {
45     for(int i=0;i<len;i++)
46         cout << arr[i] << " ";
47     cout << endl;
48 
49     return ;
50 }
51 
52 int main()
53 {
54     //int arr[10] = {9,8,7,6,5,4,3,2,1,0};
55     int arr[10] = {4,8,6,3,7,2,9,5,0,1};
56     QuickSort(arr,0,sizeof(arr)/sizeof(arr[0])-1);
57     PrintArr(arr,sizeof(arr)/sizeof(arr[0]));
58 
59     system("pause");
60     return 0;
61 }

<排序算法> 快速排序QuickSort

相关推荐