本系列文章【資料結構與演算法】所有完整代碼已上傳 github，想要完整代碼的小伙伴可以直接去那獲取，可以的話歡迎點個Star哦~下面放上跳轉鏈接

• https://github.com/Lpyexplore/structureAndAlgorithm-JS

之前的文章，我已經把前端需要了解的資料結構都給說了一邊，并且我們也都對其進行了封裝，現在我們要開始對排序演算法部分進行講解，排序演算法顧名思義，就是對一堆雜亂無章的資料按照一定的規則將它們有序地排列在一起，

在講解排序演算法時，大致分成兩大類，如下圖

本文先介紹三種簡單排序的實作思路以及代碼的實作

公眾號：Lpyexplore的編程小屋
關注我，不定時更新前端面試題
關注還有更多電子書、面試題、資料結構與演算法代碼等你來拿

一、大O表示法

大O表示法是一種大致表示演算法時間復雜度的表示方法，其中，演算法的時間復雜度表示的是演算法執行程序中代碼所需要的基本運算次數，

問： 假設現在有5個人，分別為 A、B、C、D 、E，它們的身高分別為 165、178、150、180、200，請你找出最高的那個人，并記錄比較次數，

我們來說一個特別簡單易懂的演算法，來了解大O表示法

答： 我們先用 A 跟 B 比較，得 B 比 A 高 ； 那我們就用 B 跟 C 比較，得 C 比 B 矮 ；繼續用 B 與 D 比較，得 D 比 B 高 ；最后用 D 跟 E 比較，得 E 比 D 高，因此，最終得出 E 是這五個人里最高得，同時我們記下得比較次數為 4 次，

那么同樣用這種方法，人數現在設定為 n，那么我們最多需要比較得次數就為 n - 1 次，此時我們可以將這種演算法的時間復雜度就為 O(n)

為什么是 O(n) 呢？因為在用這種表示方法時，其實是一種模糊的統計方法，我們要遵循以下幾個原則：

1. 代碼運行次數只取最高次項
2. 所有加法項的常數都用1代替
3. 最高次項的常數用1代替

因此當比較次數為 n - 1 時，我們要只取最高次項，并且將最高次項的常數項變為 1，因此用大O表示法就為 O(n)

其它常見的幾種大O表示法還有下面幾種：

在之后每種排序演算法中，我們都會簡單來判斷一下它們的時間復雜度，并用大O表示法來表示

二、冒泡排序

冒泡排序是一種最簡單粗暴的排序演算法，它的排序方式跟它的名字一樣，一個個資料往上冒出來，

我們來看一下具體的實作程序（該排序程序為從小到大排序），直接來看個動圖

主要的思路其實就是從最左邊開始，依次比較相鄰兩個元素的大小，若左邊的數大于右邊的數就進行交換，這樣把所有的相鄰元素都比較一遍以后，最右邊的數就是其中最大的數了，

緊接著又繼續從最左邊開始，依次比較各個相鄰元素，并判斷是否需要交換位置，但與第一遍不同的是，最右邊的數不需要進行比較，因為它已經是最大的了，因此第二遍比較完后從右往左數第二個數是其中第二大的數，

以此類推，就能將資料按從小到大的順序排好了

我們來看一下如何封裝冒泡排序的函式吧

function bubbleSort(arr) {

	// 封裝一個交換函式,便于之后呼叫
	function exchange(v1, v2) {
		let temp = arr[v1]
		arr[v1] = arr[v2]
		arr[v2] = temp
	}
	
	// 獲取傳入陣列的長度
	let length = arr.length
	
	// 1. 設定每次遍歷的長度,每遍歷一次，長度 - 1
	for(let i = length - 1; i >= 0; i --) {
		// 2. 從最左邊的數開始，依次比較相鄰元素
		for(let j = 0; j < i; j ++) {
			// 3. 如果左邊的數大于右邊的數，則交換一下兩個元素
			if(arr[j] > arr[j + 1]) {
				exchange(j, j + 1)
			}
		}
	}
	
	// 回傳排序后的陣列
	return arr
}

我們來簡單測驗一下該方法是否正確

let arr = [45, 66, 1, 19, 34, 80, 2]

console.log(bubbleSort(arr));
// 列印結果：[1, 2, 19, 34, 45, 66, 80]

接下來，討論一下冒泡排序的 比較次數 和 交換次數 如何用大O表示法來表示，

假設一個陣列一共有4個數，我們第一次遍歷需要比較3次，此時找到一個最大值；第二次遍歷只需要將其中3個數進行比較，只需要比較2次，此時找到第二大的值；第三次遍歷只需要將剩余的兩個數進行比較，只需要比較1次，此時陣列排序完畢，如果不明白，可以看一下上面的動圖

該種情況的比較次數一共是 3 + 2 + 1 = 6 次，那么延伸到普通情況中，一個陣列有 n 個元素，那么所需要的比較次數一共是 (n-1) + (n-2) + …… + 2 + 1 = n*(n-1)/2 ，按照大O表示法的規則，我們找到最高次項為 n2/2，將其常數項設為1，為 n2，因此冒泡排序的比較次數用大O表示法為 O(n2)

我們再來看看冒泡排序的交換次數如何用大O表示法來表示，很明顯，我們也不清楚到底要交換幾次，所以我們就假設每兩次比較就要交換一次的話，其總的交換次數為 n*(n-1)/4，根據大O表示法的規則，我們可以知道交換次數用大O表示法也為 O(n2)

總結：

1. 冒泡排序的比較次數：O(n2)
2. 冒泡排序的交換次數：O(n2)

三、選擇排序

