数据结构快速排序讲解这几步你要了解

对于计算机专业的大学生而言，快速排序是大家必须掌握的一种排序算法，但是快速排序理解起来不是那么容易，因此很多同学刚接触时不大明白，自己针对自己的理解用比价浅显的语言来讲解一下，让大家能够很容易学懂。

操作方法

快速排序作为和冒泡排序相同类型的排序（同为交换类排序），之所以能够被人们所熟知，是因为它解决了冒泡排序只用来对相邻两个元素进行比较，因此在互换两个相邻元素时只能消除一个逆序，而快速排序是通过两个不相邻元素的交换，来消除待排序记录中的多个逆序。即快速排序中的一趟交换可以消除多个逆序。具体思想：从待排序记录中选取一个记录（通常选取第一个记录，当然也可采用随即划分的方式，这样能大大提高快速排序的执行效率，如我们所熟知的在O(n)的时间复杂度内找出前k元的算法），将其关键字记为K1，然后将其余关键字小于K1的记录移到前面，而大于关键字K1的移到后面，一趟快速排序之后，将待排序序列划分为两个子表，最后将关键字K1插到这两个子表的分界线的位置。具体实现就是用三层while循环，最外层的while循环控制该趟快速是否进行，而内层的两个while循环一个用来从左到右扫描大于该趟基准记录关键字的元素，一个用来从右到左扫描小于该趟基准记录的关键字的元素，可以用两个指针low和high指向当前从左到右和从右到左扫描的当前记录的关键字，找到一个就将其交换。以上是一趟快速排序的思想，对上述划分后的子表重复上述过程，直至划分后的子表的长度不超过1为止。即为快速排序的思想，从定义可知快速排序是一个递归排序。具体代码如下：
#include<iostream>
using namespace std;
const int len=7;
int qk(int a[],int low,int high)//注意快速排序函数的参数，因为每一趟快速排序的作用是要将数组分割为两个部分，前面一部分不大于K，后面一部分不小于K，然后在 //对前一部分和后一部分继续进行快速排序，所以，qk的第二个参数与第三个参数应为low与high
{
int x=a[low];//选取第一个元素作为基准记录
while(low<high)
{
while(low<high&&a[high]>=x)
high--;
if(low<high)
{
a[low]=a[high];
low++;
}
while(low<high&&a[low]<=x)
low++;
if(low<high)
{
a[high]=a[low];
high--;
}
}
a[low]=x;
return low;
}
void qsort(int a[],int low,int high)
{
if(low<high)
{
int pos=qk(a,low,high);
qsort(a,low,pos-1);
qsort(a,pos+1,high);
}
}
void main()
{
int a[len]={7,4,5,1,2,3,6};
cout<<"快速排序后的结果为："<<endl;
qsort(a,0,len-1);
for(int i=0;i<len;i++)
{
cout<<a[i]<<' ';
}
cout<<endl;
}
复杂度分析：快速排序最好的情况就是每一趟排序将序列划分为两个部分，正好在表中间将表划分为两个大小相等的子表，类似于折半查找，此时复杂度为O(nlog2n).
最坏的情况就是已经排好序，则第一趟经过n-1次比较，第一个记录定在原位置，左部子表为空表，右部子表为n-1个记录，第二趟n-1个记录经过n-2次比较，第二个记录定在原位置.....即此时快速排序内层中的两个while循环不执行，此时快速排序退化为冒泡排序，总的比较次数为n*(n-1)/2，复杂度为O(n*n).