datatable的數據進行組內排序_排序算法學習分享(四)希爾排序

bd1eeb2e0a30836c92dcbe6b0194a83e.png

排序,也稱為排序算法,可以說是我們學習算法的過程中遇到的第一個門檻,也是實際應用中使用得較為頻繁的算法,我將自己對所學的排序算法進行一個歸納總結與分享,如有錯誤,歡迎指正!

排序算法學習分享(一)選擇排序

排序算法學習分享(二)交換排序---冒泡排序與快速排序

排序算法學習分享(三)插入排序

(一)排序的分類

排序算法主要分為內部排序與外部排序,當數據量大時,數據無法全部加載到內存中,因此需要接抓外部存儲(文件、磁盤等)進行排序。而內部排序則是指將要處理的所有數據加載到內部存儲器中,并在內存中就完成排序。

3dfee53c79897abe9bd9036d535c9dc5.png

本文針對的為內部排序。

(二)內部排序

4 希爾排序

前文我介紹了插入排序,但是插入排序會出現一個問題。如果我們拿到的是一個較小的數進行插入排序,那么元素后移的次數會明顯增加,那么就會嚴重影響整個排序的效率。

接下來介紹的希爾排序就是經典的對插入排序的一種優化。

希爾排序,也稱遞減增量排序,是插入排序的一種更高效的改進版本。我們都知道,插入排序對已經有序的或者是有序程度高的序列排序是非常快的,但一般情況下,由于插入排序每插入一個元素都只能一個一個元素地進行移動,因此它的效率是十分低下的。

顯然要優化插入排序的移動是很困難的,而希爾排序取巧地不去優化它的移動,希爾排序的思想我用一句話去概括:盡可能的在數組進行下一輪的排序時,提高數組的有序程度。

先記住一點:在序列的排序中,元素越少,需要交換的次數越少,排序越快。

那么怎么去提高一個數組的有序程度呢?用一個很有趣的東西——增量

這類似于分治思想,但它又不是。希爾排序利用增量這一個東西去將序列分割成若干個子序列,再將每個子序列分別排好。 那么究竟什么是增量?又要怎么利用增量?

增量就是一個等差數列的差值,比如1,3,5,7,9。它們的增量是2。一開始盡可能使用一個大的增量,使得每個子序列中的元素少,比如第一輪就盡量使得一個子序列的元素只有兩個。

增量越大,那么分的組就會越多,每個組中的元素數目就會小。每一輪都比上一輪的增量按照一定的規律遞減,那么分的組就會比上一輪的分的組少,而每個組中的元素就要比上一輪的元素要多,當增量一直減到1的時候,我們就會發現只有一個組了,而這個組中的元素就是整個序列的所有元素,這就是遞減增量。

利用增量這樣子分割序列是為了什么呢?是為了使下一輪的有序程度變高。為什么我說希爾排序是一種取巧呢?就是因為它耍賴皮,有序程度低的時候,增量就大,分組就多,組內元素就少,排序就快。當這一輪排序完成的時候,全體序列的有序程度一定是要比上一輪的有序程度要高的(有一些特殊情況,嚴謹地應該說是不低于)。

增量每一次發生遞減,那么序列的有序程度就提高了那么一點,當增量遞減到1的時候,序列的有序程度就已經很高的,這時再進行一輪插入排序,就很快了。

這么將還是有些抽象,我們舉一個實例,上一些圖來說明。

b4cfce7456a03ed1a03a463a0ce61641.png

這是一個原始數組,可以看到它的有序程度并不高。

我們對它進行第一次增量分組,使得每組中的元素盡可能少。最少的話是一個元素一個組,但是如果組中只有一個元素,那么組內的排序根本沒有意義,因此第一次的這個盡可能少,就是兩兩一組。此時的增量為4。

5d7e6f060b125f94c4fbb69428815ac3.png

我們對每個子數組內進行排序。由于每個子數組內的元素很少,因此排序很快,排序完如下:

bd8cb3dfdde6612945a24a47a2f98f2f.png

我們已經可以看到只是經過簡單的幾個交換后數組的有序程度就已經顯著提升了,那么接下來就是進入到下一輪。

遞減增量,直接使增量減半(希爾增量),新的增量為4 / 2 = 2,將2作為新的增量重新進行分組,分組如下。

d358782e8cdf59e6482fa2acadb747e1.png

我們對每個分組內進行排序,因為經過了上一輪的排序,可以看到每個組內的有序程度比上一輪如果也按照這個增量分組的有序程度要高。

這就達到了希爾排序的目的,就是每一輪都要比上一輪的有序程度要高,這很像我們做產品時候的不斷迭代。

排序好后如下:

49a6e0486c5ed98c1f5058da2ee7f25f.png

這一輪結束后增量再遞減就變成1了,最后再進行一輪插入排序即可,此時需要移動的數僅僅就是5和3,8和9。有序程度比原數組高到不知道哪里去了。再來一輪插入排序就完成啦!

96066f4928183cb753344073947a41d2.png

