南宁网站建设哪家专业,建设工程法律法规,燕郊的大型网站建设,百度引擎有趣的算法#xff08;七#xff09; ——快速排序改进算法
目录
有趣的算法#xff08;七#xff09; ——快速排序改进算法 本文章向大家介绍有趣的算法#xff08;七#xff09; ——快速排序改进算法#xff0c;主要内容包括其使用实例、应用技巧、基本知识点总结…有趣的算法七 ——快速排序改进算法
目录
有趣的算法七 ——快速排序改进算法 本文章向大家介绍有趣的算法七 ——快速排序改进算法主要内容包括其使用实例、应用技巧、基本知识点总结和需要注意事项具有一定的参考价值需要的朋友可以参考一下。 有趣的算法七
——快速排序改进算法
原创内容转载请注明来源谢谢
一、概述
快速排序被认为是最好的排序算法之一。快速排序是20世纪60年代被提出的其基本过程如下
现假设长度为n的数组a[n]需要进行排序。步骤如下
1随机选其中一个元素假设为a[i]将所有值比a[i]小的元素移到a[i]的左边假设为数组b所有比a[i]大的元素移到a[i]的右边假设为数组c。
2将数组b、c分别递归执行步骤1即将数组不断的分割成大的半部分和小的半部分并且得到的结果继续递归执行第1步直到满足第3步的条件。
3当一个数组的元素只有两个的时候则直接比较这两个元素的大小并返回比较结果当数组元素只有一个则直接返回这个数组。
快速排序的速度很快只需要O(nlogn)而且可以不需要额外的空间。
二、问题分析
快速排序在众多排序算法中属于非常优秀的算法不过这几十年来还是有许多人对其进行贡献提供了一些很好的改进。
从上述步骤中分析出快速排序主要存在几个问题
1第一步需要随机选取一个元素作为切分元素。
现有数组[1, 2,3, 5, 8, 2, 6, 10]如果恰好取到第一个元素作为切分元素则比较的结果是所有后面的元素都要进入大的数组而小数组没有内容。这样会导致效率低下。
因此对于切分元素不能选的太随意需要改进。
2快速排序是一个递归的排序算法。
在数组元素很少的时候如果也用快速排序则要不断的递归与函数调用效率较低。而有一些简单的算法对于数组数量较少的时候不需要递归而且方便。
因此对于数组元素较少的情况可以采用其他算法。
3元素值一样的问题。
上述分析都只考虑大于小于而没有考虑等于的情况。则在排序的时候对于等于的元素也会被移动或者递归效率较低。
因此需要考虑多个元素值一致的情况。
三、解决方案
针对上述三个问题分别有解决方案。
1、切分元素选取
首先针对传过来的数组需要打散数组或者随机选取一个元素作为基准切分元素假设为i则值是a[i]假设va[i]。
接着设定左右扫描指针实质是数组下标一个从第一个元素开始假设下标为p一个从最后一个元素开始假设下标为q。 在每次循环的时候p从前往后移动直到找到一个比v小的值的下标q则从后往前取比v大的下标。将这两个下标对应的值互换。
循环结束的条件是pq。结束循环后将a[i]和a[q]进行互换实现将切分元素换到数组的中间位置。
代码如下 /*** 获取快速排序的切分元素并进行部分排序保证切分元素左侧元素都小右侧都大*/private static int partition(Comparable[]a, int low, int high){int i low - 1, j high 1;//左右扫描指针int randomIndex (int)(low Math.random()*(high - low 1));Comparable v a[randomIndex];//切分元素while(true){//左边找到比v大的元素while(less(a[i], v, true)){if(i high) break;}//右边找到比v小的元素while(less(v, a[--j], true)){if(j low) break;}//扫描结束退出条件if(i j) break;//交换左右两边找到的元素保证相对有序exchange(a, i, j);}//将切分元素换到中间exchange(a, randomIndex, j);return j;}
上面代码中less是自定义方法用于比较两个数大小exchange也是自定义方法用于交换数组下标i、j的值。
经过上述方法在获取切分元素的同时实际上已经完成了以切分元素值为中值对数组进行的切分。
如下图所示
2、小数组排序
当数组元素较少不采用快速排序。经过前人研究数组元素少于5~15个的时候用插入排序的效率更高。
因此在递归的返回条件中将highlow改成highlow5即可。整个代码如下 /*** 快速排序*/private static voidstartQuickSort(Comparable[] a, int low, int high){if(a.length 5 || high low 5){insertSort(a);//数组长度5以内采用插入排序return;}int partitionNum partition(a, low,high);startQuickSort(a, low, partitionNum-1);startQuickSort(a, partitionNum1,high);
}/*** 插入排序数组长度5以内采用此方法*/private static void insertSort(Comparable[]a){int n a.length;for(int i1;in;i){for(int ji;j0 less(a[j], a[j-1], false);j--){exchange(a, j, j-1);}}
}
3、同值元素问题
因为当前的快速排序仅考虑大于和小于。对于等于的情况可以在设定一个数组专门存放于切分元素值一样的元素且放于数组的中间位置。
这个解决方案被称为三取样切分。和普通的快速排序区别就在于切分多预留一个区间。
如下图所示
核心代码如下 /*** 三取样切分*/private static voidstart3WayQuickSort(Comparable[] a, int low, int high){if(a.length 5 || high low 5){insertSort(a);//数组长度5以内采用插入排序return;}//equalLeft~equalRight区间是等值的情况,low~equal~equalLeft是小的int equalLeft low, equalRight high,i equalLeft 1;Comparable v a[low];while(i equalRight){int cmp a[i].compareTo(v);if(0 cmp) exchange(a, i,equalRight--);//a[i]v交换i和当前最后一个元素并将最后一个元素-1else if(0 cmp) exchange(a,equalLeft, i);//a[i]v交换i和左边的元素并且指针往后else i;//相同的情况则直接比较下一个元素}start3WayQuickSort(a, low, equalLeft-1);start3WayQuickSort(a, equalRight1,high);
}
四、总结
快速排序采用三采样切分的改进方案后在加上小数组情况下引入插入排序其排序的速度非常快适合大部分的排序场景
