快速排序

快排（QuickSort）思想：

基于分治法的思想：

1、分解：从数列中取出一个元素作为基准元素，将问题分解为两个子序列列，左子序列都小于基准元素，右子序列都大于

2、治理：对两个子序列进行快速排序。

3、合并：将排序后的子序列进行合并，得到原问题的解

时间复杂度：平均情况：O（nlogn）

空间复杂度：

 1 #include <iostream>
 2 using namespace std;
 3 int Partition(int r[],int low,int high) {
 4     int i=low,j=high;
 5     int pivot=r[low];
 6     //快速排序思想：
 7      
 8     while(i<j) {
 9         while(i<j&&r[j]>pivot)
10             j--;
11         if(i<j) {
12             swap(r[i++],r[j]);
13         }
14         while(i<j&&r[i]<pivot)
15             i++;
16         if(i<j) {
17             swap(r[i],r[j--]);
18         }
19     }
20     return i;
21 }
22 void QuickSort(int A[],int low,int high) {
23     int mid;
24     if(low<high) {
25         mid=Partition(A,low,high);
26         QuickSort(A,low,mid-1);
27         QuickSort(A,mid+1,high);
28     }
29 }
30 int main() {
31     int a[1000];
32     int N;
33     cout<<"请输入要排序的数据个数："<<endl;
34     cin>>N;
35     cout<<"请输入数据: "<<endl;
36     for(int i=0; i<N; i++) {
37         cin>>a[i];
38     }
39     cout<<endl;
40     QuickSort(a,0,N-1);
41     cout<<"排序后的数据： "<<endl;
42     for(int i=0; i<N; i++)
43         cout<<a[i]<<" ";
44     cout<<endl;
45     return 0;
46 }

优化：

既然我们每次都从左到右找比基准元素大的数字，然后和基准元素交换，从右向左找比基准小的数字，然后交换。最终将基准元素和

不如我们找到大数和小数，直接将二者交换不就省事了？？

 1 #include <iostream>
 2 using namespace std;
 3 int Partition2(int r[],int low,int high) {//划分函数 
 4     int i=low,j=high;
 5     int pivot=r[low];
 6     //快速排序思想：
 7     while(i<j){
 8         while(i<j&&r[j]>pivot) j--;//向左扫描 
 9         while(i<j&&r[i]<=pivot) i++;//向右扫描 
10         if(i<j){//找到左边比基准小、右边比基准大的下标i和j，实行交换 
11             swap(r[i++],r[j--]);
12         }
13         if(r[i]>pivot){
14             swap(r[i-1],r[low]);
15             return i-1;
16         }
17         swap(r[i],r[low]);
18         return i;
19     }
20      /*
21     while(i<j) {
22         while(i<j&&r[j]>pivot)
23             j--;
24         if(i<j) {
25             swap(r[i++],r[j]);
26         }
27         while(i<j&&r[i]<pivot)
28             i++;
29         if(i<j) {
30             swap(r[i],r[j--]);
31         }
32     }*/
33     return i;
34 }
35 void QuickSort(int A[],int low,int high) {
36     int mid;
37     if(low<high) {
38         mid=Partition2(A,low,high);
39         QuickSort(A,low,mid-1);
40         QuickSort(A,mid+1,high);
41     }
42 }
43 int main() {
44     int a[1000];
45     int N;
46     cout<<"请输入要排序的数据个数："<<endl;
47     cin>>N;
48     cout<<"请输入数据: "<<endl;
49     for(int i=0; i<N; i++) {
50         cin>>a[i];
51     }
52     cout<<endl;
53     QuickSort(a,0,N-1);
54     cout<<"排序后的数据： "<<endl;
55     for(int i=0; i<N; i++)
56         cout<<a[i]<<" ";
57     cout<<endl;
58     return 0;
59 }