排序算法彙總總結_Java實作

一、插入排序

直接插入排序（Insertion Sort）的算法描述是一種簡單直覺的排序算法。它的工作原理是通過建構有序序列，對于未排序資料，在已排序序列中從後向前掃描，找到相應位置并插入。插入排序在實作上，通常采用in-place排序（即隻需用到O(1)的額外空間的排序），因而在從後向前掃描過程中，需要反複把已排序元素逐漸向後挪位，為最新元素提供插入空間。

代碼實作：

<code>public</code> <code>class</code> <code>Inseretion_Sort {</code>

<code> </code><code>public</code> <code>static</code> <code>void</code> <code>main(String[] args) {</code>

<code> </code><code>//要排序的原始數組</code>

<code> </code><code>int</code> <code>score[]={</code><code>900</code><code>,</code><code>878</code><code>,</code><code>891</code><code>,</code><code>904</code><code>,</code><code>865</code><code>,</code><code>912</code><code>,</code><code>868</code><code>,</code><code>870</code><code>,</code><code>898</code><code>,</code><code>903</code><code>};</code>

<code> </code><code>//列印數組元素</code>

<code> </code><code>System.out.print(</code><code>"未排序數組："</code><code>);</code>

<code> </code><code>System.out.print(score[i]+</code><code>" "</code><code>);</code>

<code> </code><code>System.out.println();</code>

<code> </code><code>if</code> <code>(score[k]>score[k-</code><code>1</code><code>]){</code>

<code> </code><code>int</code> <code>temp=score[k];</code>

<code> </code><code>score[k]=score[k-</code><code>1</code><code>];</code>

<code> </code><code>score[k-</code><code>1</code><code>]=temp;</code>

<code> </code><code>//每周遊一次數組的結果</code>

<code> </code><code>System.out.print(</code><code>"第"</code><code>+i+</code><code>"次插入："</code><code>);</code>

<code> </code><code>System.out.print(score[j]+</code><code>" "</code><code>);</code>

<code> </code><code>System.out.println();</code>

<code> </code><code>//最終排序結果</code>

<code> </code><code>System.out.print(</code><code>"最終排序結果："</code><code>);</code>

<code> </code><code>System.out.print(score[j]+</code><code>" "</code><code>);</code>

希爾排序，也稱遞減增量排序算法，是插入排序的一種高速而穩定的改進版本。它的基本思想是先取一個小于n的整數d1作為第一個增量，把檔案的全部記錄分成d1個組。所有距離為dl的倍數的記錄放在同一個組中。先在各組内進行直接插人排序；然後，取第二個增量d2<d1重複上述的分組和排序，直至所取的增量dt=1(dt<dt-l<…<d2< d1)，即所有記錄放在同一組中進行直接插入排序為止。該方法實質上是一種分組插入方法。

<code>public</code> <code>class</code> <code>Shell_Sort {</code>

<code> </code><code>for</code> <code>(</code><code>int</code> <code>incre=score.length/</code><code>2</code><code>;incre></code><code>0</code> <code>;incre=incre/</code><code>2</code> <code>)</code>

<code> </code><code>for</code> <code>(</code><code>int</code> <code>i=incre;i<score.length;i++ )</code>

<code> </code><code>int</code> <code>temp=score[i];</code>

<code> </code><code>for</code> <code>(k=i;k>=incre ;k=k-incre )</code>

<code> </code><code>if</code> <code>(temp>score[k-incre])</code>

<code> </code><code>score[k]=score[k-incre];</code>

<code> </code><code>break</code><code>;</code>

<code> </code><code>score[k]=temp;</code>

二、交換排序

冒泡排序（Bubble Sort）是一種簡單的排序算法。它重複地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。代碼實作：

<code>public</code> <code>class</code> <code>Bubble_Sort {</code>

<code> </code><code>if</code> <code>(score[k]<score[k+</code><code>1</code><code>]){</code>

<code> </code><code>score[k]=score[k+</code><code>1</code><code>];</code>

<code> </code><code>score[k+</code><code>1</code><code>]=temp;</code>

<code> </code><code>System.out.print(</code><code>"第"</code><code>+(i+</code><code>1</code><code>)+</code><code>"次冒泡："</code><code>);</code>

<code> </code><code>System.out.print(score[j]+</code><code>" "</code><code>);</code>

快速排序是由東尼·霍爾所發展的一種排序算法基本思想是：通過一趟排序将要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然後再按此方法對這兩部分資料分别進行快速排序，整個排序過程可以遞歸進行，以此達到整個資料變成有序序列。

<code> </code><code>package</code> <code>com.mzsx.binarySearch;</code>

<code>import</code> <code>com.google.gson.Gson;</code>

<code>public</code> <code>class</code> <code>Quick_Sort {</code>

<code> </code><code>public</code> <code>static</code> <code>void</code> <code>main(String[] args) {</code>

<code> </code><code>int</code> <code>array[] = { </code><code>2</code><code>, </code><code>44</code><code>, </code><code>23</code><code>, </code><code>5</code><code>, </code><code>34</code><code>, </code><code>13</code><code>, </code><code>29</code><code>, </code><code>6</code><code>, </code><code>24</code><code>, </code><code>26</code><code>, </code><code>18</code><code>, </code><code>10</code><code>, </code><code>25</code><code>, </code><code>12</code><code>, </code><code>17</code> <code>};</code>

<code> </code><code>array = quickSort(array, </code><code>0</code><code>, array.length-</code><code>1</code><code>);</code>

<code> </code><code>System.out.print(array[i] + </code><code>" "</code><code>);</code>

<code> </code><code>System.out.println();</code>

<code> </code><code>// 快速排序算法</code>

<code> </code><code>public</code> <code>static</code> <code>int</code><code>[] quickSort(</code><code>int</code><code>[] arr, </code><code>int</code> <code>lowIndex, </code><code>int</code> <code>highIndex) {</code>

<code> </code><code>if</code> <code>(lowIndex < highIndex) {</code>

<code> </code><code>int</code> <code>start = arr[lowIndex]; </code><code>// 起始數</code>

<code> </code><code>int</code> <code>low = lowIndex;</code>

<code> </code><code>int</code> <code>high = highIndex+</code><code>1</code><code>;</code>

<code> </code><code>while</code> <code>(</code><code>true</code><code>) {</code>

<code> </code><code>//向右尋找大于s的數組元素的索引</code>

<code> </code><code>while</code> <code>(low + </code><code>1</code> <code>< arr.length && arr[++low] < start);</code>

<code> </code><code>//向左尋找小于s的數組元素的索引</code>

<code> </code><code>while</code> <code>(high - </code><code>1</code> <code>> -</code><code>1</code> <code>&& arr[--high] > start);</code>

<code> </code><code>//如果i>j,則退出循環</code>

<code> </code><code>// 交換i和j位置的元素值</code>

<code> </code><code>arr[lowIndex] = arr[high];</code>

<code> </code><code>arr[high] = start;</code>

<code> </code><code>// 對右邊進行遞歸</code>

<code> </code><code>quickSort(arr, high + </code><code>1</code><code>, highIndex);</code>

<code> </code><code>// 對左邊進行遞歸</code>

<code> </code><code>quickSort(arr, lowIndex, high - </code><code>1</code><code>);</code>

<code> </code><code>return</code> <code>arr;</code>

三、選擇排序

直接選擇排序(Selection sort)是一種簡單直覺的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小元素，然後放到排序序列末尾(目前已被排序的序列)。以此類推，直到所有元素均排序完畢。

<code>public</code> <code>class</code> <code>Select_Sort {</code>

<code> </code><code>int</code> <code>lowIndex=i;</code>

<code> </code><code>if</code> <code>(score[k]>score[lowIndex]){</code>

<code> </code><code>lowIndex=k;</code>

<code> </code><code>int</code> <code>temp=score[i];</code>

<code> </code><code>score[i]=score[lowIndex];</code>

<code> </code><code>score[lowIndex]=temp;</code>

<code> </code><code>System.out.print(</code><code>"第"</code><code>+(i+</code><code>1</code><code>)+</code><code>"次選擇："</code><code>);</code>

四、排序算法特點，算法複雜度和比較

直接插入排序

如果目标是把n個元素的序列升序排列，那麼采用直接插入排序存在最好情況和最壞情況。最好情況就是，序列已經是升序排列了，在這種情況下，需要進行的比較操作需(n-1)次即可。最壞情況就是，序列是降序排列，那麼此時需要進行的比較共有n(n-1)/2次。直接插入排序的指派操作是比較操作的次數減去(n-1)次。平均來說直接插入排序算法複雜度為O(n2)。因而，直接插入排序不适合對于資料量比較大的排序應用。但是，如果需要排序的資料量很小，例如，量級小于千，那麼直接插入排序還是一個不錯的選擇。插入排序在工業級庫中也有着廣泛的應用，在STL的sort算法和stdlib的qsort算法中，都将插入排序作為快速排序的補充，用于少量元素的排序（通常為8個或以下）。

希爾排序

希爾排序是基于插入排序的一種算法，在此算法基礎之上增加了一個新的特性，提高了效率。希爾排序的時間複雜度為 O(N*(logN)2)，沒有快速排序算法快

O(N*(logN))，是以中等大小規模表現良好，對規模非常大的資料排序不是最優選擇。但是比O(N2）複雜度的算法快得多。并且希爾排序非常容易實作，算法代碼短而簡單。此外，希爾算法在最壞的情況下和平均情況下執行效率相差不是很多，與此同時快速排序在最壞的情況下執行的效率會非常差。專家們提倡，幾乎任何排序工作在開始時都可以用希爾排序，若在實際使用中證明它不夠快，再改成快速排序這樣更進階的排序算法.

希爾排序是按照不同步長對元素進行插入排序，當剛開始元素很無序的時候，步長最大，是以插入排序的元素個數很少，速度很快；當元素基本有序了，步長很小，插入排序對于有序的序列效率很高。是以，希爾排序的時間複雜度會比o(n^2)好一些。由于多次插入排序，我們知道一次插入排序是穩定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最後其穩定性就會被打亂，是以shell排序是不穩定的

冒泡排序

時間複雜度為O（n^2），雖然不及堆排序、快速排序的O（nlogn，底數為2），但是有兩個優點：1.“程式設計複雜度”很低，很容易寫出代碼；2.具有穩定性。

其中若記錄序列的初始狀态為"正序"，則冒泡排序過程隻需進行一趟排序，在排序過程中隻需進行n-1次比較，且不移動記錄；反之，若記錄序列的初始狀态為"逆序"，則需進行n(n-1）/2次比較和記錄移動。是以冒泡排序總的時間複雜度為O(n*n)。

快速排序

在最好的情況，每次我們執行一次分割，我們會把一個數列分為兩個幾近相等的片段。這個意思就是每次遞回調用處理一半大小的數列。是以，在到達大小為一的數列前，我們隻要作 log n 次巢狀的調用。這個意思就是調用樹的深度是O(log n)。但是在同一階層的兩個程式調用中，不會處理到原來數列的相同部份；是以，程式調用的每一階層總共全部僅需要O(n)的時間（每個調用有某些共同的額外耗費，但是因為在每一階層僅僅隻有O(n)個調用，這些被歸納在O(n)系數中）。結果是這個算法僅需使用O(n log n)時間。

另外一個方法是為T(n)設立一個遞回關系式，也就是需要排序大小為n的數列所需要的時間。在最好的情況下，因為一個單獨的快速排序調用牽涉了O(n)的工作，加上對n/2大小之數列的兩個遞回調用，這個關系式可以是：

T(n) = O(n) + 2T(n/2)

解決這種關系式型态的标準數學歸納法技巧告訴我們T(n) = O(n log n)。

事實上，并不需要把數列如此精确地分割；即使如果每個基準值将元素分開為 99% 在一邊和 1% 在另一邊，調用的深度仍然限制在 100log n，是以全部執行時間依然是O(n log n)。

然而，在最壞的情況是，兩子數列擁有大各為 1 和 n-1，且調用樹（call tree）變成為一個 n 個巢狀（nested）呼叫的線性連串（chain）。第 i 次呼叫作了O(n-i)的工作量，且遞回關系式為：

T(n) = O(n) + T(1) + T(n - 1) = O(n) + T(n - 1)

這與插入排序和選擇排序有相同的關系式，以及它被解為T(n) = O(n2)。

讨論平均複雜度情況下，即使如果我們無法随機地選擇基準數值，對于它的輸入之所有可能排列，快速排序仍然隻需要O(n log n)時間。因為這個平均是簡單地将輸入之所有可能排列的時間加總起來，除以n這個因子，相當于從輸入之中選擇一個随機的排列。當我們這樣作，基準值本質上就是随機的，導緻這個算法與亂數快速排序有一樣的執行時間。

更精确地說，對于輸入順序之所有排列情形的平均比較次數，可以借由解出這個遞回關系式可以精确地算出來。

在這裡，n-1 是分割所使用的比較次數。因為基準值是相當均勻地落在排列好的數列次序之任何地方，總和就是所有可能分割的平均。

這個意思是，平均上快速排序比理想的比較次數，也就是最好情況下，隻大約比較糟39%。這意味着，它比最壞情況較接近最好情況。這個快速的平均執行時間，是快速排序比其他排序算法有實際的優勢之另一個原因。

讨論空間複雜度時被快速排序所使用的空間，依照使用的版本而定。使用原地（in-place）分割的快速排序版本，在任何遞回呼叫前，僅會使用固定的額外空間。然而，如果需要産生O(log n)巢狀遞回呼叫，它需要在他們每一個儲存一個固定數量的資訊。因為最好的情況最多需要O(log n)次的巢狀遞回呼叫，是以它需要O(log n)的空間。最壞情況下需要O(n)次巢狀遞回呼叫，是以需要O(n)的空間。

然而我們在這裡省略一些小的細節。如果我們考慮排序任意很長的數列，我們必須要記住我們的變量像是left和right，不再被認為是占據固定的空間；也需要O(log n)對原來一個n項的數列作索引。因為我們在每一個堆棧架構中都有像這些的變量，實際上快速排序在最好跟平均的情況下，需要O(log2n)空間的位元數，以及最壞情況下O(n log n)的空間。然而，這并不會太可怕，因為如果一個數列大部份都是不同的元素，那麼數列本身也會占據O(n log n)的空間位元組。

非原地版本的快速排序，在它的任何遞回呼叫前需要使用O(n)空間。在最好的情況下，它的空間仍然限制在O(n)，因為遞回的每一階中，使用與上一次所使用最多空間的一半，且

它的最壞情況是很恐怖的，需要

空間，遠比數列本身還多。如果這些數列元素本身自己不是固定的大小，這個問題會變得更大；舉例來說，如果數列元素的大部份都是不同的，每一個将會需要大約O(log n)為原來儲存，導緻最好情況是O(n log n)和最壞情況是O(n2 log n)的空間需求。

不同條件下，排序方法的選擇

(1)若n較小(如n≤50)，可采用直接插入或直接選擇排序。　

當記錄規模較小時，直接插入排序較好；否則因為直接選擇移動的記錄數少于直接插入，應選直接選擇排序為宜。

(2)若檔案初始狀态基本有序(指正序)，則應選用直接插入、冒泡或随機的快速排序為宜；

(3)若n較大，則應采用時間複雜度為O(nlgn)的排序方法：快速排序、堆排序或歸并排序。　

快速排序是目前基于比較的内部排序中被認為是最好的方法，當待排序的關鍵字是随機分布時，快速排序的平均時間最短；　

堆排序所需的輔助空間少于快速排序，并且不會出現快速排序可能出現的最壞情況。這兩種排序都是不穩定的。　

若要求排序穩定，則可選用歸并排序。但本章介紹的從單個記錄起進行兩兩歸并的排序算法并不值得提倡，通常可以将它和直接插入排序結合在一起使用。先利用直接插入排序求得較長的有序子檔案，然後再兩兩歸并之。因為直接插入排序是穩定的，是以改進後的歸并排序仍是穩定的。

(4)在基于比較的排序方法中，每次比較兩個關鍵字的大小之後，僅僅出現兩種可能的轉移，是以可以用一棵二叉樹來描述比較判定過程。　

當檔案的n個關鍵字随機分布時，任何借助于"比較"的排序算法，至少需要O(nlgn)的時間。　

箱排序和基數排序隻需一步就會引起m種可能的轉移，即把一個記錄裝入m個箱子之一，是以在一般情況下，箱排序和基數排序可能在O(n)時間内完成對n個記錄的排序。但是，箱排序和基數排序隻适用于像字元串和整數這類有明顯結構特征的關鍵字，而當關鍵字的取值範圍屬于某個無窮集合(例如實數型關鍵字)時，無法使用箱排序和基數排序，這時隻有借助于"比較"的方法來排序。　

若n很大，記錄的關鍵字位數較少且可以分解時，采用基數排序較好。雖然桶排序對關鍵字的結構無要求，但它也隻有在關鍵字是随機分布時才能使平均時間達到線性階，否則為平方階。同時要注意，箱、桶、基數這三種配置設定排序均假定了關鍵字若為數字時，則其值均是非負的，否則将其映射到箱(桶)号時，又要增加相應的時間。

(5)有的語言(如Fortran，Cobol或Basic等)沒有提供指針及遞歸，導緻實作歸并、快速(它們用遞歸實作較簡單)和基數(使用了指針)等排序算法變得複雜。此時可考慮用其它排序。

(6)本章給出的排序算法，輸人資料均是存儲在一個向量中。當記錄的規模較大時，為避免耗費大量的時間去移動記錄，可以用連結清單作為存儲結構。譬如插入排序、歸并排序、基數排序都易于在連結清單上實作，使之減少記錄的移動次數。但有的排序方法，如快速排序和堆排序，在連結清單上卻難于實作，在這種情況下，可以提取關鍵字建立索引表，然後對索引表進行排序。然而更為簡單的方法是：引人一個整型向量t作為輔助表，排序前令t[i]=i(0≤i<n)，若排序算法中要求交換R[i]和R[j]，則隻需交換t[i]和t[j]即可；排序結束後，向量t就訓示了記錄之間的順序關系：

R[t[0]].key≤R[t[1]].key≤…≤R[t[n-1]].key

若要求最終結果是：

R[0].key≤R[1].key≤…≤R[n-1].key

則可以在排序結束後，再按輔助表所規定的次序重排各記錄，完成這種重排的時間是O(n)。

五、各排序算法時間複雜度和空間複雜度

排序法

平均時間

最差情形

穩定度

額外空間

備注

冒泡

O(n2)

穩定

O(1)

n小時較好

交換

不穩定

選擇

插入

穩定

大部分已排序時較好

基數

O(logrd)

O(n)

d是關鍵字項數(0-9)，

r是基數(個十百)

Shell

O(nlogn)

O(ns) 1<s<2

s是所選分組

快速

O(n2)

n大時較好

歸并

堆

本文轉自夢朝思夕 51CTO部落格，原文連結:http://blog.51cto.com/qiangmzsx/1414502

排序算法彙總總結_Java實作

繼續閱讀

資料結構與算法（27）——排序（二）

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method

hdu7108哈希