关于前端:JavaScript基础-数组排序的6种方法

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 5console.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]不同的办法比拟计算次数。