漯河网站建设zrgu投资者互动平台

当前位置： 首页 > news >正文

漯河网站建设zrgu,投资者互动平台,全国信息企业查询平台,微信小程序个人网站开发这篇文章#xff0c;以对话的方式#xff0c;详细着讲解了快速排序以及排序排序的一些优化。 一禅#xff1a;归并排序是一种基于分治思想的排序#xff0c;处理的时候可以采取递归的方式来处理子问题。我弄个例子吧#xff0c;好理解点。例如对于这个数组arr[] { 4… 这篇文章以对话的方式详细着讲解了快速排序以及排序排序的一些优化。 一禅归并排序是一种基于分治思想的排序处理的时候可以采取递归的方式来处理子问题。我弄个例子吧好理解点。例如对于这个数组arr[] { 41327580}。 我们把它切割成两部分。 把左半部分和右半部分分别排序好。 之后再用一个临时数组把这两个有序的子数组汇总成一个有序的大数组 排好之后在复制原源arr数组 这时源数组就排序完毕了 一禅左半部分和右半部分的排序相当于一个原问题的一个子问题的也是采取同样的方式把左半部分分成两部分然后… 直到分割子数组只有一个元素或0个元素时这时子数组就是有序的了(因为只有一个元素或0个肯定是有序的啊)就不用再分割了直接返回就可以了(当然我在讲解这个归并排序的过程中是假设你大致了解归并排序的前提下的了) 一禅把一个n个元素的数组分割成只有一个元素的数组那么我需要切logn次每次把两个有序的子数组汇总成一个大的有序数组所需的时间复杂度为O(n)。所以总的时间复杂度为O(nlogn) 快速排序 小白那倒不是快速排序的平均时间复杂度也是O(nlogn)不过他不需要像归并排序那样还需要一个临时的数组来辅助排序这可以节省掉一些空间的消耗而且他不像归并排序那样把两部分有序子数组汇总到临时数组之后还得在复制回源数组这也可以节省掉很多时间。 小白快速排序也是和归并排序差不多基于分治的思想以及采取递归的方式来处理子问题。例如对于一个待排序的源数组arr { 4132768}。 我们可以随便选一个元素假如我们选数组的第一个元素吧我们把这个元素称之为”主元“吧。 然后将大于或等于主元的元素放在右边把小于或等于主元的元素放在左边。 通过这种规则的调整之后左边的元素都小于或等于主元右边的元素都大于或等于主元很显然此时主元所处的位置是一个有序的位置,即主元已经处于排好序的位置了。 主元把数组分成了两半部分。把一个大的数组通过主元分割成两小部分的这个操作我们也称之为分割操作(partition)。 接下来我们通过递归的方式对左右两部分采取同样的方式每次选取一个主元 元素使他处于有序的位置。
那什么时候递归结束呢当然是递归到子数组只有一个元素或者0个元素了
分割操作单向调整 一禅就按照你说的选一个主元你刚才选的是第一个元素为主元这次我选最后一个为主元吧哈哈。假设数组arr的范围为[left, right]即起始下标为left末尾下标为right。源数组如下 然后可以用一个下标 i 指向 left即 i left ;用一个下标 j 也指向l eft即j left 接下来 j 从左向右遍历遍历的范围为 [left, right-1] 遍历的过程中如果遇到比主元小的元素则把该元素与 i 指向的元素交换并且 i i 1 当j指向1时1比4小此时把i和j指向的元素交换之后 i。 就这样让j一直向右遍历直到 j right 遍历完成之后把 i 指向的元素与主元进行交换交换之后i 左边的元素一定小于主元而 i 右边的元素一定大于或等于主元。这样就 i 完成了一次分割了。 一禅一言不合就把代码撸好了第一版代码如下 //分割操作方法一单向调整 int partion(int a[], int left, int right) {int temp,pivot;//pivot存放主元int i,j;i left;pivot a[right];for(j left;j right;j){if(a[j] pivot){ //交换值temp a[i];a[i] a[j];a[j] temp;i;}}a[right] a[i];a[i] pivot;return i;//把主元的下标返回 } //快速排序 void QuickSort(int a[], int left, int right) {int center;int i,j;int temp;if(left right){center partion(a,left,right);QuickSort(a,left,center-1);//左半部分QuickSort(a,center1,right);//右半部分} }分割操作双向调整 小白对啊因为你这调整方法可能会出现对同一个元素进行多次交换例如刚才你在演示的那组元素在j向右遍历交换的过程中 第一次8和1交换 第二次8和3交换 第三次8和2交换 8被重复交换了很多次 小白其实我们可以这样来调整元素。我还是用我的第一个元素充当主元吧。哈哈 源数组如下 然后用令变量i left 1j right。然后让 i 和 j 从数组的两边向中间扫描。 i 向右遍历的过程中如果遇到大于或等于主元的元素时则停止移动j向左遍历的过程中如果遇到小于或等于主元的元素则停止移动。 当i和j都停止移动时如果这时i j则交换 i, j 所指向的元素。此时 i j交换8和3 然后继续向中间遍历直到i j。 此时i j分割结束。 最后在把主元与 j 指向的元素交换(当然与i指向的交换也行)。 这个时候j 左边的元素一定小于或等于主元而右边则大于或等于主元。 到此分割调整完毕 代码如下 方法二双向扫描 int partition2( int[] arr, int left, int right) {int pivot arr[left];int i left 1;int j right;while(true){ //向右遍历扫描while(i j arr[i] pivot) i;//向左遍历扫描while(i j arr[j] pivot) j–;if(i j)break;//交换int temp arr[i];arr[i] arr[j];arr[j] temp;}//把arr[j]和主元交换arr[left] arr[j];arr[j] povit;return j; }时间复杂度 小白因为快速排序的最坏时间复杂度是O(n2)。 例如有可能会出现一种极端的情况每次分割的时候主元左边的元素个数都为0而右边都为n-1个。这个时候就需要分割n次了。而每次分割整理的时间复杂度为O(n)所以最坏的时间复杂度为O(n2)。 而最好的情况就是每次分割都能够从数组的中间分割了这样分割logn次就行了此时的时间复杂度为O(nlogn)。 而平均时间复杂度则是假设每次主元等概率着落在数组的任意位置最后算出来的时间复杂度为O(nlogn)至于具体的计算过程我就不展开了。 不过显然像那种极端的情况是极少发生的。 小白哈哈之所以说它快是因为它不像归并排序那样需要额外的辅助空间而且在分割调整的时候不像归并排序那样元素还要在辅助数组与源数组之间来回复制。 稳定性 一禅不是啊例如在排序的过程中主元在和j交换的时候是有可能破坏稳定性的例如 把主元与j指向的元素进行交换
//随机选取主元 int random_partition(int[] arr, int left, int right) {i random(left, right);//随机选取一个位置//在把这个位置的元素与ar[left]交换swap(arr[i], arr[left]);return partition(arr, left, right); }终于写完这个快排写了挺长时间觉得有收获的话可以转发支持一波哦(´-ω-)。 更多排序算法文章

1. 漫画什么是冒泡排序算法
2. 漫画什么是选择排序算法
3. 漫画什么是插入排序算法
4. 漫画什么是希尔排序算法
5. 漫画什么是归并排序算法
6. 漫画什么是快速排序算法
7. 漫画什么是堆排序算法
8. 漫画什么是基数排序算法
9. 漫画什么是外部排序
10. 什么是计数排序
11. 十大排序算法极简汇总篇 推荐阅读 下载破 2w在校生必看《程序员内功修炼》第二版出炉 从双非到大厂帅地写了一本原创PDF送给大家 一个帮你拿offer的校招网站 算法刷题路线(系统全面) 作者简介我是帅地校招拿到过不少大厂offer毕业去了腾讯研发岗毕业半年整到人生第一个 100 万目前专注于写大学规划 校招求职相关的内容著有个人原创网站 PlayOffer。