快速排序

简单的了解以下快排：

参考的讲解网址：https://blog.csdn.net/nrsc272420199/article/details/82587933

1、稳定性问题首先大家应该都知道快速排序是一个不稳定排序算法，那么到底什么才是排序的稳定性呢，我认为通俗的讲有两个相同的数A和B，在排序之前A在B的前面，而经过排序之后，B跑到了A的前面，对于这种情况的发生，我们管他叫做排序的不稳定性，而快速排序在对存在相同数进行排序时就有可能发生这种情况。例如(5,3A,6,3B)对这个进行排序，排序之前相同的数3A与3B，A在B的前面，经过排序之后会变成(3B，3A，5，6),所以说快速排序是一个不稳定的排序

2、时间复杂度问题

最优情况:每一次的flag刚好都可以平分整个数组，此时的时间复杂度为O(nlogn)

最坏情况:每一次的flag刚好都是最大或者最小的数，此时的时间复杂度为O(n2)

平均情况:经过推到平均情况为O(nlogn)

我的代码:

 1 #include<cstring>
 2 #include<cstdio>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6 int qksort(int* A,int left,int right)
 7 {
 8     if(left>=right)return 0;
 9     //终止条件是>=的运算符
10     int p=A[left];
11     //printf("->>%d
",p);
12     int low=left,high=right;
13     while(low!=high)
14     {
15         while(high>low&&A[high]>=p)high--;
16         A[low]=A[high];
17         while(low<high&&A[low]<=p)low++;
18         A[high]=A[low];
19         //while判断条件需要格外注意。
20         //首先要判断的是low与high的大小关系
21         //其次要注意第二条件中允许了 等于 这一条件，否则遇到相同的数据会死循环
22     }
23     A[low]=p;
24     qksort(A,left,low-1);
25     qksort(A,low+1,right);
26     return 0;
27 }
28 
29 int quick_sort(int* A,int* Aend)
30 {
31     int lenth=Aend-A;
32     qksort(A,0,lenth-1);
33     return 0;
34 }
35 
36 int main()
37 {
38     int aim[]={6,69,4,8,3,69,12,63,42};
39     quick_sort(aim,aim+9);
40     for(int i=0;i<9;i++)
41         printf("%d ",aim[i]);
42     printf("
");
43     return 0;
44 }

-----------------------------------------------------------------------------

下面是第一次补充内容：一个更好一些的模板

 1 int quick_sort(int *aim,int x,int y)
 2 {
 3     //printf("[%d,%d)
",x,y);
 4     if(y-x<=1)return 0;//区间是左闭右开
 5     //也许选定的标准数字是最小的或最大的使得下一层递归中没有排序对象
 6     int p=aim[x];//选定最开头的数字为标准数字
 7     int low=x,high=y-1;
 8     while(low!=high)
 9     {
10         while(low<high&&aim[high]>=p)high--;
11         aim[low]=aim[high];
12         while(low<high&&aim[low]<=p)low++;
13         aim[high]=aim[low];
14         //比较有规律，建议直接背住
15     }
16     aim[low]=p;
17     for(int i=x;i<y;i++)cout<<aim[i]<<" ";
18     cout<<endl;
19     //
20     quick_sort(aim,x,low);
21     quick_sort(aim,low+1,y);
22     return 0;
23 }