web開發(fā)中如何實現(xiàn)希爾排序

小編給大家分享一下web開發(fā)中如何實現(xiàn)希爾排序，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

希爾排序

希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。但希爾排序是非穩(wěn)定排序算法。

希爾排序是基于插入排序的以下兩點性質(zhì)而提出改進方法的：

• 插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時，效率高，即可以達到線性排序的效率；

• 但插入排序一般來說是低效的，因為插入排序每次只能將數(shù)據(jù)移動一位；

希爾排序的基本思想是：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。

算法步驟

1. 選擇一個增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

2. 按增量序列個數(shù) k，對序列進行 k 趟排序；

3. 每趟排序，根據(jù)對應(yīng)的增量 ti，將待排序列分割成若干長度為 m 的子序列，分別對各子表進行直接插入排序。僅增量因子為 1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

來源：https://github.com/hustcc/JS-Sorting-Algorithm

算法演示

排序動畫過程解釋

1. 首先，選擇增量 gap = 10/2 ，縮小增量繼續(xù)以 gap = gap/2 的方式

2. 初始增量為 gap = 10/2 = 5，整個數(shù)組分成了 5 組

3. 按顏色劃分為【 8 , 3 】，【 9 , 5 】，【 1 , 4 】，【 7 , 6 】，【 2 , 0 】

4. 對這分開的 5 組分別使用上節(jié)所講的插入排序

5. 結(jié)果可以發(fā)現(xiàn)，這五組中的相對小元素都被調(diào)到前面了

6. 縮小增量 gap = 5/2 = 2，整個數(shù)組分成了 2 組

7. 【 3 , 1 , 0 , 9 , 7  】，【 5 , 6 , 8 , 4 , 2  】

8. 對這分開的 2 組分別使用上節(jié)所講的插入排序

9. 此時整個數(shù)組的有序性是很明顯的

10. 再縮小增量 gap = 2/2 = 1，整個數(shù)組分成了 1 組

11. 【 0, 2 , 1 , 4 , 3 , 5 , 7 , 6 , 9 , 0  】

12. 此時，只需要對以上數(shù)列進行簡單的微調(diào)，不需要大量的移動操作即可完成整個數(shù)組的排序

代碼實現(xiàn)

為了更好的讓讀者用自己熟悉的編程語言來理解動畫，筆者將貼出多種編程語言的參考代碼，代碼全部來源于網(wǎng)上。

C++代碼實現(xiàn)

Java代碼實現(xiàn)

Python代碼實現(xiàn)

JavaScript代碼實現(xiàn)

以上是“web開發(fā)中如何實現(xiàn)希爾排序”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學(xué)習(xí)更多知識，歡迎關(guān)注億速云行業(yè)資訊頻道！