Python中排序算法的重要性,希爾排序 ShellSort,中級python技術

2020-12-22 科技叮鈴噹啷

Python中排序算法的重要性

排序是計算機科學中最深入研究的算法之一。有許多不同的排序實現和應用程式，您可以使用它們來提高代碼的效率。

你可以使用排序來解決各種各樣的問題：

搜索：如果列表是排序的，那麼在列表中搜索條目的速度會快得多。選擇：使用已排序的數據，從列表中根據項與其他項的關係選擇項更容易。例如，當值按升序或降序排列時，查找第k大的或最小的值，或查找列表的中值，要容易得多。重複項：在列表排序時，可以非常快速地查找列表中的重複值。分布：如果列表是排序的，那麼分析列表中項目的頻率分布是非常快的。例如，通過排序列表查找出現頻率最高或最低的元素相對比較簡單。從商業應用程式到學術研究，以及其間的任何地方，都有無數種方法可以使用排序來節省自己的時間和精力。

希爾排序 ShellSort

希爾排序的實質就是分組插入排序，該方法又稱縮小增量排序，因DL．Shell於1959年提出而得名。

該方法的基本思想是：先將整個待排元素序列分割成若干個子序列（由相隔某個「增量」的元素組成的）分別進行直接插入排序，然後依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序。因為直接插入排序在元素基本有序的情況下（接近最好情況），效率是很高的，因此希爾排序在時間效率上比前兩種方法有較大提高。

n=10的一個數組49, 38, 65, 97, 26, 13, 27, 49, 55, 4為例

第一次 gap = 10/2 = 5

49 38 65 97 26 13 27 49 55 4

1A 1B

2A 2B

3A 3B

4A 4B

5A 5B

1A, 1B, 2A, 2B等為分組標記，數字相同的表示在同一組，大寫字母表示是該組的第幾個元素， 每次對同一組的數據進行直接插入排序。即分成了五組(49, 13) (38, 27) (65, 49) (97, 55) (26, 4)這樣每組排序後就變成了(13, 49) (27, 38) (49, 65) (55, 97) (4, 26)，下同。

第二次 gap = 5 / 2 = 2

排序後

13 27 49 55 4 49 38 65 97 26

1A 1B 1C 1D 1E

2A 2B 2C 2D 2E

第三次 gap = 2 / 2 = 1

4 26 13 27 38 49 49 55 97 65

1A 1B 1C 1D 1E 1F 1G 1H 1I 1J

第四次 gap = 1 / 2 = 0 排序完成得到數組：

4 13 26 27 38 49 49 55 65 97

下面給出嚴格按照定義來寫的希爾排序

關於排序算法，我總結了幾篇，大家有興趣可以去瀏覽下：

Python中的Timsort算法，Timsort算法的優缺點，中級python技術點

Python中的快速排序算法，快速排序的優缺點，中級python技術點

Python中的合併排序算法，合併排序的優缺點，中級python技術點

Python中的插入排序算法，插入排序的優缺點，中級python技術點

Python中的冒泡排序算法，冒泡排序的優缺點，中級python技術點

