"Алгоритмы и структуры данных" разобраться 6 алгоритмов сортировки

алгоритм JavaScript
"Алгоритмы и структуры данных" разобраться 6 алгоритмов сортировки

предисловие

Алгоритмов сортировки в этот раз я разобрала 6. От освоения идеи до ее воплощения я еще очень много времени потратила на рисование, и разбирала по заметкам, только разбирала, а эффект будет привлекать других.

Общие алгоритмы сортировки в 6 имеют GIF-анимацию, которая помогает вам понять идеи сортировки.

Кодовая точка здесь github

фотография недействительнаЩелкните здесь, чтобы прочитать эту статью

6 видов следующие👇

  • Пузырьковая сортировка
  • сортировка по подсчету
  • быстрая сортировка
  • Сортировка слиянием
  • Сортировка вставки
  • сортировка выбором

Временная сложность следующая👇

排序算法复杂度分析
Анализ сложности алгоритма сортировки

Следующий анимированный GIF взят изЧжиху красивый

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

Происхождение имени похоже на пузырь浮Встаньте, решитесь, то есть каждый раз сравнивайте размер двух соседних элементов, а потом потихоньку "вплывайте" вверх, я просто прикалываюсь, видите идею.

"Временная сложность O (n * n)"

идеи

  1. При сравнении соседних элементов, если первый больше второго, они меняются местами.
  2. Сделайте то же самое для каждой пары соседних элементов, начиная с первой пары до последней пары, чтобы последний элемент был самым большим элементом.
  3. Повторите вышеуказанные шаги для N элементов, каждый цикл окончательный отрицательный ток.
  4. Повторяйте шаги 1–3, пока сортировка не будет завершена.

анимация

冒泡排序
Пузырьковая сортировка

Код 

// 最外层循环控制的内容是循环次数
// 每一次比较的内容都是相邻两者之间的大小关系
let BubbleSort = function (arr, flag = 0) {
    let len = arr.length

    for (let i = 0; i < len - 1; i++) {
        for (let j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
            }
        }
    }
    return flag ? arr.reverse() : arr
}

let arr = [2, 9, 6, 7, 4, 3, 1, 7]
console.log(BubbleSort(arr, 1))

сортировка по подсчету

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

Данные массива должны быть целыми числами, а разница между максимальным и минимальным значениями не должна быть слишком большой."Если данные отрицательные, реализованное мной решение оптимизировано для этого".

"Временная сложность: O(n+k)"

идеи

1. Вычислить разницу d, минимальное значение которой меньше 0, плюс собственное сложение

2. Создайте статистический массив и подсчитайте количество соответствующих элементов

3. Статистический массив преобразуется, и следующие элементы равны сумме предыдущих элементов, то есть ранжирующий массив

4. Пройдите исходный массив, найдите правильную позицию в массиве статистики и выведите в массив результатов.

анимация

计数排序
сортировка по подсчету

Код 

// 计数排序
let countingSort = function(arr, flag = 0) {
    let min = arr[0],
        max = arr[0],
        len = arr.length;
    // 求最大最小值
    for(let i = 0; i < len; i++) {
        max = Math.max(arr[i], max)
        min = Math.min(arr[i], min)
    }
    // 1.计算出差值d,最小值小于0,加上本身add

    let d =  max - min,
        add = min < 0 ? -min : 0;
    //2.创建统计数组并统计对应元素个数    
    let countArray  = new Array(d+1+add).fill(0)
    for(let i = 0; i < len; i++){
        let demp = arr[i]- min + add
        countArray[ demp ] += 1 
    }
    
    //3.统计数组做变形，后面的元素等于前面的元素之和,也就是排名数组
    let sum = 0;

    // 这里需要遍历的是countArray数组长度
    for(let i = 0; i < d+1+add; i++){
        sum += countArray[i]
        countArray[i] = sum;
    }
    let res = new Array(len)
    4.遍历原始数组,从统计数组中找到正确位置,输出到结果数组
    for(let i = 0; i < len; i++){
        let demp = arr[i] -min + add
        res[ countArray[demp] -1 ] = arr[i]
        countArray[demp] --;
    }
    return flag ? res.reverse() : res
}

let arr = [2, 9, 6, 7, 4, 3, 1, 7,0,-1,-2]
console.log(countingSort(arr))

быстрая сортировка

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

"Временная сложность: O(nlogn)"

идеи

  1. В качестве основания выберите среднее число массива и возьмите это основание из массива
  2. Подготовить два массива контейнеров, через массив, один по сравнению с основанием, слева поставить малый контейнер, справа поставить большой контейнер;
  3. Рекурсивно обрабатывает элементы двух контейнеров и объединяет обработанные данные с базой в массив, возвращает.

анимация

快速排序
быстрая сортировка

Код 

