网站功能设计怎么写,网站建设专有名词,家政公司网站的建设,wordpress中文版 docker一、快速排序有三种方法#xff1a;hoare版本、挖坑法、前后指针版本
但是三种方法的核心思想都是一样的#xff0c;都是将该数组分为左右两半递归式的排序。
1.hoare版本 该方法是先保存a[keyi]位置的值#xff0c;然后右边先开动找小#xff0c;找到小后#xff0c;左…一、快速排序有三种方法hoare版本、挖坑法、前后指针版本
但是三种方法的核心思想都是一样的都是将该数组分为左右两半递归式的排序。
1.hoare版本 该方法是先保存a[keyi]位置的值然后右边先开动找小找到小后左边开动找大找到大之后两数互换最后相遇位置与a[keyi]位置互换即默认每次相遇位置都是小于a[keyi]
int PartSort1(int* a, int begin, int end)
{int midi GetMidi(a, begin, end);Swap(a[midi], a[begin]);int left begin, right end;int keyi begin;while (left right){// 右边找小while (left right a[right] a[keyi]){--right;}// 左边找大while (left right a[left] a[keyi]){left;}Swap(a[left], a[right]);}Swap(a[left], a[keyi]);return left;
}
那为什么默认相遇位置比a[keyi]小呢 2.挖坑法
该方法是先把第一个数据存放在临时变量key中形成一个坑位然后r向左走r--直到找到比key小的将r的值放入l中r处形成一个坑位然后l向右走l直到找到比key大的……以此循环。 int PartSort2(int* a, int begin, int end)
{int midi GetMidi(a, begin, end);Swap(a[midi], a[begin]);int key a[begin];int hole begin;while (begin end){// 右边找小填到左边的坑while (begin end a[end] key){--end;}a[hole] a[end];hole end;// 左边找大填到右边的坑while (begin end a[begin] key){begin;}a[hole] a[begin];hole begin;}a[hole] key;return hole;
}3.前后指针版本
该方法是将第一个数据保存至临时变量key中利用两个指针prev begincur prev 1cur向前进cur遇到比key小时让a[pre
void QuickSort(int* a, int begin, int end)
{if (begin end)return;int keyi PartSortn(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
}v1]与a[cur]位置的数据进行交换以此往复循环。 快排
void QuickSort(int* a, int begin, int end)
{if (begin end)return;int keyi PartSortn(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
}找三数中值
int GetMidi(int* a, int begin, int end)
{int midi (begin end) / 2;// begin midi end 三个数选中位数if (a[begin] a[midi]){if (a[midi] a[end])return midi;else if (a[begin] a[end])return begin;elsereturn end;}else // a[begin] a[midi]{if (a[midi] a[end])return midi;else if (a[begin] a[end])return begin;elsereturn end;}
}
二、快排的非递归
为了实现快排的非递归我们就需要借助基本数据结果栈来解决
每次都可以插入头和尾begin、end的数据进入STPush由于后进先出原则因此我们先插入end再插入begin取STTop赋值于leftPop数据再取STTop赋值于rightPop数据随后进行快排这里其实就是一种递归思想的非递归。
代码
void QuickSortNonR(int* a, int begin, int end)
{ST s;STInit(s);STPush(s, end);STPush(s, begin);while (!STEmpty(s)){int left STTop(s);STPop(s);int right STTop(s);STPop(s);int keyi PartSort3(a, left, right);// [left, keyi-1] keyi [keyi1, right]if (left keyi - 1){STPush(s, keyi - 1);STPush(s, left);}if (keyi 1 right){STPush(s, right);STPush(s, keyi 1);}}STDestroy(s);
}
C语言中栈的实现 //Stack.h
#pragma once
#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.htypedef int STDataType;typedef struct Stack
{STDataType* a;int top; // 标识栈顶位置的int capacity;
}ST;void STInit(ST* pst);
void STDestroy(ST* pst);// 栈顶插入删除
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
STDataType STTop(ST* pst);bool STEmpty(ST* pst);
int STSize(ST* pst);
//Stack.c
#includeStack.hvoid STInit(ST* pst)
{assert(pst);pst-a NULL;pst-capacity 0;// 表示top指向栈顶元素的下一个位置pst-top 0;// 表示top指向栈顶元素//pst-top -1;
}void STDestroy(ST* pst)
{assert(pst);free(pst-a);pst-a NULL;pst-top pst-capacity 0;
}// 栈顶插入
void STPush(ST* pst, STDataType x)
{assert(pst);if (pst-top pst-capacity){int newcapacity pst-capacity 0 ? 4 : pst-capacity * 2;STDataType* tmp (STDataType*)realloc(pst-a, sizeof(STDataType) * newcapacity);if (tmp NULL){perror(realloc fail);return;}pst-a tmp;pst-capacity newcapacity;}pst-a[pst-top] x;pst-top;
}//栈顶删除
void STPop(ST* pst)
{assert(pst);// 不为空assert(pst-top 0);pst-top--;
}STDataType STTop(ST* pst)
{assert(pst);// 不为空assert(pst-top 0);return pst-a[pst-top - 1];
}bool STEmpty(ST* pst)
{assert(pst);/*if (pst-top 0){return true;}else{return false;}*/return pst-top 0;
}int STSize(ST* pst)
{assert(pst);return pst-top;
}
