基礎排序演算法—冒泡,插入,選擇
- 2020 年 4 月 10 日
- 筆記
前言
冒泡,插入,選擇這三種基礎的排序演算法,比較簡單效率不高,工作中一般不會使用,但是當做演算法來研究還是能了解一些知識的,本文以<數據結構與演算法之美>為基礎,詳細解析一下.
正文
首先要引入幾個概念
穩定性
如果待排序數組中有相同的元素,排序過後它們的相對順序不發生變化. 比如 2，9，3，4，8，3 排序過後為2, 3 , 3, 4, 8, 9 這兩個3的相對順序不變.這樣就是具有穩定性. 穩定性可以保證複雜數據結構排序時的相對有序性. 比如我們要對一筆訂單先按金額排列,金額相同的再按時間排序
就可以先將這筆訂單按照時間排序,再採用具有穩定性的排序演算法按金額進行排序. 猜測Java8中的compare().thenCompare()就是採用這種原理實現
原地排序
排序過程中只佔用常數級的額外空間或者不佔用額外空間
有序度
數組中具有有序關係的元素對的個數,數學表達式為 有序元素對：a[i] <= a[j], 如果i < j。
2,4,3,1,5,6 的有序度為11,有序元素對為(2,4),(2,3),(2,5),(2,6),(4,5),(4,6),(3,5),(3,6),(1,5),(1,6),(5,6)
對 6,5,4,3,2,1 這個完全逆序的數組,有序度為0
對 1,2,3,4,5,6 這個完全有序的數組,有序度為(n-1)+(n-2)+(n-3)+...+0 = n*(n-1)/2 = 15,即滿有序度
逆序度
和有序度定義正好相反 逆序度 = 滿有序度 – 有序度
約定
為了方便描述,這裡約定數組為arr[0~n],n≥1,排列方式為正序(從小到大).
下面的描述不會舉例講解,推薦到 visualgo查看動畫演示
冒泡排序
主要思路
首先將數組在邏輯劃分為左側的未排序部分和右側的已排序部分
冒泡排序中對未排序部分的一次遍歷稱為一次冒泡,初始時未排序部分為arr[0~n-1],未排序部分為空.冒泡一次後,未排序部分為arr[0~n-2],已排序部分為arr[n-1~n-1],冒泡x(1≤x<n)次後,未排序部分為arr[0~n-1-x),已排序部分為arr[n-x~n-1],最終達成全部排序
每次冒泡未排序部分時,只會操作相鄰的元素,方向為 arr[0]→ arr[n-1],如果a[i]>a[i+1]就進行交換,這樣一次冒泡操作後,未排序部分中的最大值就會移動到已排序部分且在最左側(即已排序部分的最小值).
同時,如果一次冒泡後沒有進行過任何交換說明整個數組已經有序了,結合這個特性可以省去不必要的冒泡,核心程式碼如下
public void sort(Comparable[] a) { if (a.length <= 1) { return; } for (int i = a.length - 1; i > 0; i--) { boolean changeFlag = false; for (int j = 0; j < i; j++) { if (a[j + 1].compareTo(a[j]) < 0) { swap(a, j + 1, j); changeFlag = true; } } if (!changeFlag) { break; } } } 時間複雜度
最壞情況下,數組完全倒序, 時間複雜度為 (n-1)+(n-2)+(n-3)+…+1 = (n^2)/2 ~= O(n^2) 數字表示交換的次數
最好情況下,數組已經有序,只需要一次冒泡, 時間複雜度為 O(n) 這裡不會有交換,以比較的次數作為計量單位
平均情況下,用概率推算會很困難,這裡採用上面提到的有序度和逆序度,並將元素的交換次數當做計量單位, 觀察可以看到,每交換一次,都會使原來逆序的一組元素變為有序,逆序度即為交換次數,那麼在最好情況下逆序度為0,最壞情況下逆序度為n(n-1)/2,平均時間複雜度為兩者取平均值
(0 + n(n-1)/2)/2 = O(n^2)
是原地排序嗎?
冒泡排序涉及到兩個元素的交換,交換時只使用了一個單位臨時空間,是原地排序
穩定嗎?
冒泡排序中元素位置發生變化交換時,並且交換僅在a[i]>a[i+1]時才發生,a[i]==a[i+1]時時不會發生的,因此是穩定的
插入排序
主要思路
將數組分為左側的已排序部分和右側的未排序部分
初始時已排序部分為arr[0~0],未排序部分為arr[1~n-1]一次插入後,已排序部分為arr[0~1],未排序部分為arr[2~n-1],x(1≤x<n)次插入後,已排序部分為arr[0x],未排序部分為arr(x+1n-1]
從未排序部分的起始位置開始(即arr[1]),每次插入時,方向為 arr[n-1]→ arr[0],找出第一個小於等於arr[i]的元素,有兩種情況
- 找到了,插入在它之後(具體實現時 假設找到的下標為j, 將a[j+1~i-1]的元素依次後移,再將a[i]設置到a[j+1]),
- 沒找到,說明a[i]就是當前最小的元素,將a[0~i-1]的元素依次後移,將a[i]設置到a[0]
核心程式碼如下
public void sort(Comparable[] arr) { if (arr.length <= 1) { return; } for (int i = 1; i < arr.length; i++) { Comparable insertValue = arr[i]; int insertPos = i; for (int j = i - 1; j >= 0; j--) { if (insertValue.compareTo(arr[j]) < 0) { arr[j + 1] = arr[j]; insertPos = j; } else { insertPos = j + 1; break; } } arr[insertPos] = insertValue; } } 時間複雜度
以元素移動的次數作為計量單位
最壞情況下,數組完全倒序,時間複雜度為 0 + 1 + 2 + 3 +…+ (n-1) = n*(n-1)/2 ~= O(n^2)
最好情況下,數組完全順序, 時間複雜度為 1 + 1 + 1 + … + 1= n ~=O(n)
平均情況下, 我們仍然使用逆序數這個概念,再觀察依舊可以得知: 逆序數等於移動次數,所以時間複雜度為 (0 + n(n-1)/2)/2 ~= O(n^2)
是原地排序嗎?
插入排序中,沒有使用額外的空間,因此是原地排序
穩定嗎
插入排序中,只有移動操作會改變元素位置,而判定條件是小於等於arr[i] ,符合情況1,a[i]會被設置到a[j+1],從而保證相對順序的穩定.
選擇排序
主要思路
將數組分為左側的已排序部分和右側的未排序部分
選擇排序中選擇表示對未排序部分的一次遍歷,初始時已排序部分為空,未排序部分為arr[0~n-1],
一次選擇後,已排序部分為arr[0~0],未排序部分為arr[1~n-1],x(1≤x<n)次選擇後,已排序部分為arr[0~x-1],未排序部分為arr(x~n-1]
第x(1≤x<n)次選擇時,找出未排序數組中的最小值,放入已排序數組(與arr[x-1]交換),核心程式碼如下
public void sort(Comparable[] arr) { if (arr.length <= 1) { return; } for (int i = 1; i < arr.length ; i++){ int minPos=i-1; Comparable minValue=arr[i-1]; for(int j=i;j<arr.length;j++){ if (minValue.compareTo(arr[j])>0){ minPos=j; minValue=arr[j]; } } swap(arr,minPos,i-1); } } 時間複雜度
以minValue被替換的次數作為計量單位.
最壞情況下為 (n-1) + (n-2) + … + 0 =n(n-1)/2 ~= O(n^2)
最好情況下為 1+1+1…+1 =n ~= O(n)
平均情況下,仍然使用逆序數, 可以發現: 逆序數等於替換的次數,因此時間複雜度為(0 + n(n-1)/2)/2 ~= O(n^2)
是原地排序嗎?
選擇排序中,minValue使用了一個單位的額外空間,因此是原地排序
穩定嗎
選擇排序中,沒有約束可以確保穩定, 比如 4, 3, 2, 4, 1 排序過後,兩個4的相對位置會發生變化
冒泡,插入,選擇的比較
三者的相同之處
- 將數組虛擬為
已排序和未排序部分,在排序過程中逐步將未排序部分轉化為已排序部分. - 都是原地排序
- 平均時間複雜度都是O(n^2)
三者的不同之處
- 冒泡排序,插入排序是穩定的,選擇排序時
不穩定的 - 冒泡和選擇頻繁使用交換操作,插入排序較多使用賦值操作,而賦值相比交換性能更好
三者比較,根據我這裡的簡單測試 性能方面選擇>插入>冒泡, 但是選擇排序不穩定,僅此一點很多場景下就不適用,實用性大大降低. 因此插入排序時三者中較好的選擇.
總結
冒泡,插入,選擇是三種基本的排序演算法,研究他們對學習更高效的排序演算法有幫助,相關源碼已經上傳到這裡
