n个元素快速排序最坏要多少轮 什么是快速排序？
什么是快速排序？
1. 如何理解快速排序
快速排序是对冒泡排序的一种改进， 它是不稳定的。由C. A. R. Hoare在1962年提出的一种划分交换排序，采用的是分治策略（一般与递归结合使用），以减少排序过程中的比较次数，它的最好情况O(nlogn)，最坏情况O(n^2)，平均时间复杂度为O(nlogn)。分而治之不是一种解决问题的算法，而是一种希望问题分解，将复杂的问题划分为多个简单问题来解决的思想。
?
快速排序的基本思想：
?
选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小。然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以达到全部数据变成有序。
?
快速排序的步骤：
?
(1) 从数列中挑出一个
如何通过JS对ipv6进行排序？
不知道你所指的排序是哪种规则排序。排序算法分类 比较排序，时间复杂度为O(nlogn) ~ O(n^2)，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等 非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等。
选择排序每次比较的是数组定索引的值与全数组中每个值的大小比较，每次都选出一个最小(最大)值，如果当前索引的值大于之后索引的值，则两者进行交换。
冒泡排序每次从数组的最开始索引处与后一个值进行比较，如果当前值比较大，则交换位置。这样一次循环下来，最大的值就会排入到最后的位置。
插入排序类似于扑克牌的插入方法，选取待排列数组中的任意一个数字作为已排序的基准，再依次从待排序数组中取出数字，根据依次比较，将这个数字插入到已排序的数组中。
二分插入排序是直接插入排序的一个变种，利用二分查找法找出下一个插入数字对应的索引，然后进行插入。当n较大时，二分插入排序的比较次数比直接插入排序的最差情况好得多，但比直接插入排序的最好情况要差，所当以元素初始序列已经接近升序时，直接插入排序比二分插入排序比较次数少。二分插入排序元素移动次数与直接插入排序相同，依赖于元素初始序列。
希尔排序是一种更高效的插入排序，通过设计步长(gap)将数组分组，然后每组中单独采用排序算法将每组排序，然后在缩小步长，进行重复的分组排序工作，直到gap变为1的时候，整个数组分为一组，算法结束。
例如：数组 [1, 4, 5, 2, 3, 9, 0, 7, 6]，如果每次以数组长度的一半来作为步长，可以分解为以下步骤
1. gap: Math.floor(9 / 2) 4
分为四组，分组为： { 1, 3 }, { 4, 9 }, { 5, 0 }, { 2, 7 }
最后一个数字 6 需要等到第5个数字排序完成，也就是3，可以得出3依旧还处在第4索引的位置，因此最后一个分组为 { 3, 6 }
完成一轮分组以及排序后的数组为：[ 1, 4, 0, 2, 3, 9, 5, 7, 6 ]
2. gap: Math.floor(4 / 2) 2
分为两组，分组为：{ 1, 0, 3, 5, 6 }, { 4, 2, 9, 7 }
完成第二轮分组以及排序后的数组为：[ 0, 2, 1, 4, 3, 7, 5, 9, 6 ]
3. gap: Math.floor(2 / 2) 1
分为一组，即为：{ 0, 2, 1, 4, 3, 7, 5, 9, 6 }
完成第三轮分组以及排序后的数组为：[ 0, 1, 2, 3, 4, 5, 6, 7, 9 ]// 分类 -------------- 内部比较排序// 数据结构 ---------- 数组// 最差时间复杂度 ---- 根据步长序列的不同而不同。已知最好的为O(n(logn)^2)// 最优时间复杂度 ---- O(n)// 平均时间复杂度 ---- 根据步长序列的不同而不同。// 所需辅助空间 ------ O(1)// 稳定性 ------------ 不稳定
var arr [1, 4, 5, 2, 3, 9, 0, 7, 6]var gap Math.floor(arr.length / 2)
function swap(arr, i, j) { var t t arr[j] arr[j] arr[i] arr[i] t}
for ( gap gt 0 gap Math.floor(gap / 2)) { //从第gap个元素，逐个对其所在组进行直接插入排序操作 for(var i gap i lt arr.length i ) { var j i // 这里采用的其实是冒泡排序 while(j - gap gt 0 ampamp arr[j] lt arr[j-gap]) { //插入排序采用交换法 swap(arr, j, j-gap) j - gap } // 或者插入排序 var temp arr[j] if (arr[j] lt arr[j-gap]) { while (j-gap gt 0 ampamp temp lt arr[j-gap]) { arr[j] arr[j-gap] j - gap } arr[j] temp } }}
console.log(arr)
版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。
