数据结构快速排序讲解

1、快速排序作为和冒泡排序相同类型的排序（同为交换类排序），易七淄苷之所以能够被人们所熟知，是因为它解决了冒泡排序只用来对相邻两个元素进行比较，因此在互换两个相邻元艾绱书虻素时只能消除一个逆序，而快速排序是通过两个不相邻元素的交换，来消除待排序记录中的多个逆序。即快速排序中的一趟交换可以消除多个逆序。具体思想：从待排序记录中选取一个记录（通常选取第一个记录，当然也可采用随即划分的方式，这样能大大提高快速排序的执行效率，如我们所熟知的在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).