排序演化(一):希爾

NO IMAGE

人腦排序

給一個數組排序

全文默認是升序

[11,2,33,4]

排序演化(一):希爾

按照人的正常思維,我們會看一遍,選擇最大的,然後放在最後面,然後在剩餘的數裡面不斷重複。

腦海裡的思考就是,

  1. 33 移到最後
  2. 11 移到 33 前面
  3. 4 移到 11前面
  4. 2 在正確位置了
  5. 好了

當然,你思考的可能是

  1. 2 移到最前
  2. 4 移到 2後面
  3. 11 移到 4後面
  4. 33 在正確位置了
  5. 好了

後面我們都基於上面的 從小到大的移法

如果灰色背景是一個存放藍色長方形的平面,藍色長方形是一個實體,我們沒有空餘的位置直接把 2 移到最前面,那隻能與該位置上的元素進行交換了。

於是就有

swap(2,11)

排序演化(一):希爾

swap(4,11)

排序演化(一):希爾

swap(11,33)

排序演化(一):希爾

在上面的排序過程中,我們似乎只是進行了交換操作。

但實際上,我們的大腦是進行了比較的,只是上面的數字少差異又大,立馬就知道比較後的結果

如果數字很多的話?

排序演化(一):希爾

假設你還按前面所說的思路(從小到大找):

此時,你想著是誰移到第一個位置呢?

這個誰的意思就是全部數中的最小值。

謹慎的你,就會先在紙上寫 21,假設為最小值

然後和後面的數字不斷的比較,來確認21是不是最小的

交換函數

為了使代碼簡潔,這裡使用下面這種方式作為交換函數

let a = '11'
let b = '22'; // 這裡要加分好 不然語法錯誤
[a, b] = [b, a]
console.log(`a=${a}`); // a=22
console.log(`b=${b}`);// b=11

上面的過程我們就可以寫成

注意,此時我們都是用下標來表示一個數

let arr = [21, 22, 30, 25, 28, 26, 29, 25, 26, 24, 22, 21, 21, 29, 25, 26, 24, 22, 21]
// 類似上述中 紙上的的最小值,先假設是數組的第一個為最小值
let minIndex = 0
for (let i = minIndex + 1; i < arr.length; i++) {
// 不斷與後面的數進行比較,如果找到比現在數還小的,就劃掉原來的數,填上找到數
if (arr[i] < arr[minIndex]) minIndex = i
}
// 下面這段代碼其實就是swap()交換函數
// 最小的元素和第一個元素交換
[arr[minIndex], arr[0]] = [arr[0], arr[minIndex]]

通過上面的代碼,我們就能比較找到最小的值,然後和第一個位置的元素進行交換。

當我們完成了第一步時,數組中的第一個數已經就是有序的了

排序演化(一):希爾

此時,我們把除去第一個數的數組作為新的數組的話(即紅框裡的數組),重複以上操作。

+for (let i = 0; i < arr.length; i++) {
- let minIndex = 0
+	let minIndex = i
for (let i = minIndex + 1; i < arr.length; i++) {
if (arr[i] < arr[minIndex]) minIndex = i
}
- [arr[minIndex], arr[0]] = [arr[0], arr[minIndex]]
+	[arr[minIndex], arr[i]] = [arr[i], arr[minIndex]]
+}

i是每次紅框縮減後的第一個值,這樣當紅框縮減為1時,即i此時等於arr.length - 1,回看整個數組,就是有序的了。

選擇排序

上面的代碼寫成函數就有

let arr = [21, 22, 30, 25, 28, 26, 29, 25, 26, 24, 22, 21, 21, 29, 25, 26, 24, 22, 21]
function selectionSort(arr) {
for (let j = 0; j < arr.length; j++) {
let minIndex = j
for (let i = minIndex + 1; i < arr.length; i++) {
if (arr[i] < arr[minIndex]) minIndex = i
}
[arr[minIndex], arr[j]] = [arr[j], arr[minIndex]]
}
return arr
}
console.log(selectionSort(arr));
// [ 21, 21, 21, 21, 22, 22, 22, 24, 24, 25, 25, 25, 26, 26, 26, 28, 29, 29, 30 ]

