JavaScript如何實現(xiàn)十大排序算法

本文小編為大家詳細介紹“JavaScript如何實現(xiàn)十大排序算法”，內(nèi)容詳細，步驟清晰，細節(jié)處理妥當，希望這篇“JavaScript如何實現(xiàn)十大排序算法”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學習新知識吧。

冒泡排序

排序的效果圖

解法

當前解法為升序

冒泡排序的特點，是一個個數(shù)進行處理。第i個數(shù)，需要與后續(xù)的len-i-1個數(shù)進行逐個比較。

為什么是 `len-i-1`個數(shù)？

因為數(shù)組末尾的i個數(shù)，已經(jīng)是排好序的，確認位置不變的了。

為什么確認位置不變，因為它們固定下來之前，已經(jīng)和前面的數(shù)字都一一比較過了。

function bubbleSort(arr){
	const len = arr.length;
	for(let i = 0; i < len - 1; i++){
		for(let j = 0; j < len - i - 1; j++){
			if(arr[j] > arr[j+1]){
				const tmp = arr[j+1];
				arr[j+1] = arr[j];
				arr[j] = tmp;
			}
		}
	}

	return arr;
}

快速排序

概要

快速排序，使用的是分治法的思想。
通過選定一個數(shù)字作為比較值，將要排序其他數(shù)字，分為 >比較值 和 <比較值，兩個部分。并不斷重復這個步驟，直到只剩要排序的數(shù)字只有本身，則排序完成。

效果圖

解法

function quickSort(arr){

	sort(arr, 0, arr.length - 1);
	return arr;


	function sort(arr, low, high){
		if(low >= high){
			return;
		}
	
		let i = low;
		let j = high;
		const x = arr[i]; // 取出比較值x，當前位置i空出，等待填入
		while(i < j){
			// 從數(shù)組尾部，找出比x小的數(shù)字
			while(arr[j] >= x && i < j){
				j--;
			}
			// 將空出的位置，填入當前值， 下標j位置空出
			// ps：比較值已經(jīng)緩存在變量x中
			if(i < j){
				arr[i] = arr[j]
				i++;
			}

			// 從數(shù)組頭部，找出比x大的數(shù)字
			while(arr[i] <= x && i < j){
				i++;
			}
			// 將數(shù)字填入下標j中，下標i位置突出
			if(i < j){
				arr[j] = arr[i]
				j--;
			}
			// 一直循環(huán)到左右指針i、j相遇，
			// 相遇時，i==j, 所以下標i位置是空出的
		}

		arr[i] = x; // 將空出的位置，填入緩存的數(shù)字x，一輪排序完成

		// 分別對剩下的兩個區(qū)間進行遞歸排序
		sort(arr, low, i - 1);
		sort(arr, i+1, high);
	}
}

希爾排序

概要

希爾排序是一種插入排序的算法，它是對簡單的插入排序進行改進后，更高效的版本。由希爾（Donald Shell）于1959年提出。
特點是利用增量，將數(shù)組分成一組組子序列，然后對子序列進行插入排序。
由于增量是從大到小，逐次遞減，所以也稱為縮小增量排序。

效果圖

解法

注意點
插入排序時，并不是一個分組內(nèi)的數(shù)字一次性用插入排序完成，而是每個分組交叉進行。

執(zhí)行插入時，使用交換法

function shellSort(arr){
	// 分組規(guī)則 gap/2 遞減
	for(let gap = Math.floor(arr.length/2); gap > 0; gap = Math.floor(gap/2)){
		for(let i = gap; i < arr.length; i++){
			let j = i;
			// 分組內(nèi)數(shù)字，執(zhí)行插入排序，
			// 當下標大的數(shù)字，小于 下標小的數(shù)字，進行交互
			// 這里注意，分組內(nèi)的數(shù)字，并不是一次性比較完，需要i逐步遞增，囊括下個分組內(nèi)數(shù)字
			while(j - gap >= 0 && arr[j] < arr[j - gap]){
				swap(j, j-gap);
				j = j - gap;
			}
		}
	}

	return arr;

	function swap(a, b){
		const tmp = arr[a];
		arr[a] = arr[b];
		arr[b] = tmp;
	}
}

執(zhí)行插入時，使用移動法

