前端对普通数字数组排序示例

1. arr.sort(fn)

// 升序排序
    arr.sort((a, b) => a - b);
 
// 降序排序
    arr.sort((a, b) => b - a);

2. 冒泡排序

冒泡排序-升序原理:

eg: [1, 6, 7, 9, 10, 3, 4, 5, 2]

1) 先遍历第一遍数组, 前一个数字大于后一个数字, 就交换位置, 最后最大值10放在数组的最后, 此时是 [1, 6, 7, 9, 3, 4, 5, 2, 10];

for (let j = 0; j < arr.length-1; j++) {
            preNum = arr[j];
            const nextNum = arr[j + 1];
            if (preNum > nextNum) { // 左边的数字大于右边的数字,交换位置
                // 数字小的往前挪, 数字大的往后挪
                arr[j] = nextNum;
                arr[j + 1] = preNum;
            }
        }

2) 第二遍就是: 前一个数字大于后一个数字, 就交换位置, 最后第二大的值放在数组的倒数第二位, 此时是 [1, 6, 7, 3, 4, 5, 2, 9, 10];

for (let j = 0; j < arr.length-2; j++) {
            preNum = arr[j];
            const nextNum = arr[j + 1];
            if (preNum > nextNum) { // 左边的数字大于右边的数字,交换位置
                // 数字小的往前挪, 数字大的往后挪
                arr[j] = nextNum;
                arr[j + 1] = preNum;
            }
        }

3) 第三遍就是: 前一个数字大于后一个数字, 就交换位置, 最后第三大的值放在数组的倒数第三位, 此时是 [1, 6, 3, 4, 5, 2, 7, 9, 10];

for (let j = 0; j < arr.length-3; j++) {...}

以此类推...

4) 最后一遍: 前一个数字大于后一个数字, 就交换位置, 最后第2小的值放在数组的第2位, 此时是 [1, 2, 3, 4, 5, 6, 7, 9, 10]

for (let j = 0; j < 1; j++) {...}

5) 因为for (let j = 0; j < x; j++) {...}; 推导可知x的值范围是(0, arr.length-1];

所以:

for (let j = arr.length - 1; i > 0; i--) {

        for (let j = 0; j < i; j++) {...}

}



排序.js:14 第1次计算:

1. (9) [1, 6, 7, 9, 3, 4, 5, 2, 10]

排序.js:14 第2次计算:

1. (9) [1, 6, 7, 3, 4, 5, 2, 9, 10]

排序.js:14 第3次计算:

1. (9) [1, 6, 3, 4, 5, 2, 7, 9, 10]

排序.js:14 第4次计算:

1. (9) [1, 3, 4, 5, 2, 6, 7, 9, 10]

排序.js:14 第5次计算:

1. (9) [1, 3, 4, 2, 5, 6, 7, 9, 10]

排序.js:14 第6次计算:

1. (9) [1, 3, 2, 4, 5, 6, 7, 9, 10]

排序.js:14 第7次计算:

1. (9) [1, 2, 3, 4, 5, 6, 7, 9, 10]

排序.js:14 第8次计算:

1. (9) [1, 2, 3, 4, 5, 6, 7, 9, 10]

最后一次不用计算了, 最小值就是1

[1, 2, 3, 4, 5, 6, 7, 9, 10]

冒泡排序--普通双层遍历循环版本:

// 冒泡排序-升序
const bubleSort = (arr) => {
    let preNum = null;
    // 之所以i>0, 因为排序交互位置到最后两个的时候, 只需要比较一次就行了, 最后那个数字不必比较了
    for (let i = arr.length - 1; i > 0; i--) {
        for (let j = 0; j < i; j++) {
            preNum = arr[j];
            const nextNum = arr[j + 1];
            if (preNum > nextNum) { // 左边的数字大于右边的数字,交换位置
                // 数字小的往前挪, 数字大的往后挪
                arr[j] = nextNum;
                arr[j + 1] = preNum;
            }
        }
    }
    return arr;
}
 
// 冒泡排序-降序
const bubleSort = (arr) => {
    let preNum = null;
    // 之所以i>0, 因为排序交互位置到最后两个的时候, 只需要比较一次就行了, 最后那个数字不必比较了
    for (let i = arr.length - 1; i > 0; i--) {
        for (let j = 0; j < i; j++) {
            preNum = arr[j];
            const nextNum = arr[j + 1];
            if (preNum < nextNum) { // 左边的数字小于右边的数字,交换位置
                // 数字大的往前挪, 数字小的往后挪
                arr[j] = nextNum;
                arr[j + 1] = preNum;
            }
        }
    }
    return arr;
}

