手写常用排序算法

冒泡排序

在未排序区域中，从前向后不断对比相邻数据，将较大值不断向后移动，直至移动到未排序区域的最后一位。

    const arr = [2, 44, 1, 0, -22, 56, -78];
    // arr.sort((a,b)=>a-b)
    function bubbleSort(arr){
        let tmp;
        for(let i=arr.length; i>0; i--){// 较大的arr[j]会冒泡到arr的尾部
            for(let j=0; j<i-1; j++){
                if(arr[j]>arr[j+1]){// 前一个元素比或一个大，则向后冒泡(交换)
                    tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
        }
        return arr;
    }
    console.log(bubbleSort(arr));// [-78, -22, 0, 1, 2, 44, 56]

选择排序

遍历未排序区域，通过对比相邻数据，记录较小值的下标，每遍历一遍就能找出未排序区域中最小的数据，将记录的未排序区域的最小值与未排序区域的第一个元素交换位置，该位为有序，未排序区域长度减一，直至完成排序。

const arr = [2, 44, 1, 0, -22, 56, -78];
function selectionSort(arr){
	for(let i = 0;i<arr.length;i++){
		let minIndex = i; // 假设arr[i]为最小元素（即默认就是递增）
		let tmp;
		for(let j = i+1;j<arr.length;j++){ 
			if(arr[j]< arr[minIndex]){// 如果arr[j]比arr[minIndex]还小
				minIndex = j;// 更新最小元素的下标
			}
		}
		// 交换arr[i]和arr[minIndex]
		tmp = arr[i];
		arr[i] = arr[minIndex]
		arr[minIndex] = tmp
	}
}

插入排序

将第一个数据视为已排序区域，取第一个未排序区域中的数据，从它前一个位置依次向前寻找，直至找到第一个小于等于它的数据，或超出数组范围（已排序区域中没有比它小的值），则将它从未排序区域移除，插入到第一个小于等于它的位置后，或第一位。直至全部排序结束。

function insetSort(arr){
	for(let i = 1; i< arr.length;i++){
        let index = i;
        let temp = arr[i]
        while(index > 0 && arr[index - 1] > temp){
            index--
        }
        arr.splice(i,1);
        arr.splice(index,0,temp);
    }
}

归并排序

通过递归将数组不断一分为二，直至每个数组只有一个元素，这时数组即为有序的。在合并时因为两个数组都是有序的，只需比较两个有序数组中的第一个元素，将较小的放入合并后的数组中，即可合并出一个有序数组。

function mergeSort(arr){
	if(arr.length < 2){
		return arr
	}
	
	let mid = Math.floor(arr.length/2);
	let leftArr = arr.slice(0,mid);
	let rightAr  = arr.slice(mid);
	return merge(mergeSort(leftArr,mergeSort(rightArr)));
}

function merge(leftArr,rightArr){
    let res = [];
    while(leftArr.length > 0 && rightArr.length > 0){
		if(leftArr[0] < rightArr[0]){
            res.push(leftArr.shift())
        }else {
            res.push(rightArr.shift())
        }
    }
    
    if(leftArr.length !== 0){
        res.push(...leftArr)
    }
    
    if(rightArr.length !== 0){
        res.push(...rightArr)
    }
    return res
}

快速排序

从未排序区域中取一个值视为基准值（通常取最中间位置的值），将剩余数据中，小于该值的数据放入leftArr中，将大于等于该值的数据放入rightArr中，此时基准值即为有序。再不断对leftArr和rightArr分别重复该步骤，直至数组中只有一个元素（数组中只有一个元素时为有序数组），将leftArr、基准值、rightArr按顺序合并成一个数组，该数组即为有序。

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 index = i;
            let temp = arr[i];
            while(index > 0 && arr[index - gap] > temp) {
                index -=gap;
            }
            arr.splice(i, 1);
            arr.splice(index, 0, temp);
        }

    }

}

参考

https://juejin.cn/post/7127636022996762654

https://www.cnblogs.com/pangqianjin/p/14998643.html#:~:text=JavaScript%E6%89%8B%E5%86%99%E5%87%A0%E7%A7%8D%E5%B8%B8%E8%A7%81%E7%9A%84%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%EF%BC%9A%E5%86%92%E6%B3%A1%E3%80%81%E9%80%89%E6%8B%A9%E3%80%81%E6%8F%92%E5%85%A5%E3%80%81%E5%B8%8C%E5%B0%94%E3%80%81%E5%BD%92%E5%B9%B6%E3%80%81%E5%BF%AB%E6%8E%92%201%20%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F%202%20%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F%203,%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%204%20%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F%205%20%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F%206%20%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F