首页 > itarticle > 常见排序

常见排序

admin 10月 28, 2020 0

冒泡排序

基本思想：在每一轮中，都确定一个数的位置。对于n个数，需要n次循环，每次比较n-i次(i为第几次循环)。

function (arr) {
    const len = arr.length;
    if(len <= 1) return;
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len - i - 1; j++) {
            const pre = arr[j];
            const next = arr[j + 1];
            if (pre > next) {
                let _p = pre;
                arr[j] = next;
                arr[j + 1] = _p;
            }
        }
    }
}
const arr = [5, 3, 9, 11, 1, 23];

快速排序

思路：选定一个数组的右边界作为基准元素。storeIndex从数组左边界开始，i也从左边界开始。当index为i的元素小于基准元素时，交换i和storeIndex位置的元素。当i到完成循环后，交换基准元素和storeIndex所在的元素，然后，对被storeIndex分割的两个数组进行递归操作。

function quickSort(arr, left, right) {
    const len = arr.length;
    if (left >= right) return;
    let base = arr[right];
    let storeIndex = left;
    let i = left;
    while(i < right - left) {
        if(arr[i] < base) {
            swap(arr, i, storeIndex++);
        }
        i++;
    }
    swap(arr, storeIndex, right);
    quickSort(arr, left, storeIndex - 1);
    quickSort(arr, storeIndex + 1, right);
}

function swap(arr, j, k) {
    if(j === k) return;
    const temp = arr[j];
    arr[j] = arr[k];
    arr[k] = temp;
}