其實遞減增量的規則有很多種,不止折半這一種,有時候根據需求改變遞減增量的方式會取得更優的性能。

下面嘗試用代碼實現希爾排序:

f2531e6d126db780794959dbf89d18d6.png

希爾排序使用的增量是折半的方式遞減的,這種方式的增量叫做希爾增量。希爾排序利用增量分組粗調一般情況下是減少了插入排序的工作量,使得插入排序的時間復雜度低于O(n2)。

但是,在一種極端的情況下,希爾排序所做的粗略調整不但沒有減少插入排序的工作量,反而增大的插入排序的工作量。

舉一個例子:

645966506065f352ec8e2fdb57cad7df.png

我們利用希爾增量來分組,當增量為4時,分組為:(2,7),(1,6),(5,9),(3,8)。我們可以看到它在組內是有序的,再折半減少增量為2,分組為(2,5,7,9),(1,3,6,8),還是有序的,經過兩輪增量排序,它的有序程度并沒有提高,比起直接插入排序反而還增加分組排序的這一個步驟,增加了工作量。

會出現這種情況的原因在于希爾增量,希爾增量之間是等比的,這代表著等比之間是可以出現一定的盲區的,就像上面這個例子,就完美地處在了希爾增量之間的盲區。

那么才能使得增量之間沒有盲區呢?最好的方式就是使得每一輪彼此的增量“互質”。而增量的方式很多,最為典型的就是Hibbard增量和Sedgewick增量。因為本文講的是希爾排序,就不繼續往下介紹了。

希爾排序是一個不穩定的排序算法,是因為在分組的過程中,兩個元素的交換的跨度有時候是會很大的。比如m > i = j > k,而原數組是( i ,j ,k ,m ),那么第一輪希爾排序后,i 就到 j 后面了。

希爾排序的介紹就到這里啦!希爾排序的中心思想就是: 盡可能的在數組進行下一輪的排序前,提高數組的有序程度。即每一輪都比上一輪時候的有序程度要高。

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/537554.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/537554.shtml
英文地址,請注明出處:http://en.pswp.cn/news/537554.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

jupyter notebook 安裝代碼提示功能

效果 安裝成功后,輸入部分代碼,按 tab 鍵,會提示代碼 安裝步驟 1.安裝nbextensions 從國內的pip鏡像下載快 pip install -i http://pypi.douban.com/simple --trusted-host pypi.douban.com jupyter_contrib_nbextensions jupyter contr…

轉:EL表達式的11個內置對象

原文地址&#xff1a;https://blog.csdn.net/qq_17045385/article/details/54799998 EL是JSP內置的表達式語言 JSP2.0開始&#xff0c;不讓再使用Java腳本&#xff0c;而是使用EL表達式和動態標簽來代替Java腳本 ############EL替代的是<%... %>&#xff0c;也就是說EL只…

python需要配置環境變量嗎_python為什么會環境變量設置不成功

學習python編程&#xff0c;首先要配置好環境變量。本文主要講解python的環境變量配置&#xff0c;在不同版本下如何安裝 Windows 打開Python官方下載網站 https://www.python.org/downloads/release/python-370/ x86:表示是32位電腦 x86-64:表示是64位電腦 目前Python版本分為…

一維數組、二維數組、三維數組、四維數組、多維數組的理解

以圖書館來舉例 一維數組是一條線 二維數組是一頁紙 三維數組是一本書 四維數組是書架 五維數組是圖書室2201&#xff08;好幾個書架&#xff09; 六維數組是圖書館某一層&#xff0c;2樓/3樓&#xff0c;好幾個圖書室 七維數組是整個圖書館 第N維數組是宇宙..................…

線性篩

我就是我&#xff0c;一輩子都學不會線性篩的菜雞 一篇非常好的博客轉載于:https://www.cnblogs.com/yzxverygood/p/9907281.html

在資源使用狀況視圖中查看資源的負荷情況

只有工時類資源才會出現過度分配&#xff0c;因為工時類資源通常指組織內部的人力資源或者機械設備等&#xff0c;這些資源通常都有數量上的瓶頸&#xff0c;也只有工時類資源才會在【資源工作表】中設置它的最大單位和資源可用性&#xff0c;這就限制了它在不同時間段內的可用…

python常用單詞自由且開放_python常用英語單詞詞匯 unit7

1. Darcula IntelliJ IDEA自帶的黑色主題名稱&#xff0c;Android Studio是基于IntelliJ IDEA的。 2. Appearance /prns/ n. 外觀&#xff1b; 3. Custom /kstm/ n. 習慣&#xff1b; 4. UI abbr. 用戶界面&#xff08;user interface&#xff09; 5.Terminate /tmnet/ 終止、結…

2018.10.29-2018.11.4

簡述osi七層模型和TCP/IP五層模型應用層OSI 參考模型中最靠近用戶的一層&#xff0c;是為計算用戶提供應用接口&#xff0c;也為用戶直接提供網絡服務。常見的應用層網絡服務協議有&#xff1a;HTTP,HTTPS,FTP,POP3,SMTP等表示層表示提供各種用于應用層數據編碼和轉換功能&…

