经典排序之快速排序-创新互联
// 按照升序对a数组中[left, right)区间中的元素进行排序
void QuickSort(int* a, int left, int right) {
if (left+1>=right) {
return;
}
// 按照基准值对a数组的 [left, right)区间中的元素进行划分
int div = partion(a, left, right);
//以div为边界递归左右区间
QuickSort(a, left, div - 1);
QuickSort(a, div+1, right);
}
站在用户的角度思考问题,与客户深入沟通,找到河东网站设计与河东网站推广的解决方案,凭借多年的经验,让设计与互联网技术结合,创造个性化、用户体验好的作品,建站类型包括:网站建设、成都网站制作、企业官网、英文网站、手机端网站、网站推广、域名注册、虚拟空间、企业邮箱。业务覆盖河东地区。
二、按基准值划分区间
1.hoare版本首先选取一个key值,一般选取最左或最右。当选最左为key值时需要R先移动,当R所在位置的数值小于key值时停下,L移动找到比key值大的位置,然后交换L和R的数值,重复以上操作直到L和R相遇。一趟排序完成后key值被放在了正确的位置即左子序列均小于key值,右子序列均大于key值。这里值得注意的是当key值选取最左端时需要R先移动,选取最右端时需要L先移动。这是因为相遇时的数值与后移动的一方有关,如果key值选左而L先移动那么就会将比key值大的数字交换到最左边,这不符合规则。hoare版本划分区间代码:
int Partion(int* a, int left, int right) {
int key = left;
while (left< right) {
while (left< right && a[right] >= a[key]) {
right--;
}
while (left< right && a[left]<= a[key]) {
left++;
}
swap(&a[left], &a[right]);
}
swap(&a[key], &a[left]);
return left;
}
2.挖坑法挖坑法是hore法的一种变形 ,先将第一个数据存放在临时变量key中,形成一个坑位。R移动找到比key值小的就停下与坑位交换,L再移动找到比key值大的与坑位交换。相遇时将key值填入坑位。挖坑法划分区间代码:
int partion(int* a, int left, int right) {
int key = a[left];
int pivot = left;
while (left< right) {
while (left< right && a[right] >= key) {
right--;
}
a[pivot] = a[right];
pivot = right;
while (left< right && a[left]<= key) {
left++;
}
a[pivot] = a[left];
pivot = left;
}
a[pivot] = key;
return pivot;
}
3.前后指针法初始时pre指向序列起始位置,cur指向其后。cur移动找到比key值小的时停下,交换cur的值和pre后一位置的值。cur继续移动重复操作直到越界。
int partion(int* a, int left, int right) {
int pre = left;
int key = left;
int cur = pre + 1;
while (cur<= right) {
if (a[cur]< a[key] && ++pre != cur) {
swap(&a[pre], &a[cur]);
}
cur++;
}
swap(&a[key], &a[pre]);
return pre;
}
三、快速排序非递归实现递归版本中每个创建的栈帧都保存了当前区间的left和right值,我们也可以利用栈这种数据结构存入待处理的区间,每次取出区间后按key值划分区间,并将形成的两个新区间压入栈中,当划分的区间内没有值时停止压栈,重复操作直到栈空。
//写的栈的代码就不列出
void QuickSortNonR(int* a, int left, int right) {
ST st;//创建栈
StackInit(&st);//初始化栈
//将左右区间值压入栈中
StackPush(&st, right);
StackPush(&st, left);
while (!StackEmpty(&st)) {
//取出栈中存放的左右区间值
int left=StackTop(&st);
StackPop(&st);
int right=StackTop(&st);
StackPop(&st);
//划分区间,前面已讲
int div = partion(a, left, right);
//区间内有值继续压入栈中
if (div + 1< right) {
StackPush(&st, right);
StackPush(&st, div+1);
}
if (left + 1< div) {
StackPush(&st, div-1);
StackPush(&st, left);
}
}
StackDestroy(&st);//销毁栈
}
四、优化
1.三数取中法选key值理想情况下快速排序的时间复杂度为O(n*logn),但是如果待排序的序列是有序的,每次划分区间时选择左值为key值,划分后左子区间都是是不存在的,此时时间复杂度变成了O(n^2).
解决方法:
(1).随机选择key值,不推荐
(2).三数取中,选择left、right、left+(right-left)/2,这三个位置的中间大小的数值做key值。
2.递归到小的子区间时,考虑使用插入排序与二叉树结构类似,当递归到最后几层时,大量的小区间调用了函数,代价较大。于是就有了小区间优化的概念。当区间的序列个数小于一定数时(这里取十),采用插入排序。
快速排序优化版本完整代码:
int FindMiddle(int* a, int left, int right) {
int middle = left+(right-left)/2;
if (a[right] >a[middle]) {
if (a[middle] >a[left]) {
return middle;
}
else {
return left;
}
}
else {
if (a[right] >a[left]) {
return right;
}
else {
return left;
}
}
}
//前后指针法划分区间
int partion(int* a, int left, int right) {
int mid = FindMiddle(a,left,right);//取中
swap(&a[left],&a[mid);//交换mid位置的值和left的值
int pre = left;
int key=left;
int cur = pre + 1;
while (cur<= right) {
if (a[cur]< a[key] && ++pre != cur) {
swap(&a[pre], &a[cur]);
}
cur++;
}
swap(&a[key], &a[pre]);
return pre;
}
void QuickSort(int* a, int left, int right) {
if (left+1>=right) {
return;
}
//小区间优化,区间内的个数小于10时采用插入排序
if(right-left<10){
InsertSort(a,right-left+1);
}else{
int div = partion(a, left, right);
QuickSort(a, left, div - 1);
QuickSort(a, div+1, right);
}
}
特殊情况:当待排序序列为同一个值或者大量相同数值时,优化也不能解决此类问题,此时不建议采用快速排序。
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
分享标题:经典排序之快速排序-创新互联
链接分享:http://scyanting.com/article/dphghe.html