总结数组排序的方法,方便日后查阅。
1. sort()
sort() 按照 ASCII 字符排序,默认升序。
普通数组
// 数字 var sum = 0; var numbers = [4, 2, 5, 1, 3]; numbers.sort(function(a, b) { sum++; return a - b; }); console.log(numbers); // 1 2 3 4 5 console.log(sum); // 7 // 字符串 const months = ['March', 'Jan', 'Feb', 'Dec']; months.sort(); console.log(months); // ['Dec', 'Feb', 'Jan', 'March']
数组对象
var student = [ {'name': 'jack', 'age': 18}, {'name': 'apple', 'age': 16}, {'name': 'tony', 'age': 30}, {'name': 'marry', 'age': 8}, ] // 按年龄 student.sort(function (a, b) { return (a.age - b.age) }); // 按姓名 student.sort(function (a, b) { var nameA = a.name.toUpperCase(); var nameB = b.name.toUpperCase(); if (nameA < nameB) { return -1; } if (nameA > nameB) { return 1; } });
2. 冒泡排序
相邻两个数逐个比较,如果前一个数比后一个数小则交换位置。
重点:交换过程需要变量存储较小值/较大值
var numbers = [4, 2, 5, 1, 3]; var sum = 0; function bubbleSort (arr) { let temp = ''; for (let i = 0; i < arr.length; i++) { for (let j = 0; j < arr.length - 1; j++) { if (arr[j] > arr[j + 1]) { temp = arr[j + 1]; arr[j + 1] = arr[j]; arr[j] = temp; } sum++; } } return arr; }; console.log(bubbleSort(numbers)); console.log(sum) // 20
3. 快速排序
冒泡排序的改进算法。通过多次的比较和交换来实现排序。
重点:需设定分界值,根据分界值将数组分为左右两部分。然后在左右两边不断重复取分界值和分左右部分的操作。
var numbers = [4, 2, 5, 1, 3]; var sum = 0; function quickSort (arr) { if (arr.length <= 1) { return arr; } var medianIndex = Math.floor(arr.length / 2); // 分解值索引 var medianValue = arr.splice(medianIndex, 1); // 分界值 var left = []; var right = []; for (let i = 0; i < arr.length; i++) { if (arr[i] < medianValue) { left.push(arr[i]) } else { right.push(arr[i]) } sum++; } console.log(medianIndex, medianValue, left, right) return quickSort(left).concat(medianValue,quickSort(right)); }; console.log(quickSort(numbers)); console.log(sum) // 10
4. 插入排序
假设前面 n-1 的元素已经排好序,将第n个元素插入到前面已经排好的序列中。
重点:需定义有序序列中最后一个位置,从最后一位开始不断和序列前元素进行比较,直到找到插入位置。
var numbers = [4, 2, 5, 1, 3]; var sum = 0; function insertSort(arr) { // 假设第一个元素已经排好序 for (let i = 1; i < arr.length; i++) { if (arr[i] < arr[i - 1]) { // 取出无序序列中需要插入的第i个元素 var temp = arr[i]; // 定义有序中的最后一个位置 var j = i - 1; arr[i] = arr[j]; // 根据序列最后一位,不断循环比较,找到插入的位置 while(j >= 0 && temp < arr[j]){ arr[ j+1 ] = arr[j]; j--; sum++; }; //插入 arr[ j+1 ] = temp; } } } console.log(insertSort(numbers)); console.log(sum) // 6
5. 希尔排序
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序。
希尔排序是插入排序算法的一种更高效的改进版本。
var numbers = [4, 2, 5, 1, 3]; var sum = 0; function shellSort(arr) { var len = arr.length; // 定义间隔区间 var fraction = Math.floor(len / 2); // fraction = Math.floor(fraction / 2) => 循环中不断切割区间 for (fraction; fraction > 0; fraction = Math.floor(fraction / 2)) { // 以间隔值开始遍历 for (var i = fraction; i < len; i++) { // 如果前面一个大于后面一个 for (var j = i - fraction; j >= 0 && arr[j] > arr[fraction + j]; j -= fraction) { var temp = arr[j]; arr[j] = arr[fraction + j]; // 后移 arr[fraction + j] = temp; // 填补 sum++; } } } } console.log(shellSort(numbers)); console.log(sum) // 6
6. 选择排序
从待排序的数据元素中选出最小/最大的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小/最大元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。
var numbers = [4, 2, 5, 1, 3]; var sum = 0; function selectionSort(arr) { if (arr == null || arr.length < 2) { return arr; } for (var i = 0; i < (arr.length - 1); i++) { let minIndex = i; for (let j = i + 1; j < arr.length; j++) { minIndex = arr[j] < arr[minIndex] ? j : minIndex; sum++; } let temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } return arr; } console.log(selectionSort(numbers)); console.log(sum) // 10
7. 比较
以同一个数组[4, 2, 5, 1, 3]
不同的方法比较计算次数。
方法 | 计算次数 | 稳定性 |
---|---|---|
sort() | 7 | |
冒泡排序 | 20 | 稳定 |
快速排序 | 10 | 不稳定 |
插入排序 | 6 | 稳定 |
希尔排序 | 6 | 不稳定 |
选择排序 | 10 | 不稳定 |