let quickSort = function (arr) {
    // 递归出口就是数组长度为1
    if (arr.length <= 1) return arr
    //获取中间值的索引，使用Math.floor向下取整；
    let index = Math.floor(arr.length / 2)
    // 使用splice截取中间值，第一个参数为截取的索引，第二个参数为截取的长度；
    // 如果此处使用pivot=arr[index]; 那么将会出现无限递归的错误；
    // splice影响原数组
    let pivot = arr.splice(index, 1)[0],
        left = [],
        right = [];
    console.log(pivot)
    console.log(arr)
    for (let i = 0; i < arr.length; i++) {
        if (pivot > arr[i]) {
            left.push(arr[i])
        } else {
            right.push(arr[i])
        }
    }
    return quickSort(left).concat([pivot], quickSort(right));
}

//let arr = [2, 9, 6, 7, 4, 3, 1, 7]
// console.log(quickSort(arr))

Сортировка слиянием

Объединение двух упорядоченных последовательностей в одну упорядоченную последовательность называется «слиянием».

Основная идея процесса: количество рекурсивной декомпозиции первого столбца, а затем объединение количества столбцов (типичные идеи разделения приложения)

"Временная сложность: O (nlog (n))"

идеи

  1. Разделите массив на две группы, A и B, и продолжайте разбивать две группы, пока в каждой группе не останется только один элемент.
  2. Группы постепенно объединяются в соответствии с процессом разбиения.Поскольку каждая группа изначально имеет только один элемент, это можно рассматривать как порядок внутри группы, а слияние группы можно рассматривать как процесс слияния двух упорядоченных массивов.
  3. Повторите второй шаг в левом и правом десятичных колонках, пока не будет всего не только 1 номер.

анимация

归并排序
Сортировка слиянием

Код 

const merge = (left, right) => { // 合并数组

    let result = []
    // 使用shift()方法偷个懒,删除第一个元素,并且返回该值
    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift())
        } else {
            result.push(right.shift())
        }
    }
    while (left.length) {
        result.push(left.shift())
    }

    while (right.length) {
        result.push(right.shift())
    }
    return result
}

let mergeSort = function (arr) {
    if (arr.length <= 1)
        return arr
    let mid = Math.floor(arr.length / 2)
    // 拆分数组
    let left = arr.slice(0, mid),
        right = arr.slice(mid);
    let mergeLeftArray = mergeSort(left),
        mergeRightArray = mergeSort(right)
    return merge(mergeLeftArray, mergeRightArray)
}

let arr = [2, 9, 6, 7, 4, 3, 1, 7, 0, -1, -2]
console.log(mergeSort(arr))

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

Как следует из названия: создав упорядоченную последовательность, для несортированных данных просканируйте отсортированную последовательность сзади вперед, найдите соответствующую позицию и вставьте.

"Временная сложность: O(n*n)"

идеи

  1. Начиная с первого элемента, элемент можно считать отсортированным;
  2. Возьмите следующий элемент и просканируйте его от начала до конца в последовательности отсортированных элементов;
  3. Если элемент (отсортированный) больше нового элемента, переместите элемент на следующую позицию;
  4. Повторяйте шаг 3, пока не найдете позицию, в которой отсортированный элемент меньше или равен новому элементу;
  5. Повторите шаги 2–5.

анимация

插入排序
Сортировка вставками

Код 

let insertionSort = function (arr) {
    let len = arr.length

    for (let i = 0; i < len; i++) {
        let preIndex = i - 1,
            cur = arr[i];
        while (preIndex >= 0 && arr[preIndex] > cur) {
            arr[preIndex + 1] = arr[preIndex]
            preIndex--;
        }
        arr[preIndex + 1] = cur
    }
    return arr
}


let arr = [2, 9, 6, 7, 4, 3, 1, 7, 0, -1, -2]
console.log(insertionSort(arr))

сортировка выбором

Идея: выбирать самый большой (самый маленький) элемент из элементов массива, который будет сортироваться как первый элемент каждый раз, пока строка не будет исчерпана

"Временная сложность O (n * n)"

идеи

  1. Есть n чисел, которые нужно отсортировать n-1 раз.
  2. Минимальное значение выбирается впервые и ставится первым
  3. Выберите минимальное значение во второй раз и поставьте его на второе место
  4. ...повторить процесс
  5. Выберите минимальное значение для n-1-го раза и поместите его в n-1-ю позицию

анимация

选择排序
сортировка выбором

Код 

let selectSort = function (arr, flag = 0) {
    let len = arr.length,
        temp = 0;

    // 一共需要排序len-1次
    for (let i = 0; i < len - 1; i++) {
        temp = i;
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < arr[temp])
                temp = j;
        }
        // 每一趟保证第i位为最小值
        if (temp !== i) {
            [arr[i], arr[temp]] = [arr[temp], arr[i]]
        }
    }

    return flag ? arr.reverse() : arr
}



let arr = [2, 9, 6, 7, 4, 3, 1, 7, 0, -1, -2]
console.log(selectSort(arr, 1))

❤️ Всем спасибо

Если вы считаете этот контент полезным:

  1. Поставьте лайк и поддержите его, чтобы больше людей увидело этот контент
  2. Вы можете поделиться со мной своими мыслями в области комментариев, и вы также можете записать свой мыслительный процесс в области комментариев.
  3. Если вы считаете, что это хорошо, вы также можете прочитать последние статьи TianTian (спасибо за вашу поддержку и поддержку 🌹🌹🌹):

Категории