選擇排序跟冒泡排序非常類似，唯一的區別就是選擇排序每次遍歷時，將各個元素比較，將最大值或最小值的索引存放在一個變數中，全部比較完了以后，再將該索引上的元素進行就交換，簡單來說就是選擇排序是每次遍歷交換一次，而冒泡排序每次遍歷需要交換多次，因此選擇排序一般來說是要比冒泡排序效率高一點的，

同樣的，我們來看一下選擇排序（從小到大排序）的動圖展示：

我們來看一下選擇排序的代碼封裝

function selectionSort(arr) {
    // 封裝交換元素的函式，方便后面呼叫
    function exchange(v1, v2) {
        let temp = arr[v1]
        arr[v1] = arr[v2]
        arr[v2] = temp
    }
	
	// 獲取傳入陣列的長度
    let length = arr.length
	
	// 1. 設定遍歷的范圍
	for(let i = 0; i < length - 1; i ++) {
		// 2. 先將遍歷的起始索引設為最小值的索引
		let min = i
		// 3. 從索引為min的后一個值開始遍歷全部元素
		for(let j = min; j < length; j ++) {
			// 3.1 將每個遍歷到的元素與arr[min]比較
			if(arr[min] > arr[j]) {
				min = j
			}
		}
		// 4. 將得到的最小值的索引min上的元素與我們初始遍歷的位置上的元素交換
		exchange(min, i)
	}

	// 回傳排序后的陣列
	return arr
}

我們來測驗一下該方法是否正確

let arr = [45, 66, 1, 19, 34, 80, 2]

console.log(selectionSort(arr));
// 列印結果：[1, 2, 19, 34, 45, 66, 80]

在了解了選擇排序與冒泡排序的區別后，我們應該能清楚得知道，選擇排序的比較次數跟冒泡排序一樣，因此選擇排序的比較次數用大O表示法表示為 O(n2)

選擇排序每遍歷一次陣列，就只需要交換一次資料，因此其交換次數用大O表示法表示為 O(n)

總結：

1. 選擇排序的比較次數：O(n2)
2. 選擇排序的交換次數：O(n)

四、插入排序

插入排序是一種將指定元素與某個有序區域元素比較并交換位置的排序演算法，

我們先簡單舉個例子，假設現在有這樣一個無序陣列

首先，我們把索引為0的元素看作區域，該區域是有序的，因為就只有一個元素，怎樣排序都是它一個元素，所以就認為它是有序的，

然后我們取出有序區域右邊的第一個元素，即索引為1的元素 67，存到變數 temp 中，然后從有序區域的最右邊開始，將元素依次與變數 temp 中的元素 67 比較，若大于67，則將位置向右移動一格；若小于67，則不需要繼續遍歷了，因為該區域是有序的，

第一次遍歷的動圖：

此時的有序區域為 索引0 ~ 索引1 這部分，所以我們將索引為2的元素取出，跟有序區域的元素比較

第二次遍歷的動圖：

此時的有序區域為 索引0 ~ 索引2 這部分，所以我們將索引為3的元素取出，跟有序區域的元素比較

第三次遍歷的動圖：

此時的有序區域為 索引0 ~ 索引3 這部分，所以我們將索引為4的元素取出，跟有序區域的元素比較

第四次遍歷的動圖：

此時整個陣列都是有序區域了，這就是一個完整的插入排序

接下來我們來封裝一個插入排序的函式

function insertionSort(arr) {
	// 獲取傳入陣列的長度
    let length = arr.length
	
	// 1. 從索引為1的元素開始向后遍歷陣列
	for(let i = 1; i < length; i ++) {
		// 2. 取出有序區域右邊第一個元素
		let temp = arr[i]
		let j = i
		// 3. 從右往左將有序區域內的元素與temp比較
		while(arr[j - 1] > temp && j > 0) {
			arr[j] = arr[j - 1]
			j --
		}
		// 4. 將temp插入到合適的位置
		arr[j] = temp
	}
	
	// 回傳排序后的陣列
	return arr
}

我們來測驗一下該函式是否正確

let arr = [45, 66, 1, 19, 34, 80, 2]

console.log(insertionSort(arr));
// 列印結果：[1, 2, 19, 34, 45, 66, 80]

插入排序每次遍歷時，比較次數和元素的移動次數都是不確定，那我們就按最壞的情況來考慮，

第一次遍歷：比較次數為1，元素移動次數為1；
第二次遍歷：比較次數為2，元素移動次數為2；
……
第N次遍歷：比較次數為N，元素移動次數為N；

所以，插入排序的比較次數為 1 + 2 + …… + n，元素的移動次數也和比較次數一樣，那么我們對其取個平均值，也就是 (n2 - n)/4，用大O表示法表示為 O(n2)

總結：

1. 插入排序的比較次數：O(n2)
2. 插入排序的元素移動次數：O(n2)

五、結束語

排序演算法中的簡單排序就已經講完啦，下一篇文章將講解三種高級排序演算法：希爾排序、歸并排序、快速排序，

大家可以關注我，之后我還會一直更新別的資料結構與演算法的文章來供大家學習，并且我會把這些文章放到【資料結構與演算法】這個專欄里，供大家學習使用，

然后大家可以關注一下我的微信公眾號：Lpyexplore的編程小屋，等這個專欄的文章完結以后，我會把每種資料結構和演算法的筆記放到公眾號上，大家可以去那獲取，

或者也可以去我的github上獲取完整代碼，歡迎大家點個Star

• https://github.com/Lpyexplore/structureAndAlgorithm-JS

我是Lpyexplore，創作不易，喜歡的加個關注，點個收藏，給個贊~