经典面试题：JS常见的排序算法

以你之姓@ 2022-12-13 11:29 119阅读 0赞

### 1. 冒泡排序 ###

// 冒泡排序
    // 比较两个相邻的元素，将值大的元素交换至右端
    // N个数字要排序完成，总共进行N-1趟排序
    function bubbleSort(arr) {
    	if (arr.length === 0) {
    		return []
    	}
    	for(let i = 0; i < arr.length; i++) {
    		for(let j = 0; j<arr.length; j++) {
    			if (arr[j] > arr[j+1]) {
    				let temp = arr[j]
    				arr[j] = arr[j+1]
    				arr[j+1] = temp
    			}
    		}
    	}
    	return arr
    }

### 2. 选择排序 ###

// 选择排序
    // 每一次从待排序的数据元素中选出最小的一个元素，存放在序列的开头， 以此类推
    // 第一次循环比较n-1次，第二次循环比较n-2次，依次类推，最后一个元素不需要比较，因此共进行n- 1次循环，最后一次循环比较1次。
    // 因此一共比较1+2+ ... +（n - 2）+（n - 1）次，求和得n2/2 - n/2 ，忽略系数，取最高指数项，该排序的时间复杂度为O(n2)
    function selectSort(arr) {
    	if (arr.length === 0) {
    		return []
    	}
    	let minIndex;
    	for(let i = 0; i<arr.length-1; i++) {
    		minIndex = i
    		for(let j = i+1;j<arr.length;j++) {
    			if (arr[minIndex] > arr[j]) {
    				minIndex = j // 记录最小的缩影
    			}
    		}
    		// 用找到的最小值与默认的做交换(min 与 mowMin交换, 也就是i与minIndex交换)
    		let temp = arr[i]
    		arr[i] = arr[minIndex]
    		arr[minIndex] = temp
    	}
    	return arr
    }

### 3. 插入排序 ###

// 插入排序
    // 设索引i之前的为已排过序的， 让arr[i]与之前的数据在一个个比较
    function insertSort(arr) {
    	if (arr.length === 0) {
    		return []
    	}
    	for (let i = 1; i<arr.length;i++) {
    		for(let j = 0; j < i ;j++) {
    			if (arr[j] > arr[i]) {
    				let temp = arr[j]
    				arr[j] = arr[i]
    				arr[i] = temp
    			}
    		}
    	}
    	return arr	
    }

### 4. 快速排序 ###

// 快速排序
    // 1. 从数组中选择一个元素作为基准点
    // 2. 排序数组，所有比基准值小的元素摆放在左边，而大于基准值的摆放在右边。每次分割结束以后基准值会插入到中间去。
    // 3. 最后利用递归，将摆放在左边的数组和右边的数组在进行一次上述的1和2操作。
    function quickSort(arr) {
    	if (arr.length === 0) {
    		return []
    	}
    	let midlen = Math.floor(arr.length / 2) // 取数组长一半
    	let midValue = arr.splice(midlen, 1) // 删除，并取出中间值， 相当于抠出中间值
    	let left = []
    	let right = []
    	for(let i = 0; i < arr.length; i++) {
    		if (arr[i] < midValue) {
    			left.push(arr[i])
    		} else {
    			right.push(arr[i])
    		}
    	}
    	return quickSort(left).concat(midValue, quickSort(right))
    }