相關焦點

  • 快速掌握Java的希爾排序與快速排序算法
    排序算法，是作為程式設計師的基礎算法，也是一定要具備的，如剛從學校出來或者剛轉行過來的夥伴，筆者的建議是要掌握這些基礎的算法，這一篇講解的是希爾排序和快速排序，後續講解哈希表。從此，希爾排序誕生，它就是解決插入排序的更加高效。希爾排序希爾排序在1959年提出而得名，英文Shell’s Sort，它是一種插入排序，又稱「縮小增量排序」。這種插入排序算法比傳統的插入排序算法更加高效。這種算法是非常的穩定。
  • 排序算法:歸併排序
    在日常開發中經常會遇到一類問題，就是對一個集合的數據進行排序掌握一些排序算法，對於日常開發是非常有幫助今天介紹一下歸併排序法01算法邏輯02時間複雜度由上圖邏輯可以得出，歸併排序的循環次數為由算法導論的主定理可以推導出，可見之前的文章（文末有連結）歸併排序的時間複雜度為03空間複雜度由上圖邏輯可以得出，歸併排序每次分解都是要復一份新的數據片段
  • 力扣(LeetCode)- 常見的排序算法總結
    如何分析一個排序算法好壞時間複雜度、比較和交換次數、原地排序（空間複雜度為(1)）、排序穩定性（相等元素之間的位置先後順序不變）。有序度：是數組中具有有序關係的元素對的個數逆序度：和有序度相反。選擇排序是不穩定排序，所以應用最少。
  • Pandas進階Excel【六】——排序
    用excel實現較為簡單，下面介紹在python中如何實現。。。import pandas as pddf = pd.read_excel(r"C:\Users\Administrator\Desktop\火影忍者\pandas庫\火影忍者.xlsx",sheet_name = 1)df2 = df.sort_values(by = ["體術"],ascending = True)print
  • 《python 入陣曲:初級》開題報告
    本課程以培養編程思維和編程能力為核心，雖然沒有將python語言的細節面面俱到，但把編者日常使用、覺得好用的內容傾囊相授，並非要以嚴謹的知識體系介紹python這門語言（而這顯然是筆者力所不能及的）。 基本流程        舉例：寫作、解謎遊戲###    3、輸入與輸出        算法：輸入、處理、輸出 基本流程        泛談：輸入途徑、輸出途徑        分析常見場景中的輸入輸出模式        優秀設計模式：輸入、處理、輸出分離        舉例：遊戲輸入輸出方式的進化
  • 手敲一遍數據結構和排序算法
    排序算法 性質記憶 冒泡排序 選擇排序 插入排序 快速排序 歸併排序 希爾排序 堆排序數據結構 數組 堆 棧 隊列 鍊表 二叉樹 二叉搜索樹 圖 哈希表搜索 廣度優先搜索 深度優先搜索附件 排序算法代碼點擊
  • Python數據類型之列表list
    # 列表是python中最基本的數據結構，它是一個有序序列，序列中的每個元素都分配一個數字（位置，索引）# 1、我們可以使用 方括號，中括號[]來創建列表# 2、我們可以直接將序列放在list（seq）
  • mysql 002|order by的排序算法竟然是這樣的!
    拋出本文問題order by 的排序流程是什麼？order by 的排序算法是什麼？order by 的優化點在於什麼？解答疑問排序流程關於排序過程，MySQL 會通過判斷 sort_buffer_size來執行不同的排序流程。
  • 3種方法學會python模塊使用,3分鐘直接上手一個python繪圖程序
    013種方式查看python模塊使用，使用turtle模塊完成第一個繪畫程序程式語言是一種工具，工具就是為了解決問題，我們的學習模式三種查看模塊下具有哪些函數的方法：1、在python代碼編輯器中，使用模塊加"."
  • python高階函數:map、filter、reduce的替代品
    map函數在小編以前的文章中做過相應的知識分享。sorted函數是python的內置函數，它的可選參數key用於提供一個函數，它可以將函數應用到各個元素上進行排序。根據單詞長度，使用sorted函數對一個列表進行排序。
  • 2019 必知的 10 大頂級 python 庫
    在本文中，我們將討論一些 python 中的頂級庫，開發人員可以使用這些庫在現有的應用程式中應用、清洗和表示數據，並進行機器學習研究。它是一個與 NumPy 和 SciPy 相關聯的 python 庫。它被認為是處理複雜數據的最佳庫之一。在這個庫中進行了許多修改。其中一個修改是交叉驗證特性，它提供了使用多個度量的能力。許多訓練方法，如物流回歸和最鄰近算法，都沒有得到什麼改善。
  • Python2 已終結,入手Python 3,你需要這30個技巧
    檢查所需的最低 Python 版本你可以在代碼中先檢查一下你的 Python 版本，以免當前用戶的 Python 版本與你的腳本不適配。實現的代碼很簡單：3. 使用 IPythonIPython 其實就是升級版的 shell，單單是自帶的自動補全功能就值得你使用它了。
  • Python入門很簡單,只要掌握3456點
    也希望大家對學python能夠持之以恆 python愛好群， 要快速學會Python，謹記3456這四個數字就可以了。 Python基礎培訓要點 下面我來描述這四個數字的含義！
  • 快速介紹Python數據分析庫pandas的基礎知識和代碼示例
    在本例中，將新行初始化為python字典，並使用append()方法將該行追加到DataFrame。在向append()添加python字典類型時，請確保傳遞ignore_index=True，以便索引值不會被使用。生成的軸將被標記為編號series0,1，…， n-1，當連接的數據使用自動索引信息時，這很有用。
  • 【算法知識】詳解直接插入排序算法
    】詳解選擇冒泡算法【算法知識】詳解選擇排序算法在玩撲克牌的時候，我們抽到一張牌的時候，都是將它插入到當前手中牌的合適位置的。如下圖：（上圖來自算法導論）直接插入排序也是這樣的思想。基本思想 插入排序的思想是：將待排序序列分成兩個序列，前面的序列保持有序，依次選取後面的序列的元素，在前面的序列中進行插入。初始時，有序序列的長度為1。
  • Python和人工智慧有什麼關係?Python 和人工智慧的區別是什麼?
    人工智慧人工智慧是一個大的概念，在人工智慧下有計算機視覺，語音識別，自然語言處理等不同的技術領域，這些技術領域中在Github上又有許多開源的代碼可以直接用來開發，而這些代碼往往需要或者只支持人工智慧是一個大的範疇，包括很多方面的應用，比如機器學習，在機器學習中的回歸算法，它們是通過統計分析所有數據來建立多因式，然後求解式子，而在這個過程中程式語言起到的作用是清洗數據、處理數據、建立關係求解結果的作用，python適用於數據清洗且學習成本低，所以在一定程度上，好一部分人傾向於將python應用於人工智慧應用領域。
  • heapq堆排序
    j] i = j # 往下看一層 j = i * 2 + 1 else: # tmp的數值更大，把tmp放到i的位置上 li[i] = tmp # 把tmp放到某一級領導位置上 break else:        li[i] = tmp  # 把tmp放到葉子節點上def heap_sort
  • Python基礎教程之小白入門篇
    下面總結了python語言的三大閃光點：數據科學領域的主流語言隨著大數據時代的來臨，人們越來越意識到數據的重要性，數據分析師被稱為二十一世紀最性感的職業。python緊挨著R語言，以短短幾年時間迅速成為數據科學領域中程式語言的後起之秀，為該領域提供了大量功能強大的模塊。
  • 基於JAVA實現的史上最好的排序和數據結構入門教程
    經歷過校招的人都知道，算法和數據結構都是不可避免的。在筆試的時候，最主要的就是靠算法題。像拼多多、頭條這種大公司，上來就來幾道算法題，如果你沒AC出來，面試機會都沒有。在面試（現場面或者視頻面）的時候也會問算法題，難度肯定是沒有筆試的時候那麼難的。
  • 12步輕鬆搞定Python裝飾器
    作為一名教python的老師，我發現學生們基本上一開始很難搞定python的裝飾器，也許因為裝飾器確實很難懂。搞定裝飾器需要你了解一些函數式編程的概念，當然還有理解在python中定義和調用函數相關語法的一些特點。我沒法讓裝飾器變得簡單，但是通過一步步的剖析，我也許能夠讓你在理解裝飾器的時候更自信一點。