這種排序,有個專有的名字:選擇排序

效率分析

我們來思考一下效率的問題。

在排序的過程中,我們一般只有兩種操作

  • 比較
  • 交換

比較

排序演化(一):希爾

把全部加起來

排序演化(一):希爾

如果我們只是想看個大概,即看最明顯的,忽略細節,

比如係數排序演化(一):希爾這種常數直接忽略掉,

或者兩著相差過的數,如排序演化(一):希爾排序演化(一):希爾兩者,我們就留最大者

因為當數很大的時候,排序演化(一):希爾對於排序演化(一):希爾來說就可以忽略不計。

我們稱這種表達法為大O表示法,那此時的比較規模就為 排序演化(一):希爾

後面如果沒說真實次數,就默認是大O表示法,比如說約一約

排序演化(一):希爾

總的來說就是

  • 真實比較次數:排序演化(一):希爾
  • 大O表示: 排序演化(一):希爾

交換

交換的次數就比較玄了,如果整個數組是有升序的,整個數字都不用交換,如果是降序的,那就交換排序演化(一):希爾

取平均的話也就排序演化(一):希爾,約一約,就是排序演化(一):希爾

總結

  • 運行時間和輸入無關。不管我們輸入的數組是否有序,比較的次數永遠是排序演化(一):希爾
  • 數據移動是最少的。每次比較過後的移動,即交換,都是精準的,不會有額外的移動。

插入排序

上面的排序,有個特別緻命的缺點,就是如果數組已經是有序的,比較的次數還是那麼多。

我們思考一個情景。

課外活動,看電影,每個同學搬椅子排成一列縱隊,身高由低到高

排序演化(一):希爾

隊伍已經排好了,此時,4號同學遲到了,現在要插入到這個隊伍中

排序演化(一):希爾

這個4號同學會怎麼插入到隊伍中呢?

他會先把椅子放在7號同學後面

排序演化(一):希爾

然後和7號同學說:同學,你比我高,我看不到電影,你往後做一個位置唄,等等我坐那個空位置

排序演化(一):希爾

然後4號同學發現,6號還是比他高呀!絕望!就和6號說,你也往後坐個位置唄,前面空出的位置給我。

還沒坐下,4號發現,5號還是比他高,所以又和5號說,你往後坐一個位置唄。

這個時候,4號對比了下他和3號的身高,發現,嗯終於有人比我矮了,那此時4號就直接坐下來了。

排序演化(一):希爾

在這個過程中,4號同學,並沒有3號前面的同學比較就找到了正確的位置,那是因為原本的隊伍是有序的,當前面的同學比你矮時,那更前面的同學一定更矮,我們就沒必要比較了。很顯而易見呀!

let arr = [1, 2, 3, 5, 6, 7, 4]
// j表示最後一個位置
let j = arr.length - 1
// temp此時指4號同學
let temp = arr[j]
while (temp < arr[j - 1] & j > 0) { // 如果前面沒位置了 就不用比了呀 所以 j一定要大於0
// arr[j - 1] 表示前面的同學
// 下面的操作表示 前面的同學往後做
arr[j] = arr[j - 1]
j--
}
// 最後4號同學在空出來的位置上坐下
arr[j] = temp
console.log(arr);
// [ 1, 2, 3, 4, 5, 6, 7 ]

那我們能不能把這種思想來解決選擇排序裡面比較次數過多的問題呢?

我們遇到的第一個障礙是,上面的操作是把一元素插入到一有序隊列中。

此時我們思考,如果班上只有一個人,不管此人身高如何,他怎麼站,他一定是有序的。

假設我們從零開始整理隊伍。

首先,讓某一同學搬好椅子,在學校規劃區域中的最前面,坐好。

那一個有序隊列就出先了。

後面只要,不斷添加同學,讓他先把椅子放在該隊列的末端,然後比較前面與自己兩者的身高,重複上述4號同學的動作。

