什么是快速排序？1. 如何理解快速排序快速排序是對(duì)冒泡排序的一種改進(jìn)， 它是不穩(wěn)定的。由C. A. R. Hoare在1962年提出的一種劃分交換排序，采用的是分治策略（一般與遞歸結(jié)合使用），以減少排

什么是快速排序？

1. 如何理解快速排序

快速排序是對(duì)冒泡排序的一種改進(jìn)， 它是不穩(wěn)定的。由C. A. R. Hoare在1962年提出的一種劃分交換排序，采用的是分治策略（一般與遞歸結(jié)合使用），以減少排序過程中的比較次數(shù)，它的最好情況O(nlogn)，最壞情況O(n^2)，平均時(shí)間復(fù)雜度為O(nlogn)。分而治之不是一種解決問題的算法，而是一種希望問題分解，將復(fù)雜的問題劃分為多個(gè)簡(jiǎn)單問題來解決的思想。

?

快速排序的基本思想：

?

選擇一個(gè)基準(zhǔn)數(shù)，通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小。然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以達(dá)到全部數(shù)據(jù)變成有序。

?

快速排序的步驟：

?

(1) 從數(shù)列中挑出一個(gè)

如何通過JS對(duì)ipv6進(jìn)行排序？

不知道你所指的排序是哪種規(guī)則排序。排序算法分類 比較排序，時(shí)間復(fù)雜度為O(nlogn) ~ O(n^2)，主要有：冒泡排序，選擇排序，插入排序，歸并排序，堆排序，快速排序等 非比較排序，時(shí)間復(fù)雜度可以達(dá)到O(n)，主要有：計(jì)數(shù)排序，基數(shù)排序，桶排序等。

選擇排序每次比較的是數(shù)組定索引的值與全數(shù)組中每個(gè)值的大小比較，每次都選出一個(gè)最小(最大)值，如果當(dāng)前索引的值大于之后索引的值，則兩者進(jìn)行交換。

冒泡排序每次從數(shù)組的最開始索引處與后一個(gè)值進(jìn)行比較，如果當(dāng)前值比較大，則交換位置。這樣一次循環(huán)下來，最大的值就會(huì)排入到最后的位置。

插入排序類似于撲克牌的插入方法，選取待排列數(shù)組中的任意一個(gè)數(shù)字作為已排序的基準(zhǔn)，再依次從待排序數(shù)組中取出數(shù)字，根據(jù)依次比較，將這個(gè)數(shù)字插入到已排序的數(shù)組中。

二分插入排序是直接插入排序的一個(gè)變種，利用二分查找法找出下一個(gè)插入數(shù)字對(duì)應(yīng)的索引，然后進(jìn)行插入。當(dāng)n較大時(shí)，二分插入排序的比較次數(shù)比直接插入排序的最差情況好得多，但比直接插入排序的最好情況要差，所當(dāng)以元素初始序列已經(jīng)接近升序時(shí)，直接插入排序比二分插入排序比較次數(shù)少。二分插入排序元素移動(dòng)次數(shù)與直接插入排序相同，依賴于元素初始序列。

希爾排序是一種更高效的插入排序，通過設(shè)計(jì)步長(zhǎng)(gap)將數(shù)組分組，然后每組中單獨(dú)采用排序算法將每組排序，然后在縮小步長(zhǎng)，進(jìn)行重復(fù)的分組排序工作，直到gap變?yōu)?的時(shí)候，整個(gè)數(shù)組分為一組，算法結(jié)束。

例如：數(shù)組 [1, 4, 5, 2, 3, 9, 0, 7, 6]，如果每次以數(shù)組長(zhǎng)度的一半來作為步長(zhǎng)，可以分解為以下步驟

1. gap: Math.floor(9 / 2) 4

分為四組，分組為： { 1, 3 }, { 4, 9 }, { 5, 0 }, { 2, 7 }

最后一個(gè)數(shù)字 6 需要等到第5個(gè)數(shù)字排序完成，也就是3，可以得出3依舊還處在第4索引的位置，因此最后一個(gè)分組為 { 3, 6 }

完成一輪分組以及排序后的數(shù)組為：[ 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 }

完成第二輪分組以及排序后的數(shù)組為：[ 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 }

完成第三輪分組以及排序后的數(shù)組為：[ 0, 1, 2, 3, 4, 5, 6, 7, 9 ]// 分類 -------------- 內(nèi)部比較排序// 數(shù)據(jù)結(jié)構(gòu) ---------- 數(shù)組// 最差時(shí)間復(fù)雜度 ---- 根據(jù)步長(zhǎng)序列的不同而不同。已知最好的為O(n(logn)^2)// 最優(yōu)時(shí)間復(fù)雜度 ---- O(n)// 平均時(shí)間復(fù)雜度 ---- 根據(jù)步長(zhǎng)序列的不同而不同。// 所需輔助空間 ------ O(1)// 穩(wěn)定性 ------------ 不穩(wěn)定

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個(gè)元素，逐個(gè)對(duì)其所在組進(jìn)行直接插入排序操作 for(var i gap i lt arr.length i ) { var j i // 這里采用的其實(shí)是冒泡排序 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)