数据结构学习(十三)、快速排序

基本思想：通过一趟排序将待排记录分割成独立两个部分，其中一部分记录的关键字均比另一部分记录的关键字小，

则可分别对这两部分继续进行排序，重复操作以上操作，已达到整个序列有序的目的

void QuickSort(SqList *L){QSort(L,1,L->length);}

/* 对顺序表L中的子序列L->dara[low..high]最快速排序 */void QSort(SqList *L,int low,int high) { int pivot; if(low<high){ pivot = Partition(L,low,high); /*将L->data[low..high]一分为二，并算出分界点 */ QSort(L,low,pivot-1); /* 分界点左边进行排序 */ QSort(L,pivot+1,high); /* 分界点右边进行排序 */ } }

/*
交换L中子表的记录，使枢轴记录到位，并返回其所在的位置
此时，它之前（后）的记录均不大（小）于它
*/int Partition(SqList *L,int low,int high) { int pivotkey; pivotkey = L->r[low]; while(low<high){ while(low<high && L->r[high]>=pivotkey) high --; swap(L,low,high); while(low<high && L->r[low]<=pivotkey) low++; swap(L,low,high); } return low; }

 改进算法：

1、优化选取枢轴

  三数取中法，即先选取三个关键字进行排序，将中间数作为枢轴，一般取左端、中间、右端三个数。

/*
交换L中子表的记录，使枢轴记录到位，并返回其所在的位置
此时，它之前（后）的记录均不大（小）于它
*/int Partition(SqList *L,int low,int high){int pivotkey;int m = low +(high-low)/2;            /* 计算数组中间元素的下标 */if(L->data[low]>L->data[high])      /* 交换左右保证左边的较小 */swap(L,low,high);if(L->data[m]>L->data[high])      /* 交换中间 和右边保证中间的较小 */swap(L,m,high);if(L->data[low]>L->data[m])      /* 交换中间 和左边保证左边的较小 */swap(L,m,low);pivotkey = L->data[m];                   /* 用子表的中间值作为枢轴 */L->data[0] = pivotkey;                     /* 将轴关键字备份到L->data[0] */while(low<high){while(low<high && L->data[high]>=pivotkey)high --;L->data[low] = L->data[high];        /* 采用替换 而不采用交换 */while(low<high && L->data[low]<=pivotkey)low++;L->data[high] = L->data[low];         /* 采用替换 而不采用交换 */}L->data[low] = L->data[0];                /* 将枢轴数值替换回L->data[low] */return low;}

 

优化不必要的交换

转载于:https://www.cnblogs.com/huixuexidezhu/p/5969200.html

总结

以上是生活随笔为你收集整理的数据结构学习(十三)、快速排序的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。