Исследование внутреннего принципа метода сортировки нативного массива JS sort()

JavaScript

Метод sort() сортирует исходный массив без создания копии (то есть он изменит исходный массив)

Использовать без параметров

В настоящее время метод сортировки заключается в сортировке по коду ascii, который сначала преобразует все элементы массива в строки (не затрагивая исходное значение), что удобно для сравнения.

let arr = [23, 12, 32, 5, 21, 7, 1]
    
arr.sort()
//此时原数组已经被改变
console.log(arr)

распечатать результат

Использовать с параметрами

Сначала посмотрите на определение, данное w3school.

О чем говорит эта ТМ? ? На что ссылается? что значит б? Как сортировка реализована внутри? ? Нижеследующее является предметом нашего исследования.
Во-первых, давайте посмотрим, что именно означает a

let arr = [23, 12, 32, 5, 21, 7, 1]

console.log(arr)
arr.sort((a, b) => {
    console.log("a:" + a)
    return 1
})
console.log(arr)

распечатать результат

Легко видеть, что диапазон a равен[arr[1],arr[arr.length-1]](Чтобы избежать случайностей, я также провел много других тестов, поэтому я не буду перечислять их все здесь)
Кроме того, мы также можем видеть, что когда функция возвращает положительное значение, массив не изменяется (также изменяется 0, что здесь не показано).

Далее, позвольте мне посмотреть, что означает b

let arr = [23, 12, 32, 5, 21, 7, 1]

console.log(arr)
arr.sort((a, b) => {
    console.log("b:" + b)
    return -1
})
console.log(arr)

распечатать результат

диапазон b[arr[0],arr[arr.length-2]Кроме того, здесь мы также подбираем метод для изменения порядка массива (другой — это метод массива).reverse()метод) Диапазон a и b просто определяется нами, но не так просто, когда он фактически отсортирован.Давайте посмотрим.

let arr = [23, 12, 32, 5, 21, 7, 1]

console.log(arr)
arr.sort((a, b) => {
    console.log("b:" + b)
    console.log("a:" + a)
    return a - b
})
console.log(arr)

распечатать результат

Удивлен или нет, удивлен или нет? ?
Не паникуйте, давайте сначала отсортируем данные

На данный момент мне интересно, есть ли вероятность того, что sort() внутреннеСортировка вставками, так что я начал свою проверку

Здесь мы доказываем, что sort() использует внутри себя дихотомическую сортировку вставками, но я сказал в Интернете, что если размер массива превышает 10, будет использоваться метод быстрой сортировки. этот вывод

Затем сравните производительность сортировки сортировки и других видов сортировки.
sort()

let arr = []
for(let i = 0 ; i < 100000 ; i++){
    arr.push(parseInt(Math.random() * 10000))
}
//performance.now()H5的一个新的api，效果相当于Date.now()，不过它更强大
let startTime = performance.now()
arr.sort((a, b) => {
    return a - b
})
let endTime = performance.now()

console.log(endTime - startTime)

Значение колеблется, здесь я получаю режим, и заинтересованные друзья могут проверить его самостоятельно.

Быстрый ряд

function quickSort(arr) {
    var len = arr.length;
    //结束递归的条件
    if (len <= 1) return arr;
    var left = [];
    var right = [];
    //中间基数
    var midindex = Math.floor(len / 2);
    var mid = arr[midindex];
    for (var i = 0; i < len; i++) {
        if (arr[i] == mid) continue;
        else if (arr[i] < mid) left.push(arr[i]);
        else right.push(arr[i]);
    }
    return quickSort(left).concat([mid], quickSort(right));
}

let arr = []
for(let i = 0 ; i < 100000 ; i++){
    arr.push(parseInt(Math.random() * 10000))
}

let startTime = performance.now()
quickSort(arr)
let endTime = performance.now()

console.log(endTime - startTime)

Сортировка вставками

function insertSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len; i++) {
        var k = i;
        //前提： 1  前面必须有内容
        //前提： 2  当前这个元素，比左边小，交换1次
        while (k - 1 >= 0 && arr[k] < arr[k - 1]) {
            var temp = arr[k];
            arr[k] = arr[k - 1];
            arr[k - 1] = temp;
            k--;
        }
    }
    return arr;
}

let arr = []
for(let i = 0 ; i < 100000 ; i++){
    arr.push(parseInt(Math.random() * 10000))
}

let startTime = performance.now()
insertSort(arr)
let endTime = performance.now()

console.log(endTime - startTime)

Пузырьковая сортировка

 let arr = []
for(let i = 0 ; i < 100000 ; i++){
    arr.push(parseInt(Math.random() * 10000))
}

function bubbleSort(arr) {
    var len = arr.length - 1;//循环次数
    for (var j = len; j > 0; j--) {
        //比较 交换
        for (var i = 0; i < j; i++) {
            if (arr[i] > arr[i + 1]) {
                var tamp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = tamp;
            }
        }
    }
    return arr;
    }
let startTime = performance.now()
bubbleSort(arr)
let endTime = performance.now()

console.log(endTime - startTime)

Суммировать

  1. sort()Когда метод не имеет параметров, он сортируется по коду ascii.
  2. Даваяsort()Возврат отрицательного значения для аргумента может реализовать массивreverse()Эффект
  3. sort(next,prev)возврат параметраnext - prev, массив в порядке возрастания, возврат-(next - prev)которыйprev - next, массив в порядке убывания
  4. Из приведенного выше сравнения мы видим, чтоsort()Метод достаточно эффективен и может быть использован непосредственно
  5. В общем, сортировка массива с помощью быстрой сортировки илиsort(), другие методы сортировки рассматриваются только тогда, когда известны правила данных
Категории