首页 > 代码库 > 快速排序
快速排序
快速排序基本思想是,一趟排序,选择一个元素作为枢轴,然后将所有比枢轴小的元素放到枢轴的左边,将比枢轴大的元素放到枢轴的右边,这样的一趟排序也称为一次划分。然后对该枢轴划分的左右子序列分别再进行划分,如此递归。就平均时间而言,快速排序是目前被认为是最好的一种内部排序方法,其平均时间是O(nlogn),最坏情况是O(n2)(是n方),最坏的情况就是如下倒序完后再正序排的情况。
C++代码如下:
#include "stdafx.h" #define MAXSIZE 20 typedef struct{ int r[MAXSIZE+1]; int len; }SqList; int Partition(SqList &L, int low, int high) { L.r[0] = L.r[low]; // 以第一个元素作为枢轴 int pivotkey = L.r[low];// 记录枢轴关键字 while (low < high) { while(low<high && L.r[high]>=pivotkey)
--high;// 找到从high位置开始向前第一个比枢轴小的元素 L.r[low] = L.r[high];// 将找到的比枢轴小的元素放到前边的空闲位置 while(low<high && L.r[low]<=pivotkey)
++low;// 找到从low位置开始向后第一个比枢轴大的元素 L.r[high] = L.r[low];// 将找到的比枢轴大的元素放到后边的空闲位置 } L.r[low] = L.r[0];// 将枢轴放回中间的空闲位置 return low; } void QSort(SqList &L, int low, int high) { if (low < high) { int pivotloc = Partition(L, low, high); QSort(L, low, pivotloc-1); QSort(L, pivotloc+1, high); } } int _tmain(int argc, _TCHAR* argv[]) { SqList sqList; for (int i=1; i<MAXSIZE+1; i++) { sqList.r[i] = MAXSIZE - i; } sqList.len = MAXSIZE; QSort(sqList, 1, sqList.len); return 0; }
// 附一次划分过程,第一行为index,第二行为待排序序列 // 0 1 2 3 4 5 6 7 // __ 49 38 65 97 76 13 27 // 开始时,0号位空闲(low:1, high:7) // 49 __ 38 65 97 76 13 27 // 将第1号元素作为枢轴,放到0号位,1号位冗余(low:1, high:7) // 49 27 38 65 97 76 13 __ // 发现27比49小,将7号位值放到1号位,7号位冗余(low:1, high:7) // 49 27 38 __ 97 76 13 65 // 发现65比49大,将3号位值放到7号位,3号位冗余(low:3, high:7) // 49 27 38 13 97 76 __ 65 // 发现13比49小,将6号位值放到3号位,6号位冗余(low:3, high:6) // 49 27 38 13 __ 76 97 65 // 发现97比49大,将4号位值放到6号位,4号位冗余(low:4, high:5) // __ 27 38 13 49 76 97 65 // low == high,将枢轴放到4号位,此时49左边的都比49小,右边的都比49大
快速排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。