記得,不能超過最前面的同學的位置,如果可以隨便坐前面,沒有規矩,那大家直接坐到屏幕前吧。

同理,我們可以把數組中的第一個元素作為有序數組,那我們在後面一次往該數組插入,這樣就能保持前面的數組是有序的。

function insertionSort(arr) {
// 從1開始排,因為0做為有序隊列
for (let i = 1; i < arr.length; i++) {
let j = i
let temp = arr[j]
while (temp < arr[j - 1] && j > 0) {
arr[j] = arr[j - 1]
j--
}
arr[j] = temp
}
return arr
}
console.log(insertionSort([11, 2, 33, 4, 55]));
// [ 2, 4, 11, 33, 55 ]

效率分析

比較

很明顯,比較次數是比選擇排序少的,所以我們按最多的情況來數。

第一次插入時,最多比較1次

第二次插入時,最多比較2次

….

最後一次插入時,最多比較n-1次

總數是n,第一個默認有序,所以不用比較,所以最後一次插入,前面共有n-1個人,比較n-1次

排序演化(一):希爾

這是最壞的情況,而原本的選擇排序是每次都是這種情況。

如果拋卻最壞情況,比如數組中大部分是正確有序的,我們只要比較少部分即可。

所以在針對以下情景時

  • 數組中每個元素距離它的最終位置都不遠
  • 一個有序的大數組接一個小數組
  • 數組中只有幾個元素的位置不正確

插入排序效率會特別高。或者可以說,當倒置的數量很少時,插入排序基本是最快的。

但是奈不住,取平均下來,簡單的除以2,把這個數約一約,會發現最後的效率還是排序演化(一):希爾

交換

更有意思的是,交換次數相對選擇排序,高了很多,但是這麼說也不公平,選擇排序是全部排序共交換次數中最少的,唯一的線性增長的。

插入的交換次數是和上面的比較次數同理,因為每比較一次就交換一下,即

排序演化(一):希爾

約一約就是排序演化(一):希爾

總結

拋卻選擇排序是最少交換次數的排序而言,插入排序把比較次數降低了許多,尤其是在數組大部分有序的情況下,性能特別好。

但是因為存在如果排序的元素開始排序時,距離它正確的位置很遠時,效率極低,比如

在一個1000人的升序隊伍,一個小矮人也要來插入的話,他一個人就要影響這個有序隊伍全部人往後移動。

希爾排序

針對選擇排序固定的比較次數,我們使用了往局部有序數組裡插入數據的插入排序。

但是插入排序在逆序這種極端條件下表現效果特別差,我們思考下能不能優化下?

靈感1

還是拿小矮人的情況舉例。

身高1.1米的小矮人要插入隊伍了

他讓最後一位2.1米同學站起來,兩者比下身高,發現自己矮,要往前

然後再比倒數第2位1.9米高的同學,再問倒數第3位1.88米高的同學

連續問到倒數第五個1.8米高的同學,他實在受不了了

他說:你就不能有點逼數嗎?往前點問,別一個一個問,這一塊(已經指大概五六個人的範圍)的人都比你高,你走遠點再問。

這給了我們一個靈感,我們可以把比較的步伐擴大一點,然後慢慢的把步伐變成最小。當然如果是小矮人這種情況,先過十個問,再過五個問,最後一個一個問,看起來好像挺好的。

但是怎麼判斷步伐的改變,還有涉及錯過的問題?就會讓簡單的排序格外複雜。

那我們要怎麼運用這個增大步伐的靈感呢?

靈感2

我們在思考下我們的快速排序的痛點是什麼?

存在如果排序的元素開始排序時,距離它正確的位置很遠時,效率極低

我們還是舉一個例子:

還是班級按身高排序

在開學的時候,班主任讓班上的人到門口,按身高排序,這個時候大家剛報道都不是很熟,你會很熱情的找到某位同學背對背比身高嗎?當然不會?

那我們是怎麼做的呢?

我們一般是憑感覺和某幾個身高相仿的人在一起,整個隊伍此時雖然不是準確的有序,但是一眼望過去,不會說參差不齊。

