网站里图片做超链接,专业开发网站报价单,wordpress去除更新提示,软件开发的基本一#xff1a;基本思想 任取待排序元素序列中的某元素作为基准值#xff0c;按照该排序码将待排序集合分割成两子序列#xff0c;左子序列中所有元素均小于基准值#xff0c;右 子序列中所有元素均大于基准值#xff0c;然后最左右子序列重复该过程#xff0c;直到所有元…一基本思想 任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右 子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。 思想解释 1确认一个基准值一般默认最左面的值 2通过 排序函数最后会使得该基准值停留在正确的位置并且基准值左面的值都小于基准值基准值的右面的值都大于基准值(排序函数会遍历整个数组所以时间复杂度为O(N)) 3然后该数所处的位置就不用管了然后递归用 排序函数 解决该数所处位置的左右两个数组 4最后得到一个有序数组 分割数组的两种情况
理想情况 解释该种情况是一种理想的情况
我们每次在最左取的基准值在经过 排序函数 之后都会停留在数组的中间位置这样的话一个元素总数为N的数组会被分为logN层每层的时间复杂度为O(N)总的复杂度就是ON*logN。
极端情况 解释 该种情况是一种极端的情况
我们每次在最左取的基准值在经过 排序函数 之后还是停留在原地按照这种极端情况没有递归解决左右数组这一说了数组只会呈-1的递减每次都只是递归解决基准值右面的数组所以这个数组被分为N层每层的时间复杂度为O(N)总的复杂度就是ON^2。
那理想情况我们也不可能取到又要避免极端情况这时候就需要三数取中了。 二三数取中的意义
解释
选择三个元素通常选择数组的第一个元素、最后一个元素以及位于中间的元素。计算中位数比较这三个元素找到它们的中位数。交换基准将中位数与数组的第一个元素或最后一个元素交换使得中位数成为基准元素。
这样的话就能避免极端情况了,虽然达不到理想的情况但是时间复杂度和理想情况的同一个量级
代码
int GetMidi(int* a, int left, int right)
{// 计算中间元素的下标int mid (left right) / 2;// 比较三个元素left, mid, right// 首先比较left和midif (a[left] a[mid]){// 如果left mid再比较mid和rightif (a[mid] a[right]){// 如果left mid right则mid是中间值return mid;}else if (a[left] a[right]) // 如果left right则mid是最大值{// 在这种情况下left是中间值return left;}else{// 如果left right则right是中间值return right;}}else // 如果a[left] a[mid]{// 比较mid和rightif (a[mid] a[right]){// 如果mid right则mid是中间值return mid;}else if (a[left] a[right]) // 如果left right则mid是最小值{// 在这种情况下left是中间值return left;}else{// 如果left right则right是中间值return right;}}
}
三排序函数单趟的三种方法
1Hoare法 解释
1因为最后的6会处于正确的位置6的左面的值都6。所以left向右走的时候肯定是找6的值right向左走的时候肯定是找6的值二者都找到了L一定会找到6的R也一定会找到6de,二者不可能存在只有L或者只有R找到的情况因为三数取中已经让基准值避免了取到最大或者最小的这种极端情况所以二者都会找到然后彼此交换
2最后直到left right 代表二者相遇此时退出循环
3将基准值 6 放到正确的位置 也就是相遇的位置
4返回基准值6的位置这样才能分开数组去递归基准值左右的数组
相遇的疑问
Q1为什么相遇坐标的值一定能和基准值交换也就是说为什么能保证相遇坐标的值一定比基准值6小
A1右面R先走做到的
右面R先走此时相遇可以分为两种情况
第一种L走到R处相遇
因为R先走所以要满足第一种情况L走到R处相遇一定是在某一次寻找中R找到了比基准值小的值然后停下此时L找不到比key大的最后和R相遇此时相遇处也就是R之前找到的比基准值小的位置所以此时一定是可以和基准值进行交换的
第二种R走到L处相遇
在某一次寻找中R开始找比基准值小的值但是一直没有找到直到走到了L处与其相遇此时的L处一定不会是最左面因为三数取中后L肯定在上一轮中向右走并且找到了比基准值大的值然后R也在上一轮中找到了比基准值小的值L和R进行了交换L处的值是R找到的比基准值小的值所以此一轮中的R走到L处与其相遇相遇位置处也就是L处的值一定是比基准值小的所以此时一定是可以和基准值进行交换的。
代码
int PartSort1(int* a, int left, int right)
{// 使用三数取中法获取基准元素的正确位置int Mid GetMidi(a, left, right);// 将基准元素交换到数组的最左边Swap(a[left], a[Mid]);// 设置基准元素的索引为keyiint keyi left;// 当left小于right时进行单趟排序while (left right){// 从右向左扫描找到第一个小于基准元素的值while (left right a[right] a[keyi]){right--;}// 注意这里使用连接两个条件并且顺序很重要// 因为如果left right我们就不再需要继续比较// 此时a[right] a[keyi]放在前面的话会越界访问// 从左向右扫描找到第一个大于基准元素的值while (left right a[left] a[keyi]){left;}// 交换两个元素将大于基准的元素放到右边小于基准的元素放到左边Swap(a[left], a[right]);}// 最后将基准元素放到正确的位置left此时指向的位置Swap(a[keyi], a[left]);// 返回基准元素的最终位置return left;
}
内部while循环的条件疑问
Q2最外面的while条件有了left right为什么内部循环的while里面还有left right
A2:因为如果内部循环while没有left right的话那么一直找不到会越界最外面的while只能判断一次无法彻底控制所以循环里面的while里面应该是leftright a【right】key
Q3为什么内部循环的while条件是和而不是单纯的和
A3相等的值交换没有意义会造成死循环因为交换之后当前位置的值会继续判断才会往下走如果相同的值当需要交换那交换之后还是会重复的交换所以应该是和
总结
升序排序 基准值放在最左面 right指针先移动寻找小于基准值的元素因为我们要把小于基准值的元素放到左边。left指针后移动寻找大于基准值的元素因为我们要把大于基准值的元素放到右边。 基准值放在最右面 left指针先移动寻找大于基准值的元素因为我们要把大于基准值的元素放到右边。right指针后移动寻找小于基准值的元素因为我们要把小于基准值的元素放到左边。
降序排序 基准值放在最左面 right指针先移动寻找大于基准值的元素因为我们要把大于基准值的元素放到左边。left指针后移动寻找小于基准值的元素因为我们要把小于基准值的元素放到右边。 基准值放在最右面 left指针先移动寻找小于基准值的元素因为我们要把小于基准值的元素放到右边。right指针后移动寻找大于基准值的元素因为我们要把大于基准值的元素放到左边。 2挖坑法 解释
1基准值得先保存到一个临时变量key中而且初识基准值的下标要保存到一个临时变量hole坑位中
2依旧是R先走找小找到了就把该值放进下标为hole的位置上不用担心覆盖掉hole位置的元素因为hole位置的元素已经被保存到了临时变量中了然后再更新holehole right
3L也是类似
4最后二者相遇时此相遇下标一定是坑位将我们一开始的key基准值放进这个相遇的坑位中即可此时基准值就来到了正确的位置
5返回相遇位置hole这样才能分开数组去递归基准值左右的数组
代码
int PartSort2(int* a, int left, int right)
{// 使用三数取中法获取基准元素的正确位置int Mid GetMidi(a, left, right);// 将基准元素交换到数组的最左边Swap(a[left], a[Mid]);// 把基准值保存到临时变量key中int key a[left];// 将基准值的下标保存到临时变量hole坑位中int hole left;// 当left小于right时进行单趟排序while (left right){// 从右向左扫描找到第一个小于基准元素的值while (left right a[right] key){--right;}// 将找到的元素放到坑中a[hole] a[right];// 更新坑的位置hole right;// 从左向右扫描找到第一个大于基准元素的值while (left right a[left] key){left;}// 将找到的元素放到坑中a[hole] a[left];// 更新坑的位置hole left;}// 最后将基准元素放到正确的位置hole此时指向的位置a[hole] key;// 返回基准元素的最终位置return hole;
}
3前后指针法 解释
1cur不断地找小于基准值的值将其不断地丢到左面去
2prev和cur的间隔有两种情况
第一种在cur还没有遇到比key大的值的时候prev紧跟着cur
第二种在cur遇到了比key大的值的时候prefv和cur之间隔着一个或多个比key大的值
3本质就是把一段大于key的区间通过prev和cur交换的方法推到右面去同时小的也甩到 了左面去
4如图所示: 可以看出来一段比key6大的区间7 8 9 10都逐渐的被推到了右面同时原先处于右面的比key6小的值 3 4 5被甩到了左面然后再把最左面的基准值放进prev中即可此时6来到了正确的位置。 代码
//前后指针法实现
int PartSort3(int* a, int left, int right)
{// 1. 获取基准值int midi GetMidi(a, left, right);// 将基准元素交换到数组的最左边Swap(a[left], a[midi]);// 2. 初始化指针int prev left; // 设置前指针prev为起始位置int cur prev 1; // 设置后指针cur为起始位置的后一个元素// 3. 单趟排序//curright代表还有元素需要比较while (cur right){// 4. 比较和交换if (a[cur] a[keyi] prev ! cur) //如果后指针cur所指向的元素小于基准值//并且prev1不等于cur才会进行交换//那么就将prev的后一个prev1和cur进行交换{//交换Swap(a[prev], a[cur]); }// 5. 移动指针cur; // 继续移动后指针cur}// 6. 交换基准值Swap(a[prev], a[keyi]);// 7. 返回基准值位置return prev;
}
代码解释
对于这一步 if (a[cur] a[keyi] prev ! cur) 进入交换的判断条件的解释
1左面是a[cur] a[keyi] 代表cur找到了比key小的值满足的左面
2右面是 prev ! cur 这是一个前置代表prev1 不等于 cur也就是说prev的下一个不是cur满足的右面需要注意的是这不仅是判断的时候的在进行交换的时候prev也已经了
3为什么满足以上两点才能进入交换
因为即使cur找到了比key小的值但是此时prev就在他的前面交换也没有意义Swap(a[prev], a[cur]); 这一步只会让cur自己交换所以我们得让二者之间有一定的间隔此时prev在经过了循环的判断条件中的前置之后指向一段比key大的区间的第一个值然后再与cur交换才有意义。
如图所示 四递归实现快速排序
1普通递归
Hoare的递归快排
//递归快排(霍尔)
void QuickSort1(int* a, int left, int right)
{if (left right)return;int keyi PartSort1(a, left, right);QuickSort1(a, left, keyi - 1);QuickSort1(a, keyi 1, right);}
挖坑法的递归快排
//递归快排挖坑
void QuickSort2(int* a, int left, int right)
{if (left right)return;int keyi PartSort2(a, left, right);QuickSort2(a, left, keyi - 1);QuickSort2(a, keyi 1, right);}
前后指针的递归快排
//递归快排前后指针
void QuickSort3(int* a, int left, int right)
{if (left right)return;int keyi PartSort3(a, left, right);QuickSort3(a, left, keyi - 1);QuickSort3(a, keyi 1, right);}
总结
递归的去执行单趟最后得到有序的数组排序函数把key位置确定了返回了key的下标keyi所以左数组是left~keyi-1右数组是keyi1~right。
2优化递归
意义
我们知道一个二叉树的最后三层占据了总结点的%87.5 所以优化递归的思路当接收到的数组 10个的时候我们不再递归10个开始递归到结束就是最后的3层而是采取插入排序来进行排序插入不懂请看插入排序-CSDN博客 代码
void BetterQuickSort(int* a, int left, int right)
{// 如果left大于或等于right则数组为空或只有一个元素无需排序直接返回if (left right)return;// 如果数组长度大于10则使用PartSort1进行快速排序if ((right - left 1) 10){// 调用PartSort1函数获取基准值的位置int keyi PartSort1(a, left, right);// 对基准值左边的部分进行快速排序QuickSort1(a, left, keyi - 1);// 对基准值右边的部分进行快速排序QuickSort1(a, keyi 1, right);}// 如果数组长度小于或等于10则使用插入排序else{// 对left到right之间的部分进行插入排序InsertSort(a left, right - left 1);}
}
五非递归实现快速排序
以上的所有快速排序都是递归快排也可以借助栈来实现非递归的快排
void QuickSortNoneR(int* a, int left, int right)
{// 1. 初始化栈ST st;STInit(st);// 2. 入栈将right和left的值分别入栈STPush(st, right);STPush(st, left);// 3. 栈不为空时继续处理while (!STEmpty(st)){// 4. 出栈从栈顶取出begin和end的值int begin STTop(st);STPop(st);int end STTop(st);STPop(st);// 5. 调用PartSort1函数获取基准值的位置int keyi PartSort1(a, begin, end);// 6. 入栈根据keyi的位置将右半部分和左半部分的起始位置入栈if (keyi 1 end){STPush(st, end);STPush(st, keyi 1);}if (keyi - 1 begin){STPush(st, keyi - 1);STPush(st, begin);}}// 7. 销毁栈STDestroy(st);
}
解释
1 栈是后进先出所以我们入栈和出栈的时候都要格外的注意
2我们先入right再入left这样就能先取到left再取到right然后进行单趟的排序函数
3然后通过单趟的排序函数返回的key1基准值来到正确位置后的下标来进行左右数组的划分
3因为我们递归是先取排序左数组再去排序右数组所以我们先入栈右数组的再入栈左数组这样下一次出栈的时候就是先得到左数组的再得到右数组
4销毁栈
总结就是用栈的性质不断去出栈入栈结合单趟的排序函数来实现快排。
六运行测试
1十万数据数组 2百万数据数组
3千万数据数组 时间的单位是ms 七代码分享
1Stack.c
#define _CRT_SECURE_NO_WARNINGS 1
#include Stack.hvoid STInit(ST* ps)
{assert(ps);ps-a NULL;ps-capacity 0;ps-top 0;
}void STDestroy(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-top ps-capacity 0;
}void STPush(ST* ps, STDataType x)
{assert(ps);if (ps-top ps-capacity){int newCapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDataType* tmp (STDataType*)realloc(ps-a, sizeof(STDataType) * newCapacity);if (tmp NULL){perror(realloc fail);exit(-1);}ps-a tmp;ps-capacity newCapacity;}ps-a[ps-top] x;ps-top;
}void STPop(ST* ps)
{assert(ps);// assert(ps-top 0);--ps-top;
}STDataType STTop(ST* ps)
{assert(ps);// assert(ps-top 0);return ps-a[ps-top - 1];
}int STSize(ST* ps)
{assert(ps);return ps-top;
}bool STEmpty(ST* ps)
{assert(ps);return ps-top 0;
}
2:Stack.h
#pragma once#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h//#define N 10
//struct Stack
//{
// int a[N];
// int top;
//};typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;void STInit(ST* ps);
void STDestroy(ST* ps);
void STPush(ST* ps, STDataType x);
void STPop(ST* ps);
STDataType STTop(ST* ps);int STSize(ST* ps);
bool STEmpty(ST* ps);3快排的所有实现
#includestdio.h
#includestdlib.h
#includetime.h
#include Stack.h
//插入函数
void InsertSort(int* arr, int N)
{for (int i 0; i N - 1; i){int end i;//即将排序的元素保留在tmpint tmp arr[end 1];//end0代表还有元素未比较while (end 0){if (tmp arr[end]){arr[end 1] arr[end];end--;}else{break;}}//来到这里分为两种情况 //1break-遇到比元素tmp小或和tmp相等的将m放在它的后面//2全部比较完了都没有遇到tmp的最后tmp放在数组第一个位置arr[end 1] tmp;}}
//交换
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}
void PrintArray(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}
//三数取中
int GetMidi(int* a, int left, int right)
{// 计算中间元素的下标int mid (left right) / 2;// 比较三个元素left, mid, right// 首先比较left和midif (a[left] a[mid]){// 如果left mid再比较mid和rightif (a[mid] a[right]){// 如果left mid right则mid是中间值return mid;}else if (a[left] a[right]) // 如果left right则mid是最大值{// 在这种情况下left是中间值return left;}else{// 如果left right则right是中间值return right;}}else // 如果a[left] a[mid]{// 比较mid和rightif (a[mid] a[right]){// 如果mid right则mid是中间值return mid;}else if (a[left] a[right]) // 如果left right则mid是最小值{// 在这种情况下left是中间值return left;}else{// 如果left right则right是中间值return right;}}
}
//全部忘加[],第二个写成if//第一种单趟霍尔法
int PartSort1(int* a, int left, int right)
{// 使用三数取中法获取基准元素的正确位置int Mid GetMidi(a, left, right);// 将基准元素交换到数组的最左边Swap(a[left], a[Mid]);// 设置基准元素的索引为keyiint keyi left;// 当left小于right时进行单趟排序while (left right){// 从右向左扫描找到第一个小于基准元素的值while (left right a[right] a[keyi]){right--;}// 注意这里使用连接两个条件并且顺序很重要// 因为如果left right我们就不再需要继续比较// 此时a[right] a[keyi]放在前面的话会越界访问// 从左向右扫描找到第一个大于基准元素的值while (left right a[left] a[keyi]){left;}// 交换两个元素将大于基准的元素放到右边小于基准的元素放到左边Swap(a[left], a[right]);}// 最后将基准元素放到正确的位置left此时指向的位置Swap(a[keyi], a[left]);// 返回基准元素的最终位置return left;
}
//挖坑法
int PartSort2(int* a, int left, int right)
{// 使用三数取中法获取基准元素的正确位置int Mid GetMidi(a, left, right);// 将基准元素交换到数组的最左边Swap(a[left], a[Mid]);// 设置基准元素的值int key a[left];// 设置基准元素的位置int hole left;// 当left小于right时进行单趟排序while (left right){// 从右向左扫描找到第一个小于基准元素的值while (left right a[right] key){--right;}// 将找到的元素放到坑中a[hole] a[right];// 更新坑的位置hole right;// 从左向右扫描找到第一个大于基准元素的值while (left right a[left] key){left;}// 将找到的元素放到坑中a[hole] a[left];// 更新坑的位置hole left;}// 最后将基准元素放到正确的位置hole此时指向的位置a[hole] key;// 返回基准元素的最终位置return hole;
}
前后指针法
//int partsort3(int* a, int left, int right)
//{
// int prev left;
// int cur left 1;
//
// while (cur right)
// {
// if (a[cur] a[left] prev ! cur)
// {
// Swap(a[cur], a[prev]);
//
// }
// cur;
// }
// Swap(a[prev], a[left]);
// //最后比left元素小的 都集中在了prev的下面及其左面此时prev和left交换最左面的元素一定是来到了正确的位置
// return prev;
// //a[cur] a[left] 后 cur肯定是要的
// //如果此时prev1 cur就代表prev和cur之间还没有比下标为left的元素大的元素所以没必要交换
// //当prev!cur 的时候才交换其次prev!cur 不仅判断还1了
//}
//第三种单趟前后指针法
//int partsort3(int* a, int left, int right)
//{
// int Mid GetMidi(a, left, right);
// Swap(a[left], a[Mid]);
//
// int prev left;
// int cur prev 1;
// int keyi left;
//
// while (cur right)
// {
// if (a[cur] a[keyi] prev ! cur)
// {
// Swap(a[cur], a[prev]);
//
// }
// cur;
// }
// Swap(a[prev], a[keyi]);
// return prev;
//}
//前后指针法
int PartSort3(int* a, int left, int right)
{// 1. 获取基准值int midi GetMidi(a, left, right);// 将基准值与数组的第一个元素交换确保基准值位于起始位置Swap(a[left], a[midi]);// 2. 初始化指针int prev left; // 设置前指针prev为起始位置int cur prev 1; // 设置后指针cur为起始位置的后一个元素int keyi left;// 3. 单趟排序while (cur right){// 4. 比较和交换if (a[cur] a[keyi] prev ! cur) // 如果后指针cur所指向的元素小于基准值{Swap(a[prev], a[cur]); // 并且前指针prev还没有到达cur的位置// 则将前指针向前移动一位并与后指针指向的元素交换}// 5. 移动指针cur; // 继续移动后指针cur}// 6. 交换基准值Swap(a[prev], a[keyi]);// 7. 返回基准值位置return prev;
}// 交换两个元素
void Swap(int* x, int* y)
{int temp *x;*x *y;*y temp;
}
//递归快排(霍尔)
void QuickSort1(int* a, int left, int right)
{if (left right)return;int keyi PartSort1(a, left, right);QuickSort1(a, left, keyi - 1);QuickSort1(a, keyi 1, right);}
//递归快排挖坑
void QuickSort2(int* a, int left, int right)
{if (left right)return;int keyi PartSort2(a, left, right);QuickSort2(a, left, keyi - 1);QuickSort2(a, keyi 1, right);}
//递归快排前后指针
void QuickSort3(int* a, int left, int right)
{if (left right)return;int keyi PartSort3(a, left, right);QuickSort3(a, left, keyi - 1);QuickSort3(a, keyi 1, right);}
//优化递归快排
void BetterQuickSort(int* a, int left, int right)
{if (left right)return;if ((right - left 1) 10){int keyi PartSort1(a, left, right);QuickSort1(a, left, keyi - 1);QuickSort1(a, keyi 1, right);}else{InsertSort(a left, right - left 1);}//左面确认起点右面确认个数
}
//非递归快排借助栈
void QuickSortNoneR(int* a, int left, int right)
{// 1. 初始化栈ST st;STInit(st);// 2. 入栈将right和left的值分别入栈STPush(st, right);STPush(st, left);// 3. 栈不为空时继续处理while (!STEmpty(st)){// 4. 出栈从栈顶取出begin和end的值int begin STTop(st);STPop(st);int end STTop(st);STPop(st);// 5. 调用PartSort1函数获取基准值的位置int keyi PartSort1(a, begin, end);// 6. 入栈根据keyi的位置将右半部分和左半部分的起始位置入栈if (keyi 1 end){STPush(st, end);STPush(st, keyi 1);}if (keyi - 1 begin){STPush(st, keyi - 1);STPush(st, begin);}}// 7. 销毁栈STDestroy(st);
}
//非递归快排(借助栈)
//void QuickSortNoneR(int* a, int begin, int end)
//{
// ST st;
// STInit(st);
// STPush(st, end);
// STPush(st, begin);
// while (!STEmpty(st))
// {
// int left STTop(st);
// STPop(st);
//
// int right STTop(st);
// STPop(st);
//
// int keyi PartSort1(a, left, right);
// // [lefy,keyi-1] keyi [keyi1, right]
// if (keyi 1 right)
// {
// STPush(st, right);
// STPush(st, keyi 1);
// }
//
// if (left keyi - 1)
// {
// STPush(st, keyi - 1);
// STPush(st, left);
// }
// }
//
// STDestroy(st);
//}
//测试少量快排
void Test1()
{int a[] { 6,1,2,7,9,3,4,5,10,8 };QuickSortNoneR(a, 0, sizeof(a) / sizeof(int) - 1);PrintArray(a, sizeof(a) / sizeof(int));
}
//测试大量快排
void Test2()
{srand(time(0));int N 10000000;int* a1 (int*)malloc(sizeof(int) * N);for (int i N - 1; i 0; --i){a1[i] rand() i;}int begin1 clock();QuickSort1(a1, 0, N - 1);int end1 clock();printf(QuickSort1:%d\n, end1 - begin1);free(a1);
}
//测试优化递归后的大量快排
void Test3()
{srand(time(0));int N 10000000;int* a1 (int*)malloc(sizeof(int) * N);for (int i N - 1; i 0; --i){a1[i] rand() i;}int begin1 clock();BetterQuickSort(a1, 0, N - 1);int end1 clock();printf(BetterQuickSort:%d\n, end1 - begin1);free(a1);}
//测试非递归快排
void Test4()
{srand(time(0));int N 10000000;int* a1 (int*)malloc(sizeof(int) * N);for (int i N - 1; i 0; --i){a1[i] rand() i;}int begin1 clock();QuickSortNoneR(a1, 0, N - 1);int end1 clock();printf(QuickSortNoneR:%d\n, end1 - begin1);free(a1);
}
int main()
{//测试递归少量快排Test1();//测试递归大量快排Test2();//测试优化递归大量快排Test3();//测试非递归大量快排Test4();return 0;
}
谢谢观看~~~~
