1. 冒泡排序
1.1 概述
- 一般用于数组的排序
- 比较相邻两个元素的大小，大的放在小的后面
1.2 原理与实现
- 需要两个for循环
- 外层循环控制比较几轮，内层循环控制每轮比较几个元素
let arr = [11,8,7,18,56,35,41,9]; for(let i = 0; i <= arr.length - 1; i++){ // 外层循环控制比较几轮 for(let j = 0; j <= arr.length- i - 1; j++){ // 内层循环控制每轮比较几个元素 if(arr[j] > arr[j+1]){ // 判断每一次比较的时候，两个数字的大小 // arr[j]是第j个元素 // arr[j+1]是第j+1 个元素 //如果j > j + 1， 把j 和j+i交换， // 也就是把相对大的值往后排序 也就是从小到大排序 //如果j < j + 1， // 把相对小的值往后排 也就是从大到小排序 let temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; // 利用第三方变量交换j 和j + 1 的值 } } } console.log(arr);
2. 二分插入排序算法
2.1 概述
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中二分查找到第一个比它大的数的位置
- 将新元素插入到该位置后
- 重复上述两步
let arr2 = [12, 7, 4, 23, 10, 35]; function insertSort(arr) { let len = arr.length; for (let i = 1; i < len; i++) { let key = arr[i]; let j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } return arr; } let newArr2 = insertSort(arr2);
休息一分钟~
3. 归并排序算法
3.1 概述
归并排序是建立在归并操作上的一种有效的排序算法
采用分治法（Divide and Conquer）的一个典型的应用
合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。 将已有序的子序列合并，得到完全有序的序列
即先使每个子序列有序，再使子序列段间有序
若将两个有序表合并成一个有序表，称为2-路归并
function merge(leftArr, rightArr) { let result = []; while (leftArr.length > 0 && rightArr.length > 0) { if (leftArr[0] < rightArr[0]) // 把最小的最先取出，放到结果集中 result.push(leftArr.shift()); else result.push(rightArr.shift()); } // 剩下的就是合并，这样就排好序了 return result.concat(leftArr).concat(rightArr); } function mergeSort(array) { if (array.length == 1) return array; let middle = Math.floor(array.length / 2); //求出中点 let left = array.slice(0, middle); //分割数组 let right = array.slice(middle); return merge(mergeSort(left), mergeSort(right)); //递归合并与排序 } let arr3 = mergeSort([30, 12, 55, 72, 66, 46]); console.log(arr3); // 12, 30, 46, 55, 66, 72
4.选择排序算法
4.1 概述
- 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
- 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
- 重复第二步，直到所有元素均排序完毕
function selectionSort(arr) { let len = arr.length; let minIndex, temp; for (let i = 0; i < len - 1; i++) { minIndex = i; for (let j = i + 1; j < len; j++) { if (arr[j] < arr[minIndex]) { // 寻找最小的数 minIndex = j; // 将最小数的索引保存 } } temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } return arr; } let arr5 = [23, 12, 4, 10, 55,34] let newArr5 = selectionSort(arr5) console.log(newArr5) // 结果 4, 10, 12, 23, 34, 55