此時,老師就會讓第2個同學開始使用插入排序來排身高了。

插入排序就要背對背咯,因為是老師命令的,就不會顯得很突兀啦

大家很快就排好了隊伍,因為原本所在的位置和最終的位置距離很近,還有些可能都不用移動。

靈感1+靈感2

如果使用靈感1增大步伐,如果要實現準確排序的話,我們就會涉及到步伐如果調節和錯過的問題。主要是錯過的問題,讓我們很難辦

通過靈感2,我們發現,如果整個隊伍原本是大致有序的,最後再來插入排序效率會很快。

結合兩者,很容易想到,通過大步伐來讓隊伍大致有序,這樣就可以避免錯過正確位置的問題,因為錯過就錯過了呀,我們只要大致有序。

排序演化(一):希爾

排序演化(一):希爾

let arr = [11, 2, 33, 4, 55, 6, 77, 8, 99, 10, 1, 12]

這裡我們先簡單的使用步伐為3進行插入排序

紅色組:11 --> 4 --> 77 --> 10

藍色組:2 --> 55 --> 8 --> 1

綠色組:33 --> 6 --> 99 --> 12

let arr = [11, 2, 33, 4, 55, 6, 77, 8, 99, 10, 1, 12]
let gap = 3
for (let i = gap; i < arr.length; i++) {
let j = i
let temp = arr[j]
while (temp < arr[j - gap] && j > 0) {
arr[j] = arr[j - gap]
j -= gap
}
arr[j] = temp
}
console.log(arr);
// [ 4, 1, 6, 10, 2, 12, 11, 8, 33, 77, 55, 99 ]
/*
4 -- > 10 -- > 11  -- > 77
1 -- > 2 -- > 8 -- > 55
6 -- > 12 -- > 33 -- > 99
*/

排序演化(一):希爾

如果上面看的懂,就不用看下面的解釋

我們拿個插入排序對比下