冒泡排序-升序-递归

// 冒泡排序-升序
const bubleSort0 = (arr, i = arr.length - 1) => {
    let preNum = null;
    // 之所以i>0, 因为排序交互位置到最后两个的时候, 只需要比较一次就行了, 最后那个数字不必比较了
    for (let j = 0; j < i; j++) {
        preNum = arr[j];
        const nextNum = arr[j + 1];
        if (preNum > nextNum) { // 左边的数字大于右边的数字,交换位置
            // 数字小的往前挪, 数字大的往后挪
            arr[j] = nextNum;
            arr[j + 1] = preNum;
        }
    }
    i--;
    if (i > 0) return bubleSort0(arr, i);
    return arr
}
 
// 冒泡(升序排序)
var arr = bubleSort0([1, 6, 7, 9, 10, 3, 4, 5, 2])
console.log(arr, '冒泡排序-升序-递归');
 
 
// 冒泡排序-降序
const bubleSort0 = (arr, i = arr.length - 1) => {
    let preNum = null;
    // 之所以i>0, 因为排序交互位置到最后两个的时候, 只需要比较一次就行了, 最后那个数字不必比较了
    for (let j = 0; j < i; j++) {
        preNum = arr[j];
        const nextNum = arr[j + 1];
        if (preNum < nextNum) { // 左边的数字小于右边的数字,交换位置
            // 数字大的往前挪, 数字小的往后挪
            arr[j] = nextNum;
            arr[j + 1] = preNum;
        }
    }
    i--;
    if (i > 0) return bubleSort0(arr, i);
    return arr
}
 
// 冒泡(降序排序)
var arr = bubleSort0([1, 6, 7, 9, 10, 3, 4, 5, 2])
console.log(arr, '冒泡排序-升序-递归');

3.  选择排序

eg: [6, 7, 9, 10, 3, 4, 5, 2, 1]

当i等于0时:

1) min=第一个元素6, 和数组其余的元素比较, 原本的第一位元素6在if (nextNum < preNum){...}中6和第一个比6小的元素3交换了位置,此时是[3, 7, 9, 10, 6, 4, 5, 2, 1];

2) min变成3,  比3小的第一个元素是2, 此时是[2, 7, 9, 10, 6, 4, 5, 3, 1];

3) min变成2, 比2小的元素是1, 所以交换位置, 此时是[1, 7, 9, 10, 6, 4, 5, 3, 2];

5) 往右数没有比1小的元素了, 结束

当i等于1时:

1)  min=数组第二个元素7, 和第三个及之后的元素比较, 第一个比7小的元素是6, 交换位置, 此时是: [1, 6, 9, 10, 7, 4, 5, 3, 2];

2) min变成6, 比6小的第一个元素是4, 此时是[1, 4, 9, 10, 7, 6, 5, 3, 2];

3) min变成4, 比4小的第一个元素是3, 此时是[1, 3, 9, 10, 7, 6, 5, 4, 2];

4) min变成3, 比3小的第一个元素是2, 此时是[1, 2, 9, 10, 7, 6, 5, 4, 3];

5) 往右数没有比2小的元素了, 结束

当i等于2时:

1) min等于数组第三个元素9, 和第四个及之后的元素比较, 第一个比9小的元素是7, 此时是[1, 2, 7, 10, 9, 6, 5, 4, 3];

2) min变成7, 比7小的第一个元素是6, 此时是[1, 2, 6, 10, 9, 7, 5, 4, 3];

3) min变成6, 比7小的第一个元素是5, 此时是[1, 2, 5, 10, 9, 7, 6, 4, 3];

4) min变成5, 比7小的第一个元素是4, 此时是[1, 2, 4, 10, 9, 7, 6, 5, 3];

5) min变成4, 比4小的第一个元素是3, 此时是[1, 2, 3, 10, 9, 7, 6, 5, 4];

5) 往右数没有比3小的元素了, 结束

以此类推...

所以:

// 小的越来越靠左, 以此类推

/**

* 选择排序:

原理: 给每个位置选择当前元素最小的;

* 比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，

* 直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。

* 选择排序的本质: 每一次大循环就是选出最小的那个值，在选最小值的过程你可以通过下标记录

* 也可以每次交换值都可以

*/

