怎么在别人网站做跳转,盐山做网站的,html网页设计作业代码,wordpress调查问卷插件一、定义#xff1a; 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法#xff08;也叫Hoare排序#xff09;#xff0c;是一种基于分治的排序方。其基本原理是将待排序的数组通过一趟排序分成两个独立的部分#xff0c;其中一部分的所有数据比另一部分的所有数…一、定义 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法也叫Hoare排序是一种基于分治的排序方。其基本原理是将待排序的数组通过一趟排序分成两个独立的部分其中一部分的所有数据比另一部分的所有数据都要小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列非递归也是可行的需要借助数据结构栈来实现 二、递归思想
排序只讲升序升序和降序也就是大于和小于逻辑上的差别
Hoare法
1、设置一个keyi记录头位置的数据然后设计2个指分别为针end和begin 一个从右边出发一个从左边出发
2、end所指向的数据若是小于keyi则停下然后begin走,所指向的数据若是大于keyi则停下
3、将end和begin指向的元素进行互换
4、继续让end走然后begin走重复2-3直到2者相遇若是相遇则将其与keyi指向的元素进交换完成一次✨ 5、keyi指向的数据的位置不是交换到了end和begin相遇的地方么我们从这里以此处为界限将区间分成2部分 也就是说我们要对左和右区间分别进行上述操作2个人走路对比交换操作完成2个区间2个区间又会分化成4个区间一直进行下去分到区间只有一个数据就实现了。有点类似与二叉树里的前序遍历的思想✨✨✨ 我们发现走完一次中间值的特点是左边全部小于他右边全部大于他
我们走路的先后是有讲究的2个人不是同时走的而是一个人先走一个人慢走也就是说满足这个特点的话讲究先后顺序因为决定了谁先遇见谁 那么如果我要左边先走了
✨✨✨用图来说话是不是不能满足了 hoare排序的难点在这里就是要注意谁先走为啥会有这种情况 ✨✨因为我们左边的任务是找大右边的任务是找小然后而且我们的2个好兄弟并不是同时走的是交替顺序走的哦相遇前的最后一次发生的交换如下这是互换好的 此时左边大于keyi的数换到了end的位置右边小于keyi的数换到了begin的位置。如果先走beginbegin走到end的位置停下也就是我们会将大于keyi的数和其交换位置所以不满足情况若是先走end那么end和begin相遇就是停在小于keyi的位置✨✨ 其实这个才是影响最终结果的情况 ✨总结“先出发是为了在你遇见我之前而遇见你”----我如果keyi的位置在首元素位置和keyi进行互换的元素需要是小于keyi指向的元素那么就需要任务为找大于keyi的数的end指针先走如果keyi在尾元素处最后与keyi交换的元素要大于keyi指向的元素那么我们需要的是任务为找大于keyi的begin指针先走。✨✨✨✨✨✨✨✨✨✨✨✨✨ Hoare的思路差不多讲完了是不是感觉已经可以自己写出代码了✨✨✨✨确实如此哈但是你这会递归吗 哈哈哈开玩笑啦❤️笔者当然相信你会的试着自己写一下嘛作为笔记我还是记录一下 ✨开始时就说过Hoare排序类似二叉树的前序先排序当keyi换好位置后将其当作“根节点”并分成2个区间2个区间又进行排序将keyi位置交换好再次以keyi根分成2个区间重复排序一直分到区间只有一个元素也就有序了这个图就是先分区间排序好后分成2部分因为每次排一次keyi交换后他的左边全是小于他的值 右边全是大于他的值每个区间的都有这样的特性因此传参传的是区间✨ 我们排号区间以节点作为区间分界点进行分割区间如6的左右2边分成了2块区间 优化1keyi的选取
✨✨其实上面的递归看着是个二叉树的样子keyi每次都换在区间中间的情况并不是每次都是这样根据待排序数组来看的哦 数据顺序千变万化
比如一个逆序的数组你将数据传入那么keyi直接交换到最后一个位置以最后一个位置分成一个区间;看图发现了么我还有重复排序情况很容易发生栈溢出的风险☠️☠️ 如果是 顺序的也是如此 时间复杂度退化到O(N^2) 因为keyi每次都是取首元素的值所以会出现上述这种弊端从keyi取值入手 1、随机值 keyi的值是随机的但是不推荐随机值不好控制 2、三数取中在区间里面左、右、中三个数取第二大的数到keyi里去 注意并不是keyi要换到这些位置而是将取到值换到keyi指向的位置因为我们本身的逻辑keyi就必须是在首元素位置✨✨ 三数取中就可以避免上面的情况数据左、右值以及中间值三个数里面找中间值 然后将中间值换到首元素位置逻辑不能变keyi的位置初始情况在首元素✨就可以保证排好序后keyi的位置接近区间的中间
//优化先三个数找中间
int GetMin(int* a, int left, int right)
{int min ((right - left) 1) left;if (a[min] a[left]){if (a[min] a[right]){return min;}else if (a[right]a[left]){return right;}else{return left;}}else{if (a[min] a[right]){return min;}else if (a[right] a[left]){return right;}else{return left;}}}
优化2小区间优化
每次分割二分以二叉树角度看最后一层是2^(h-1)个节点总节点是2^h那么我发现倒数三层占递归比例挺大的哎我能不能把这一段优化掉不用递归了降低栈溢出的风险
这里我们想到用一个时间复杂度为O(N^2)的排序来解决 当区间元素个数小于10个时我就用一个插入排序 。修改一下递归条件即可递归结束条件即可 挖坑法
因为有些大佬认为Hoare的方法不易理解就想到了挖坑法进行这里用到了坑位 思路key取出首元素2个指针begin指向首位置end指向尾位置 ✨占坑位的不能动刚开始没有坑位的是end当end走到比key小的位置我们将end指向的元素放到begin指向的坑位此时end变成坑位end不动begin走找到比key大的元素将begin指向的元素放到end指向的坑位直到二者相遇此时一起蹲坑将key放到坑里面✨ 前后指针法 思路2指针起始位置prev指向首元素cur在第二个元素位置先让cur走若是cur指向数据比key小则prev后移动一位然后将cur指向的元素和prev指向的元素进行交换当prev走过尾元素也就是走出区间将prev的值和key的值进行交换✨ 总结
后面2种写法都没有画过程看动图其实就能很好的理解哦很简单的这里就不要考虑先走的问题了 直接规定好了。当然啦✨✨三种方法的效率是一样的后面的方法是为了更好的理解Hoare的思想他们也就只是排序的写法改变了方式都是一样的逻辑没变✨ 三、非递归思想
✨我们通过递归可以发现递归的是区间对区间进行的修改那么接下来以下面这个数组作为例子 ✨ 递归变非递归 其实就是将其变成迭代的思路
我们二叉树的前序遍历就是根、左子树、右子树那么我们的思路就是先遍历[0,9]然后遍历[0,4]再是[0,1] [3,4]等等那么我们想到了创建一个栈来实现利用先进后出的特点可以将区间压进去先入右区间再入左先出来的就是左区间
先入【0.9】 取出来进行排序 排完以后找到5然后再入[6,9] 和 [0,4],此时区间变成2部分 [0,4]出栈交换后此时以下标2进行分区间入栈 是不是很好看懂就是先动左区间再动右区间处理一边再处理另一边其实就是深度优先遍历么
✨结束条件就是空栈结束喽
当然啦你可以用队列实现但是要注意队列是先进先出它是一层一层的进行排的
排序的和递归里的排序方法一样三种方法随便选一个都可以用我们的栈就是来模拟实现先序遍历的过程
四、代码实现
优化三数取中每种实现方法都需要用这个函数
//三数取中
int GetMin(int* a, int left, int right)
{int min ((right - left) 1) left;if (a[min] a[left]){if (a[min] a[right]){return min;}else if (a[right]a[left]){return right;}else{return left;}}else{if (a[min] a[right]){return min;}else if (a[right] a[left]){return right;}else{return left;}}} 1、Hoare法 void QuickSort1(int* a, int left, int right)
{//递归结束条件/*if (right left){return;}*///优化后递归结束条件变成了当剩下10个以内的元素需要排序时就使用插入排序if (right - left 1 10){InsertSort(a left, right - left 1);}else {//3个取中int mid GetMin(a, left, right);//将中的元素换到leftSwp(a[mid], a[left]);int keyi left;int begin left;int end right;while (begin end){//右边找小的左边找大的while (a[end] a[keyi] end begin){end--;}while (a[begin] a[keyi] end begin){begin;}//交换Swp(a[begin], a[end]);}Swp(a[keyi], a[begin]);QuickSort1(a, left, begin - 1);QuickSort1(a, end 1, right);}
}
2、挖坑法
//挖坑法(有一个人要蹲坑)效率差不多
void QuickSort2(int* a, int left, int right){if (right - left 1 10){InsertSort(a left, right - left 1);}else{int mid GetMin(a, left, right);Swp(a[left], a[mid]);int keyi a[left];int begin left;int end right;while (begin end){//仍然是左边找大右边找小while (begin end a[end] keyi){end--;}a[begin] a[end];while (begin end a[begin] keyi){begin;}a[end] a[begin];}a[end] keyi;QuickSort2(a, left, begin - 1);QuickSort2(a, end 1, right);}}3、前后指针法
//前后指针法
void QuickSort3(int* a, int left, int right)
{/*if (left right){return;}*/if (right - left 1 10){//小于10个数据进行插入排序InsertSort(a left, right - left 1);}else{int mid GetMin(a, left, right);Swp(a[mid], a[left]);int keyi left;int prev left;int cur left 1;//cur先走找小的while (cur right){//若小于a[keyi]则prev后移一位 再交换if (a[cur] a[keyi]){prev;Swp(a[prev], a[cur]);}cur;}Swp(a[prev], a[keyi]);QuickSort3(a, left, prev - 1);QuickSort3(a, prev 1, right);}
}4、非递归
#pragma once#includestdio.h
#includestdbool.h
#includestdlib.h
#includeassert.htypedef int LTDataType;
//顺序表栈
typedef struct SL
{LTDataType* a;int top;int capacity;
}SL;
//入栈
void SLPush(SL* p,LTDataType x)
{//不能传NULL,判空;assert(p);if (p-top p-capacity){//先判断是否为0好进行扩容int newnode p-capacity 0 ? 4 : 2 * (p-capacity);//扩容创建一个临时变量接收新的空间成功在将其交给p-aLTDataType* s (LTDataType*)realloc(p-a,newnode * sizeof(LTDataType));if (s NULL){perror(realloc);return;}p-a s;p-capacity newnode;}p-a[p-top] x;//指向下一个数据地址p-top;
}
//出栈(类似尾删)
void SLPop(SL* p)
{//是否为空assert(p);assert(p-top 0);p-top--;
}
//初始化
void SLInit(SL* p)
{p-a NULL;p-capacity 0;//p-top -1;//指向栈顶的数据p-top 0;//指向栈顶的下一个数据
}
//销毁
void SLDestroy(SL* p)
{assert(p);free(p-a);p-a NULL;p-capacity p-top 0;
}
//判空
bool SLEmpty(SL* p)
{//不能是空地址assert(p);//为0就是真(true)为1就是假(flase)return p-top 0;
}
//数据个数
int SLsize(SL* p)
{int size p-top;return size;
}
//取数据
LTDataType SLPot(SL*p)
{assert(p);return p-a[p-top-1];
}//非递归将递归变成迭代最重要的是区间
void QuickSortNonR(int* a, int left, int right)
{SL pts;SLInit(pts);SLPush(pts,right);SLPush(pts, left);while (!SLEmpty(pts)){int begin SLPot(pts);SLPop(pts);int end SLPot(pts);SLPop(pts);int mid GetMin(a, begin,end);Swp(a[mid], a[begin]);int keyi begin;int prev begin;int cur begin 1;//cur先走找小的while (cur end){//若小于a[keyi]则prev后移一位 再交换if (a[cur] a[keyi]){prev;Swp(a[prev], a[cur]);}cur;}Swp(a[prev], a[keyi]);if (prev 1 end){SLPush(pts, end);SLPush(pts, prev 1);}if (prev - 1 begin){SLPush(pts, prev-1);SLPush(pts, 0);}}SLDestroy(pts);}