function shellSort(arr){

	for(let gap = Math.floor(arr.length/2); gap > 0; gap = Math.floor(gap/2)){
		for(let i = gap; i < arr.length; i++){
			let j = i;
			const x = arr[j]; // 緩存數(shù)字，空出位置

			while(j - gap >= 0 && x < arr[j-gap]){
				arr[j] = arr[j - gap]; // 將符合條件的數(shù)字，填入空出的位置
				j = j - gap;
			}
			arr[j] = x; // 最后，將緩存的數(shù)字，填入空出的位置
		}
	}

	return arr;
}

選擇排序

排序的效果圖

解法

當前解法為升序

function selectionSort(arr){
	const len = arr.length;

	for(let i = 0; i < len-1; i++){
		let minIndex = i;
		for(let j = i+1; j < len; j++){
			if(arr[j] < arr[minIndex]){
				minIndex = j; // 保存最小數(shù)的下標
			}
		}

		const tmp = arr[i];
		arr[i] = arr[minIndex];
		arr[minIndex] = tmp;
	}

	return arr;
}

歸并排序

概要

歸并排序，利用分治思想，將大的數(shù)組，分解為小數(shù)組，直至單個元素。然后，使用選擇排序的方式，對分拆的小數(shù)組，進行回溯，并有序合并，直至合并為一個大的數(shù)組。

效果圖

小數(shù)組合并的過程

解法

function mergeSort(arr){

	return sort(arr, 0, arr.length - 1); // 注意右區(qū)間是arr.length - 1

	// sort方法，進行遞歸
	function sort(arr, left, right){
		
		// 當left !== right時，證明還沒分拆到最小元素
		if(left < right){
			// 取中間值，分拆為兩個小的數(shù)組
			const mid = Math.floor((left+right) / 2);
			const leftArr = sort(arr, left, mid);
			const rightArr = sort(arr, mid+1, right);
			// 遞歸合并
			return merge(leftArr, rightArr)
		}

		// left == right, 已經(jīng)是最小元素，直接返回即可
		return left >= 0 ? [arr[left]] : [];
	}

	// 合并兩個有序數(shù)組
	function merge(leftArr, rightArr){
		let left = 0;
		let right = 0;
		const tmp = [];

		// 使用雙指針，對兩個數(shù)組進行掃描
		while(left < leftArr.length && right < rightArr.length){
			if(leftArr[left] <= rightArr[right]){
				tmp.push(leftArr[left++]);
			}else{
				tmp.push(rightArr[right++]);
			}
		}

		// 合并剩下的內(nèi)容
		if(left < leftArr.length){
			while(left < leftArr.length){
				tmp.push(leftArr[left++]);
			}
		}

		if(right < rightArr.length){
			while(right < rightArr.length){
				tmp.push(rightArr[right++]);
			}
		}

		return tmp;
	}

}

插入排序

排序的效果圖

解法

當前解法為升序

function insertionSort(arr){
	const len = arr.length;

    // 注意，i 從 1 開始
	for(let i = 1; i < len; i++){
		let preIndex = i - 1;
		let current = arr[i];

        // 位置i之前，是已排好序的數(shù)字，while的作用是找到一個坑位，給當前數(shù)字current插入
		while(preIndex >= 0 && arr[preIndex] > current){
			arr[preIndex+1] = arr[preIndex]; // 對大于current的值，往后移一位，給current的插入騰出位置
			preIndex--;
		}
		arr[preIndex+1] = current;
	}

	return arr;
}

堆排序

概要

堆的表示形式

邏輯結構的表示如下：

在物理數(shù)據(jù)層的表示如下：

堆排序，是選擇排序的優(yōu)化版本，利用數(shù)據(jù)結構——樹，對數(shù)據(jù)進行管理。

以大頂堆為例:

• 通過構建大頂堆

• 將堆頂?shù)淖畲髷?shù)拿出，與堆底的葉子節(jié)點進行交換

• 接著，樹剪掉最大數(shù)的葉子

• 再對堆進行調(diào)整，重新變成大頂堆

• 返回步驟2，以此循環(huán)，直至取出所有數(shù)

效果圖

在實現(xiàn)代碼時，構建大頂堆時，先保證左右子樹的有序，再逐步擴大到整棵樹。

構建大頂堆

從第一個非葉子節(jié)點開始，調(diào)整它所在的子樹

調(diào)整下標1節(jié)點的子樹后，向上繼續(xù)調(diào)整它的父節(jié)點（下標0）所在的子樹

最后，完成整個樹的調(diào)整，構建好大頂堆。