CSV文件轉Excel后數字自動轉換成科學計數法的解決方法

CSV文件用Excel打開后&#xff0c;長度超過11位的數字自動轉換成科學計數法顯示&#xff0c;末尾數字變成“0000”&#xff0c;如何解決這一問題&#xff1f; 以“老勞模系統數據.CSV”為例&#xff0c;身份證碼是科學計數法了 第一步&#xff1a;新建excel&#xff0c;用 off…

python 小說 云_python小說網站

廣告關閉 騰訊云11.11云上盛惠 &#xff0c;精選熱門產品助力上云&#xff0c;云服務器首年88元起&#xff0c;買的越多返的越多&#xff0c;最高返5000元&#xff01; python爬蟲之小說網站--下載小說(正則表達式)思路:1. 找到要下載的小說首頁,打開網頁源代碼進行分析(例:htt…

數據庫導出到excel解決科學計數法問題

用Navicat等工具導出數據到excel的時候&#xff0c;身份證等超過11位的數字會自動轉換成科學計數法&#xff0c;末尾數字變成“0000”。如何解決&#xff1f; 解決方式&#xff1a;給超過11位的數字末尾添加 \t 查詢的時候&#xff0c;給相關字段添加 \t SELECT name,CONCAT…

6.6(java學習筆記)文件分割(IO綜合例子)

基本思路&#xff1a; 文件分割&#xff1a;將一個文件分割成若干個獨立的文件。 設置分割后小文件文件的字節數&#xff0c;然后讀取被分割文件&#xff0c; 將對應的字節數寫入分割后的小文件中。 使用seek定位下一次讀取位置。 文件合并&#xff1a;將分割后的若干的文件合并…

小米MIUI關閉內容中心通知

被MIUI的內容中心打擾了許久&#xff0c;終于找到徹底關閉它的方式。 這個內容中心&#xff0c;在應用列表里找不到卸載&#xff0c;在通知管理里也找不到&#xff0c;小米把它藏得深。 關閉內容中心通知 第一步&#xff0c;先進入內容中心&#xff0c;然后切換到后臺&#…

python編碼器_自編碼器和分類器python

展開全部 你好&#xff0c;下面是一個keras的softmax分類器自編碼器的python代碼。你需要安裝e5a48de588b662616964757a686964616f31333431343665最新的theano1.0.4才可以跑。import os; os.environ[KERAS_BACKEND] theano import keras from keras.datasets import mnist fro…

Java虛擬機-第二篇-GC算法與內存分配策略

2019獨角獸企業重金招聘Python工程師標準>>> GC引入 在Java的運行時數據區中&#xff0c;程序計數器、虛擬機棧、本地方法棧三個區域都是線程私有的&#xff0c;隨線程而生&#xff0c;隨線程而滅&#xff0c;在方法結束或線程結束時&#xff0c;內存自然就跟著回收…

python在函數內部有沒有辦法定義全局變量_主函數內部的全局變量python

你想要什么是不可能的*。你可以在全局命名空間中創建一個變量&#xff1a; myglobal "UGHWTF" def main(): global myglobal # prevents creation of a local variable called myglobal myglobal "yu0 fail it" anotherfunc() def anotherfunc(): print…

軟件項目經理應該具備的心態

我們&#xff08;項目經理&#xff09;必須認識到有些現實是無法改變的&#xff1a; 1.市場前期都會過度承諾 2.公司是要賺錢的&#xff0c;僅僅有虛名但不賺錢的事情公司是不會真正持久的 3.任何公司都是資源不足的 4.任何公司都有或多或少的管理問題&#xff0c;沒有問題…

Caffe學習記錄(十一) ICNet分割網絡學習

ICNet 是一個既考慮性能&#xff0c;又考慮準確率的分割網絡&#xff0c;包含了語義分割和邊緣精確分割&#xff0c;因為偶然看到就簡單的了解一下&#xff0c;記錄下來 論文是: ICNet for Real_time Semantic Segmentation on High Resolution Images&#xff0c;整篇文章都在…

如何利用python自動化辦公項目_python辦公自動化:自動進行word文檔處理和排版

上節python辦公自動化:自動打開word文檔我們一起學會了在python里打開并保存一個word文檔。這節我們將會學會如何利用python進行文本處理和將其在word里進行排版等技巧。python進行文本處理和將其在word里進行排版等技巧 使用文本 要有效地處理文本&#xff0c;首先要了解一些塊…

不同項目組織結構間的區別

項目組織結構分 職能型 項目型 矩陣型 弱矩陣型 平衡矩陣 強矩陣 職能型 場景舉例&#xff1a; 去飯店吃飯。 飯店A&#xff0c;門口宣傳接待一組人&#xff0c;進店了&#xff0c;換另一組人安排就坐點餐&#xff0c;過一會兒&#xff0c;有專人上菜...... 這是職能型&#x…