+ let gap = 3
function insertionSort(arr) {
+ for (let i = gap; i < arr.length; i++) {
-	for (let i = 1; i < arr.length; i++) {
let j = i
let temp = arr[j]
+   while (temp < arr[j - gap] && j > 0) {
-		while (temp < arr[j - 1] && j > 0) {
+			arr[j] = arr[j - gap]
-			arr[j] = arr[j - 1]
+ 		j -= gap
-			j--
}
arr[j] = temp
}
return arr
}
  1. gap = 3

    多了一個步伐的設置

  2. for (let i = gap; i < arr.length; i++) {

    此時i的初始值,由原來的1變成了gap

    當初設為1時,是表示從arr[1]開始 ,因為前面arr[0]是有序的

    此時我們分為了三組

    4 -- > 10 -- > 11 -- > 77
    1 -- > 2 -- > 8 -- > 55
    6 -- > 12 -- > 33 -- > 99

    那對於每組的第一個,同樣假設為有序,應該從後面的數開始,這裡特指10,2,12

    排序演化(一):希爾

    箭頭所指的數就為要開始插入的數,即i = gap

    但是值得注意的是,這裡的i的增長步伐還是1,仔細想象就覺得理所當然了,因為外循環的作用就是遍歷每個元素,如果不為1,如果遍歷整個數組,而前面i為gap,只是表示從哪開始

    執行的順序是三組輪流執行插入排序,先讓4在紅色組中排在正確的位置,然後是55在藍色組中排在正確的位置,接著才是6在綠色組中排到正確的位置,依次下去。

  3. 從這個while (temp < arr[j - gap] && j > 0) {開始 才是最重要的變化

    很明顯,每次應該是和自己組的比較,即原本數組裡間隔gap的數temp < arr[j - gap]

  4. arr[j] = arr[j - gap]同上

  5. j -= gap同上

排序演化(一):希爾

對比兩張圖,我們就可以看到現在這個隊列是大致有序的了

現在我們再把步伐降低為2

排序演化(一):希爾

4 -- > 6 -- > 2 -- > 11 -- > 33 -- > 55
1 -- > 10 -- > 12 -- > 8 -- > 77 -- > 99
let arr = [4, 1, 6, 10, 2, 12, 11, 8, 33, 77, 55, 99]
let gap = 2
for (let i = gap; i < arr.length; i++) {
let j = i
let temp = arr[j]
while (temp < arr[j - gap] && j > 0) {
arr[j] = arr[j - gap]
j -= gap
}
arr[j] = temp
}
console.log(arr);
// [ 2, 1, 4, 8, 6, 10, 11, 12, 33, 77, 55, 99 ]

我們對這兩組數組排序

2 -- > 4 -- > 6 -- > 11 -- > 33 -- > 55
1 -- > 8 -- > 10 -- > 12 -- > 77 -- > 99

排序演化(一):希爾

我們發現此時此時步伐3到步伐2變化已經不是很明顯了,這說明了兩個問題

  1. 步伐之差儘量大一點
  2. 元素離正確位置已經很近了

此時我們再來補最後一筆,

let arr = [2, 1, 4, 8, 6, 10, 11, 12, 33, 77, 55, 99]
let gap = 1
for (let i = gap; i < arr.length; i++) {
let j = i
let temp = arr[j]
while (temp < arr[j - gap]) {
arr[j] = arr[j - gap]
j -= gap
}
arr[j] = temp
}
console.log(arr);
//[ 1, 2, 4, 6, 8, 10, 11, 12, 33, 55, 77, 99 ]

整個數字就完美有序了。

很明顯的,上面的操作可以合成一個函數

function shellSort(arr) {
let gap = 3
while (gap >= 1) {
for (let i = gap; i < arr.length; i++) {
let j = i
let temp = arr[i]
while (temp < arr[j - gap] && j > 0) {
arr[j] = arr[j - gap]
j -= gap
}
arr[j] = temp
}
gap--
}
return arr
}

我們稱這種排序為希爾排序。

間隔選擇

我們在上面中說過,當間隔從3變為2時,變化已經不是很大了,這暗示我們一個道理,這個間隔的選擇是有門道的。

如果選擇這個間隔就影響到了算法的效率。

但是這個間隔賊難選,太難證明了。

當然,是不會像上面不管這個數組多長都選為3還每次減1,這個間隔一定是視數組長度決定,所以我們可以簡單初始值和遞減程度都這樣

let gap = Math.floor(length / 2)

當然,數學家給了比較好的

function shellSort(arr) {
let gap = 1
while (gap < arr.length / 3) gap = 3 * gap + 1
while (gap >= 1) {
for (let i = gap; i < arr.length; i++) {
let j = i
let temp = arr[i]
while (temp < arr[j - gap] && j > 0) {
arr[j] = arr[j - gap]
j -= gap
}
arr[j] = temp
}
gap = Math.floor(gap / 3)
}
return arr
}
console.log(shellSort([11, 2, 33, 4, 55, 6, 77]));

gap = 3 * gap + 1是一個遞增數列,1,4,13,40,121,364。。。。

還有一個更快的,這裡就不列了,有興趣自己去查,平時用上面這個就夠了。

效率

這個效率問題,就不像前面那麼好證明了,很難。

可以知道的就是,按上面“gap = 3 * gap + 1`這種步伐的希爾排序,在最壞的情況下,比較次數和排序演化(一):希爾成正比。

這裡說的是最話的,但是此時我們已經比原來的排序演化(一):希爾少了很多了。

而且這種排序算法的優勢,體現在數組的長度上,數組越長,優勢越大。

用圖說話

排序演化(一):希爾

總結

我們為了解決插入排序存在如果排序的元素開始排序時,距離它正確的位置很遠時,效率極低的痛點,通過增大步伐的靈感來解決,從而寫出來希爾排序。

是不是以後就不用插入排序了呢?

答案是否定的,對於部分有序和小規模的數組我們還是應該使用插入排序的。

相關文章

206反轉鏈表(JS)

Promise.all和Promise.race源碼實現

排序演化(三):快速

排序演化(二):歸併