逐個抽出堆頂最大值

堆頂數(shù)字與最末尾的葉子數(shù)字交換，抽出堆頂數(shù)字9。

此時，數(shù)字9位置固定下來，樹剪掉9所在的葉子。然后，重新構建大頂堆。

大頂堆構建好后，繼續(xù)抽出堆頂數(shù)字8，然后再次重新構建大頂堆。

最后，所有節(jié)點抽出完成，代表排序已完成。

解法

以大頂堆為例，對數(shù)組進行升序排序

注意點
樹的最后一個非葉子節(jié)點：(arr.length / 2) - 1
非葉子節(jié)點i的左葉子節(jié)點： i*2+1
非葉子節(jié)點i的右葉子節(jié)點： i*2+2

function heapSort(arr){

	// 初次構建大頂堆
	for(let i = Math.floor(arr.length/2) - 1; i >= 0; i--){
		// 開始的第一個節(jié)點是 樹的最后一個非葉子節(jié)點
		// 從構建子樹開始，逐步調(diào)整
		buildHeap(arr, i, arr.length);
	}

	// 逐個抽出堆頂最大值
	for(let j = arr.length -1 ; j > 0; j--){
		swap(arr, 0, j); // 抽出堆頂（下標0）的值，與最后的葉子節(jié)點進行交換
		// 重新構建大頂堆
		// 由于上一步的堆頂最大值已經(jīng)交換到數(shù)組的末尾，所以，它的位置固定下來
		// 剩下要比較的數(shù)組，長度是j,所以這里的值length == j
		buildHeap(arr, 0, j); 
	}

	return arr;

	
	// 構建大頂堆
	function buildHeap(arr, i, length){
		let tmp = arr[i]; 
		
		for(let k = 2*i+1; k < length; k = 2*k+1){
			// 先判斷左右葉子節(jié)點，哪個比較大
			if(k+1 < length && arr[k+1] > arr[k]){
				k++;
			}
			// 將最大的葉子節(jié)點，與當前的值進行比較
			if(arr[k] > tmp){
				// k節(jié)點大于i節(jié)點的值，需要交換
				arr[i] = arr[k]; // 將k節(jié)點的值與i節(jié)點的值交換
				i = k; // 注意：交換后，當前值tmp的下標是k，所以需要更新
			}else{
				// 如果tmp大于左右子節(jié)點，則它們的子樹也不用判斷，都是小于當前值
				break;
			}
			
		}

		// i是交換后的下標，更新為tmp
		arr[i] = tmp;
	}


	// 交換值
	function swap(arr, i, j){
		const tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
}

計數(shù)排序

概要

計數(shù)排序的要點，是開辟一塊連續(xù)格子組成的空間，給數(shù)據(jù)進行存儲。
將數(shù)組中的數(shù)字，依次讀取，存入其值對應的下標中。
儲存完成后，再按照空間的順序，依次讀取每個格子的數(shù)據(jù)，輸出即可。

所以，計數(shù)排序要求排序的數(shù)據(jù)，必須是有范圍的整數(shù)。

效果圖

解法

function countingSort(arr){
    let maxValue = Number.MIN_VALUE;
    let minValue = Number.MAX_VALUE;
    let offset = 0; // 位移，用于處理負數(shù)
    const result = [];

    // 取出數(shù)組的最大值, 最小值
    arr.forEach(num => {
        maxValue = num > maxValue ? num : maxValue;
        minValue = num > minValue ? minValue : num;
    });

    if(minValue < 0){
        offset = -minValue;
    }

    const bucket = new Array(maxValue+offset+1).fill(0); // 初始化連續(xù)的格子

    // 將數(shù)組中的每個數(shù)字，根據(jù)值放入對應的下標中，
    // `bucket[num] == n`格子的意義：存在n個數(shù)字，值為num
    arr.forEach(num => {
        bucket[num+offset]++;
    });

    // 讀取格子中的數(shù)
    bucket.forEach((store, index) => {
        while(store--){
            result.push(index - offset);
        }
    });

    return result;

}

桶排序

概要

桶排序是計數(shù)排序的優(yōu)化版，原理都是一樣的：分治法+空間換時間。
將數(shù)組進行分組，減少排序的數(shù)量，再對子數(shù)組進行排序，最后合并即可得到結果。

效果圖

解法

對桶內(nèi)數(shù)字的排序，本文采用的是桶排序遞歸。其實它的本質(zhì)是退化到計數(shù)排序。

function bucketSort(arr, bucketSize = 10){
	// bucketSize 每個桶可以存放的數(shù)字區(qū)間(0, 9]

	if(arr.length <= 1){
		return arr;
	}
	
	let maxValue = arr[0];
	let minValue = arr[0];
	let result = [];

	// 取出數(shù)組的最大值, 最小值
	arr.forEach(num => {
		maxValue = num > maxValue ? num : maxValue;
		minValue = num > minValue ? minValue : num;
	});

	// 初始化桶的數(shù)量
	const bucketCount = Math.floor((maxValue - minValue)/bucketSize) + 1; // 桶的數(shù)量
	// 初始化桶的容器
	// 注意這里的js語法，不能直接fill([])，因為生成的二維下標數(shù)組，是同一個地址
	const buckets = new Array(bucketCount).fill(0).map(() => []);

	// 將數(shù)字按照映射的規(guī)則，放入桶中
	arr.forEach(num => {
		const bucketIndex = Math.floor((num - minValue)/bucketSize);
		buckets[bucketIndex].push(num);
	});

	// 遍歷每個桶內(nèi)存儲的數(shù)字
	buckets.forEach(store => {
		// 桶內(nèi)只有1個數(shù)字或者空桶，或者都是重復數(shù)字，則直接合并到結果中
		if(store.length <= 1 || bucketSize == 1){
			result = result.concat(store);
			return;
		}

		// 遞歸，將桶內(nèi)的數(shù)字，再進行一次劃分到不同的桶中
		const subSize = Math.floor(bucketSize/2); // 減少桶內(nèi)的數(shù)字區(qū)間，但必須是最少為1
		const tmp = bucketSort(store, subSize <= 1 ? 1: subSize);
		result = result.concat(tmp);
	});

	return result;
}

基數(shù)排序

概述

基數(shù)排序，一般是從右到左，對進制位上的數(shù)字進行比較，存入[0, 9]的10個桶中，進行排序。
從低位開始比較，逐位進行比較，讓每個進制位（個、十、百、千、萬）上的數(shù)字，都能放入對應的桶中，形成局部有序。

為什么10個桶？

因為十進制數(shù)，是由0-9數(shù)字組成，對應的進制位上的數(shù)字，都會落在這個區(qū)間內(nèi)，所以是10個桶。

基數(shù)排序有兩種方式：

• MSD 從高位開始進行排序

• LSD 從低位開始進行排序

效果圖

解法

當前解法，只適用正整數(shù)的場景。
負數(shù)場景，需要加上偏移量解決。可參考 計數(shù)排序 的解法。

function radixSort(arr){
	let maxNum = arr[0];

	// 求出最大的數(shù)字，用于確定最大進制位
	arr.forEach(num => {
		if(num > maxNum){
			maxNum = num;
		}
	});

	// 獲取最大數(shù)字有幾位
	let maxDigitNum = 0;
	while(maxNum > 0){
		maxNum = Math.floor(maxNum / 10);
		maxDigitNum++;
	}

	// 對每個進制位上的數(shù)進行排序
	for(let i = 0; i < maxDigitNum; i++){
		let buckets = new Array(10).fill(0).map(() => []); // 初始化10個桶
		for(let k = 0; k < arr.length; k++){
			const bucketIndex = getDigitNum(arr[k], i); // 獲取當前進制位上的數(shù)字
			buckets[bucketIndex].push(arr[k]); // 排序的數(shù)字放入對應桶中
		}
		// 所有數(shù)字放入桶中后，現(xiàn)從0-9的順序將桶中的數(shù)字取出
		const res = [];
		buckets.forEach(store => {
			store.forEach(num => {
				res.push(num); // 注意這里，先存入桶中的數(shù)字，先取出，這樣才能保持局部有序
			})
		});
		
		arr = res;
	}


	return arr;


	/** 
		求出數(shù)字每個進制位上的數(shù)字，只支持正整數(shù)
		@param num 整數(shù)
		@param digit 位數(shù)，從0開始
	*/
	function getDigitNum(num, digit){
		return Math.floor(num / Math.pow(10, digit) % 10)
	}
}

算法復雜度

讀到這里，這篇“JavaScript如何實現(xiàn)十大排序算法”文章已經(jīng)介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內(nèi)容的文章，歡迎關注億速云行業(yè)資訊頻道。