排序算法详解(Java实现 + 动画演示)
目錄
- 引言
- 一、排序算法概述
- 排序的定義
- 術語說明
- 排序算法分類及對比
- 比較排序和非比較排序的區別
- 二、十大經典排序算法
- 1、直接選擇排序
- 2、堆排序
- 3、直接插入排序
- 4、希爾排序
- 5、冒泡排序
- 6、快速排序
- 7、歸并排序
- 8、桶排序
- 9、計數排序
- 10、基數排序
- 三、特殊、有趣排序算法
- 1、猴子排序
- 2、珠排序
- 3、隨眠排序
- 4、意大利面排序
引言
本篇文章給出了十大經典排序算法和一些奇特、有趣的排序算法的實現原理解析,附有時間復雜度、空間復雜度分析和相應的Java實現代碼,并給出了動畫演示
?
如需瀏覽,請詳見目錄,即可快速定位到所需要的內容。之后將會持續修繕文章,如需及時收到最新內容,記得關注、收藏一下┗|`O′|┛ 嗷~~
一、排序算法概述
排序的定義
排序,是將一批無序的記錄(數據)重新排列成按關鍵字有序的記錄序列的過程;其目的是將一組“無序”的數據組調整為“有序”的數據組
術語說明
- 穩定:排序前a在b的前面,且a = b(該“=”的含義是在所定義的排序規則下是相等,包括但不僅限于數值上的相等),排序后a依舊在b的前面(相對位置保持不變)
- 不穩定:排序前a在b的前面,且a = b(該“=”的含義是在所定義的排序規則下是相等,包括但不僅限于數值上的相等),排序后a可能在b的前面,也可能在b的后面(相對位置發生變化)
- 內部排序:在排序過程中,所有元素調到內存中進行的排序
- 外部排序:在排序過程中,待排序記錄的數量很大,以致于內存不能一次容納全部記錄,故而在排序過程中需要對外存進行數據的臨時存放、訪問的排序
- 時間復雜度:描述了算法執行時間隨輸入規模增長而增長的量級
- 空間復雜度:描述了算法執行過程中臨時占用存儲空間大小的量度
排序算法分類及對比
符號解釋
- n:數據規模
- k:桶的個數
- In-place:僅占用常數級內存,不額外占用與數據規模有關內存空間
- Out-place:需額外占用與數據規模有關的內存空間
比較排序和非比較排序的區別
常見的冒泡排序、快速排序、歸并排序、堆排序等都屬于比較排序,而桶排序、計數排序、基數排序等則屬于非比較排序
比較排序的優勢是,適用于各種規模的數據,也不在乎數據的分布,都能進行排序;可以說,比較排序適用于一切需要排序的情況
非比較排序的優勢是,算法時間復雜度僅為O(n),即只要確定每個元素之前的已有的元素個數即可,排序僅需一次遍歷即可
雖然非比較排序的時間復雜度低,但是由于非比較排序需要占用額外空間來存唯一儲確定的位置,而且對于的數據規模和數據的分布有一定的要求,所以普適性不如比較排序;實際使用中,需要根據具體的待排序數據組的情況來抉擇!
二、十大經典排序算法
1、直接選擇排序
選擇排序(Select Sort)是一種簡單且直觀的排序算法,通常是大多數人在一般情況下可以直接想到的排序方法,同時也是表現最穩定的排序算法之一,無論什么數據組進去都是O()的時間復雜度;如果采用直接選擇排序進行排序的話,數據規模理應越小越好。其優點是不占用額外的內存空間并且利于理解!
其實現原理直觀來講,首先在還未排序的序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再從剩余未排序的元素中繼續尋找最小(大)元素,將此次循環找出的最小(大)元素放到已排序序列的末尾。循環往復,直到所有元素均排序完畢
算法描述
n個記錄的直接選擇排序可經過n - 1趟直接選擇排序得到有序結果
動畫演示
代碼實現
2、堆排序
要特別注意的是,在實際的面試中,經常會要求自行編寫代碼來實現堆排序(不能使用高級語言中已經封裝并實現了堆排序的函數方法或對象),故而要著重理解,一氣呵成、手撕堆排序啊@.@
堆的定義如下:n個元素的序列{k1, k2, …, kn}當且僅當滿足一下條件時,稱之為堆;可以將堆看做是一個完全二叉樹,并且每個結點的值都大于等于其左右孩子結點的值,稱為大頂堆,或者每個結點的值都小于等于其左右孩子結點的值,稱為小頂堆
堆排序(Heap Sort)是利用堆進行排序的方法。其基本思想為:將待排序列構造成一個大頂堆(或小頂堆),整個序列的最大值(或最小值)就是堆頂的根結點,將根節點的值和堆數組的末尾元素交換,此時末尾元素就是最大值(或最小值),然后將剩余的n-1個序列重新構造成一個堆,這樣就會得到n個元素中的次大值(或次小值),如此反復執行,最終得到一個有序序列
算法描述
動畫演示
代碼實現
3、直接插入排序
插入排序(Insertion Sort)的算法描述是一種簡單直觀的排序算法。其工作原理是通過構建有序序列,對于未排序數據,在已排序序列中從后向前掃描,找到相應位置并插入。插入排序在實現上,通常采用In-place排序(即只需用到O(1)的額外空間的排序),因而在從后向前掃描過程中,需要反復把已排序元素逐步向后挪位,為最新元素提供插入空間
算法描述
動畫演示
代碼實現
4、希爾排序
希爾排序(Shell Sort)是希爾(Donald Shell)于1959年提出的一種排序算法;希爾排序也是一種插入排序,它是簡單插入排序經過改進之后的一個更高效的版本,它與插入排序的不同之處在于,它會優先比較距離較遠的元素,故而也稱為縮小增量排序,同時該排序算法是沖破時間復雜度O()的第一批算法之一
希爾排序是把記錄按下表的一定增量分組,對每組使用直接插入排序算法排序;隨著增量逐漸減少,每組包含的關鍵詞越來越多,當增量減至1時,整個文件恰被分成一組,算法便終止
算法描述
選擇增量gap = length / 2,縮小增量繼續以gap = gap / 2的方式,這種增量選擇可以用一個序列來表示,{n / 2, (n / 2) / 2, …, 1},稱為增量序列。希爾排序的增量序列的選擇與證明是個數學難題,當前選擇的這個增量序列是比較常用的,也是希爾建議的增量,稱為希爾增量,但其實這個增量序列不是最優的!
動畫演示
代碼實現
Tip!!!
希爾排序的時間復雜度目前還沒有一個確切的結論,因為其時間復雜度是依賴于argument sequence的,也就是說根據使用不同的“增量”序列的函數,時間復雜度是不同的!而且希爾排序的復雜度分析還涉及到一些數學上目前尚未解決的難題!
?
但現在普遍的共識是希爾排序的時間復雜度介于O(nlogn) ~ O()之間,平均時間復雜度大致是O(),即O()
5、冒泡排序
冒泡排序(Bubble Sort)是一種簡單的排序算法。它重復地走訪過要排序的數列,一次比較兩個元素,如果它們的順序錯誤就把它們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換,也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端
算法描述
動畫演示
代碼實現
6、快速排序
快速排序(Quick Sort)的基本思想:通過一趟排序將待排記錄分隔成獨立的兩部分,其中一部分記錄的關鍵字均比另一部分的關鍵字小,則可分別對這兩部分記錄繼續進行排序,以達到整個序列有序
算法描述
快速排序使用分治法來把一個串(list)分為兩個子串(sub-lists)
動畫演示
代碼實現
7、歸并排序
同選擇排序一樣,歸并排序的性能不受輸入數據的影響,但表現比選擇排序好的多,因為始終都是O(n log n)的時間復雜度,但是代價是需要額外的內存空間
歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法(Divide and Conquer)的一個非常典型的應用;歸并排序是一種穩定的排序方法,將已有序的子序列合并,得到完全有序的序列;即先使每個子序列有序,再使子序列段間有序;若將兩個有序表合并成一個有序表,稱為2路歸并
算法描述
動畫演示
代碼實現
8、桶排序
桶排序(Bucket Sort)利用了函數的映射關系,高效與否的關鍵就在于這個映射函數的確定;其工作的原理是,假設輸入數據服從均勻分布,將數據分到有限數量的桶里,每個桶再分別排序(有可能再使用別的排序算法或是以遞歸方式繼續使用桶排序進行排序
算法描述
動畫演示
代碼實現
9、計數排序
計數排序(Count Sort)是一種穩定的排序算法,計數排序使用一個額外的數組C,其中第i個元素是待排序數組A中值等于i的元素的個數,然后根據數組C來將A中的元素排到正確的位置;它只能對整數進行排序;計數排序的核心在于將輸入的數據值轉化為鍵存儲在額外開辟的數組空間中。,作為一種線性時間復雜度的排序,計數排序要求輸入的數據必須是有確定范圍的整數
算法描述
動畫演示
代碼實現
10、基數排序
基數排序(Radix Sort)是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次類推,直到最高位。有時候有些屬性是有優先級順序的,先按低優先級排序,再按高優先級排序;最后的次序就是高優先級高的在前,高優先級相同的低優先級高的在前。基數排序基于分別排序,分別收集,所以是穩定的
算法描述
動畫演示
代碼實現
三、特殊、有趣排序算法
1、猴子排序
猴子排序(Bogo Sort),也叫作隨機排序;猴子代表亂的意思,猴子排序的意思就是亂排序,直到有序為止;其含義就是把一個無序的數組進行亂排序,然后看其是否會有序,這是個概率性事件,有可能一次之后就有序了,也有可能很多次后依然無序!最佳情況O(n),平均情況n * n!),最壞的情況下可以執行到世界末日!
其中將數據組隨機排序的實現方法,可以手動生成隨機數交換對應的下標數據,也可以調用不同語言提供的內置隨機洗牌函數shuffle(),對數據組進行隨機打亂
算法描述
代碼實現
/*** 猴子排序** @param arrayList 待排序的數據組* @return 排序次數*/ public static int bogoSort(ArrayList<Integer> arrayList) {int count = 0;while (!isSorted(arrayList)) {Collections.shuffle(arrayList);count++;}return count; }/*** 判斷是否已有序** @param arrayList 待判斷的數據組* @return 是否有序*/ public static boolean isSorted(ArrayList<Integer> arrayList) {int length = arrayList.size();for (int i = 1; i < length; i++) {if (arrayList.get(i - 1) > arrayList.get(i)) {return false;}}return true; }針對猴子排序,目前也有一種升級版,基于量子理論(但目前還不成熟)的排序:量子猴子排序(Quantum Bogo Sort)!其核心思想是,如果猴子排序隨機數據組時,使用量子化隨機排列,那么在我們觀測這組數據前,它的狀態是疊加的,通過這種排列我們就能劃分出全排列數量的平行宇宙,然后下面要做的就是去觀測這個宇宙,找到一個有序的平行宇宙即可。時間復雜度一直都是O(n),沒有最好、最壞之分!
2、珠排序
珠排序(Bead Sort)的思想是,一行(row)表示一個數字,如果一行里有2顆珠子,該行代表數字2;如果一行里有4顆珠子,該行代表數字4;給定一個數組,數組里有多少個數字,就要有多少行;數組里最大的數字是幾,就要準備多少根桿子
準備就緒后,釋放珠子,珠子(按重力)下落,就完成了排序
珠排序可以類比于珠子在平行的豎直桿上滑動,就像算盤一樣;允許珠子掉落的行為在物理意義上就是允許珠子從高的行掉落至低的行。如果被行a表示的值小于被行a + 1表示的值,那么一些珠子就會從a + 1掉落至a;因為行a不包含足夠的珠子防止珠從a + 1行掉落,所以這一定會發生
用機械裝置實現的珠排序類似于計數排序,每一桿上的數字與那些在所有數中等于或大于該數字的數量相當
3、隨眠排序
睡眠排序(Sleep Sort)也稱為硬件排序,充分利用硬件計時器的資源實現擬態算法
睡眠排序的主要思想是,構造n個線程,它們和這n個數一一對應;初始化后,線程們開始睡眠,等到線程們睡眠相應的時間單位后各自醒來,然后輸出對應的數,這樣最小的數對應的線程最早醒來,最打的數對應的線程最晚醒來等所有線程都醒來,排序就結束了
代碼實現
/*** 睡眠排序** @param arrayList 待排序的數據組*/ public static void sleepSort(ArrayList<Integer> arrayList) {for (Integer integer : arrayList) {sleepThread(integer);} }/*** 創建睡眠線程** @param a 睡眠時間*/ public static void sleepThread(int a){Thread thread = new Thread(() -> {try {Thread.sleep(a);System.out.println(a);} catch (InterruptedException e) {e.printStackTrace();}});thread.start(); }4、意大利面排序
意大利面條排序(Spaghetti Sort)的思路是,將數據組對應到不同長度的面條上,每根面條的長度即為對應的數字的大小;比如,對于[1, 4, 2, 8, 9]這個輸入,則分別做出長度為1cm、4cm、2cm、8cm、9cm的面條。然后,將這些面條的一頭對其,用手抓住,另一頭向下。然后慢慢地將手向下垂直下降,第一個觸碰到桌面的面條對應的數字則為最大的數字,第二個觸碰到的就是第二大的,依次類推
意大利面條排序簡直不是一個軟件可行的想法 - 它是一種按物理長度排序的“物理”理論方法?;旧纤f:“將一堆意大利面條棒推到一個平坦的表面上,使最長的那些比最短的更突出,從而按長度排序它們
最接近的類似想法并且可以實施的是Radix分類。但這僅適用于數據肯定屬于固定值集并且足夠小以適應可用資源(例如RAM)的情況
參考資料
- https://www.latexlive.com
- https://blog.csdn.net/zolalad/article/details/11848739
- http://www.elecfans.com/d/874748.html
- https://blog.csdn.net/weixin_40539125/article/details/93379360
免責申明:相關文章及資料僅供學習交流使用,禁止一切不正當行為,如由此產生相關責任,自行承擔
?
Tip:如需轉發或引用相關內容,請務必附帶原鏈接
如果對你有幫助的話,麻煩關注一波,并且點贊、收藏、轉發一下哦o( ̄︶ ̄)o!如果有問題或者發現Bug歡迎提出反饋!
總結
以上是生活随笔為你收集整理的排序算法详解(Java实现 + 动画演示)的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 或许我们做错了,但绝非一无是处
- 下一篇: 【置顶】囚生CYのPOST(NEW VE