选择排序-双层遍历版本:

// 选择排序-升序
const selectSort = arr => {
    const len = arr.length;
    for (let i = 0; i < len; i++) {
        let min = arr[i];
        for (let j = i + 1; j < len; j++) {
            const nextNum = arr[j];
            const preNum = min;
            // 如果当前的值比记录的最小值还要小, 就交换这2个数字的位置
            if (nextNum < preNum) {
                arr[j] = preNum;
                min = nextNum; // min被赋值为比较出来的较小值
                continue;
            }
        }
        arr[i] = min; // 因为min在内循环被修改了, 所以arr[i]的值应该在跳出内循环后在它自身循环体被修改
    }
    return arr
}
 
// 选择(升序排序)
var arr = selectSort([6, 7, 9, 10, 3, 4, 5, 2, 1])
console.log(arr, '选择排序-升序');

选择排序-递归+for循环

// 选择排序
const selectSort0 = (arr, i=0) => {
    const len = arr.length;
        let min = arr[i];
        for (let j = i + 1; j < len; j++) {
            const nextNum = arr[j];
            const preNum = min;
            console.log(preNum, 'preNum=====')
            // 如果当前的值比记录的最小值还要小, 就交换这2个数字的位置
            if (nextNum < preNum) {
                arr[j] = preNum;
                min = nextNum; // min被赋值为比较出来的较小值
                continue;
            }
        }
        arr[i] = min; // 因为min在内循环被修改了, 所以arr[i]的值应该在跳出内循环后在它自身循环体被修改
    i++;
    if(i<=2) selectSort0(arr, i);
    return arr
}
 
// 选择(升序排序)
var arr = selectSort0([6, 7, 9, 10, 3, 4, 5, 2, 1])
console.log(arr, '选择排序-升序00000');

4. 快速排序:

如果数组的元素个数小于2个, 返回原数组;

如果数组元素个数大于等于2个:

1) flag = 一个标尺元素(一般是第一个元素); left=flag左边的元素组成的数组(初始化); right=flag右边的元素组成的数组(初始化);

2) 遍历arr, 比flag小的push进left数组, 比flag大的push进right数组

3) 将left和right数组执行上述(1)和(2)步骤

4) 使用concat拼接left数组, flag, right数组

快速排序-for循环+递归+concat

// 快速排序
const quickSort = (arr) => {
    const len = arr.length;
    if (len < 2) {
        return arr;
    }
    // 选择标尺元素
    let flag = arr[0];
    let left = [];
    let right = [];
    let preNum = null;
    // 因为flag取的是下标0的元素, 所以遍历从下标1开始
    for (let i = 1; i < len; i++) {
        preNum = arr[i];
        if (preNum < flag) {
            // 比flag小的放左边
            left.push(preNum);
        }
        else {
            // 比flag大的放右边
            right.push(preNum);
        }
    }
    // 进行递归
    return quickSort(left).concat(flag, quickSort(right));
}

快速排序-划分交换in-place

// 快速排列in-place(交换)--划分交换排序:
const quickInPlaceSort = (arr) => {
    // 数组指定两个位置进行值交换
    let exchange = (arr, i, j) => {
        const preNum = arr[i];
        const nextNum = arr[j];
        arr[i] = nextNum;
        arr[j] = preNum;
    }
    // 完成一次划分交换
    let findCenter = (arr, leftIdx, rightIdx) => {
        let flag = arr[leftIdx];
        let centerIdx = leftIdx + 1;
        for (let i = centerIdx; i <= rightIdx; i++) {
            if (arr[i] < flag) {
                exchange(arr, centerIdx, i); // 交换位置
                centerIdx++; // 交换的下标+1
            }
        }
        exchange(arr, leftIdx, centerIdx - 1);
        return centerIdx;
    }
    // 递归排序
    let sort = (arr, leftIdx, rightIdx) => {
        if (leftIdx < rightIdx) {
            let center = findCenter(arr, leftIdx, rightIdx);
            sort(arr, leftIdx, center - 1);
            sort(arr, center, rightIdx);
        }
    }
    sort(arr, 0, arr.length - 1);
    return arr;
}
var arr = quickInPlaceSort([1, 6, 7, 9, 10, 3, 4, 5, 2]);
console.log(arr, '快速排序-升序-划分交换'); // [1, 2, 3, 4, 5, 6, 7, 9, 10] '快速排序-升序-划分交换'
console.log('-----------------------------------------');