Алгоритмы и структуры данных в JS — Сортировка (Sort)

внешний интерфейс алгоритм JavaScript модульный тест

Алгоритм сортировки (Sort)

введение

Двумя наиболее распространенными операциями, которые мы обычно выполняем с данными, хранящимися в компьютере, являются сортировка и поиск, Исследования по сортировке и поиску компьютеров не прекращались с момента их появления. Сегодня эпоха больших данных и облачных вычислений, и к скорости и эффективности сортировки и поиска данных предъявляются все более высокие требования, поэтому для алгоритмов сортировки и поиска необходимо проводить проектирование специальной структуры данных (например, о чем мы говорили в предыдущем статья.бинарное дерево поискаявляется одним из них), чтобы сделать наши операции с данными более краткими и эффективными.

В этой статье мы представим некоторые базовые и расширенные алгоритмы сортировки данных и реализуем их один за другим с помощью JavaScript, чтобы у каждого было базовое понимание идей и реализаций распространенных алгоритмов сортировки на компьютерах, и они играли роль в привлечении новые идеи.

Примечание об алгоритмах сортировки

Прежде чем вводить каждый алгоритм, нам нужно понять некоторые термины, которые оценивают скорость алгоритмов:

стабилизировать: Если a изначально находится перед b, когда a=b, a все еще находится перед b после сортировки.
нестабильный: если a изначально стоял перед b, когда a=b, a может появиться после b после сортировки

Сортировать по: Все операции сортировки выполняются в памяти
внешняя сортировка: Поскольку данные слишком велики, данные помещаются на диск, и сортировка может быть выполнена только через передачу данных диска и памяти.

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

Если вы хотите узнать больше о сложности времени и пространства, я рекомендую статью, пожалуйста, нажмите здесьздесь

Основной алгоритм сортировки

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

1. Пузырьковая сортировка (BubbleSort)

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

Идея алгоритма пузырьковой сортировки выглядит следующим образом (сортировка по возрастанию):

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

Ниже я беру движущуюся картинку из Интернета, чтобы показать процесс пузырьковой сортировки:

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

Конкретная реализация JS выглядит следующим образом:

//冒泡排序
function bubbleSort ( data ) {
    var temp = 0;
    for ( var i = data.length ; i > 0 ; i -- ){
        for( var j = 0 ; j < i - 1 ; j++){
           if( data[j] > data[j + 1] ){
               temp = data[j];
               data[j] = data [j+1];
               data[j+1] = temp;
           }
        }
    }
    return data;
}

Давайте сначала настроим набор данных, и мы будем использовать этот набор данных для тестирования позже:

var dataStore = [ 72 , 1 , 68 , 95 , 75 , 54 , 58 , 10 , 35 , 6 , 28 , 45 , 69 , 13 , 88 , 99 , 24 , 28 , 30 , 31 , 78 , 2 , 77 , 82 , 72 ];

console.log( '原始数据:' + dataStore );
console.log( '冒泡排序:' + bubbleSort( dataStore) );

// 原始数据:72,1,68,95,75,54,58,10,35,6,28,45,69,13,88,99,24,28,30,31,78,2,77,82,72
// 冒泡排序:1,2,6,10,13,24,28,28,30,31,35,45,54,58,68,69,72,72,75,77,78,82,88,95,99

2. Сортировка выбором (SelctionSort)

Сортировка выбором — относительно простой и интуитивно понятный алгоритм сортировки. Идея его алгоритма состоит в том, чтобы пройти от начала массива, сравнить первый элемент с другими элементами, записать наименьший элемент, а после завершения цикла поместить наименьший элемент в первую позицию массива, а затем продолжить вышеописанное. шагов, начиная со второй позиции массива. Когда достигается предпоследняя позиция в массиве, все данные сортируются.

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

Точно так же я позаимствовал движущуюся картинку из Интернета, чтобы показать процесс сортировки выбором:

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

После понимания идеи алгоритма конкретная реализация не должна быть проблемой:

//选择排序
function selectionSort( data ) {
    for( var i = 0; i< data.length ; i++){
        var min = data[i];
        var temp;
        var index = i;
        for( var j = i + 1; j< data.length; j++){
            if( data[j] < min ){
                min = data[j];
                index = j;
            }
        }

        temp = data[i];
        data[i] = min;
        data[index]= temp;
    }
    return data;
}

Результаты его испытаний следующие:

console.log( '原始数据:' + dataStore );
console.log( '选择排序:' + selectionSort( dataStore) );

// 原始数据:72,1,68,95,75,54,58,10,35,6,28,45,69,13,88,99,24,28,30,31,78,2,77,82,72
// 选择排序:1,2,6,10,13,24,28,28,30,31,35,45,54,58,68,69,72,72,75,77,78,82,88,95,99

3. Сортировка вставками (insertionSort)

Сортировка вставки немного похоже на данные сортировки человека в алфавитном порядке, так же, как вы будете играть в покер и поместить карты в нужные места по размеру. Его принцип проходит через вложенные петли, внешний цикл перемещает элементы массива один на один, в то время как внутренний цикл сравнивает элементы, выбранные во внешней петле, и элементы позади него; если элемент, выбранный во внешнем цикле, меньше, чем выбран элемент В внутренней петле, затем элемент массива смещается вправо, чтобы освободить место для этого элемента во внутренней петле.

Этапы реализации следующие:

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

Схема эффекта его реализации выглядит следующим образом:

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

Конкретный код реализации выглядит следующим образом:

//插入排序

function insertionSort( data ) {
    var len = data.length;
    for (var i = 1; i < len; i++) {
        var key = data[i];
        var j = i - 1;
        while ( j >= 0 && data[j] > key) {
            data[j + 1] = data[j];
            j--;
        }
        data[j + 1] = key;
    }
    return data;
}

Результаты сортировки следующие:

console.log( '原始数据:' + dataStore );
console.log( '插入排序:' + insertionSort( dataStore) );

// 原始数据:72,1,68,95,75,54,58,10,35,6,28,45,69,13,88,99,24,28,30,31,78,2,77,82,72
// 插入排序:1,2,6,10,13,24,28,28,30,31,35,45,54,58,68,69,72,72,75,77,78,82,88,95,99

Мы изучили три основных алгоритма сортировки, из которых пузырьковая сортировка — самая медленная, сортировка вставками — самая быстрая, мы можем передать console.time('sortName') и console.timeEnd('sortName') во время запущенного процесса ') Два выхода чтобы увидеть, насколько они эффективны.Я привожу здесь набор значений в качестве ссылки.На практике требуется большой объем проверки данных и повторных экспериментов, и математическая статистика может рассматриваться как эффективная статистика;

排序时间比较
Сравнение времени сортировки

Расширенные алгоритмы сортировки

4. Сортировка Шелла

Первое, что нам нужно изучить, — это сортировка Хилла, также известная как инкрементная сортировка с уменьшением.Этот алгоритм значительно улучшен на основе сортировки вставками.В отличие от сортировки вставками, он сначала сравнивает элементы, которые находятся дальше, а не соседние элементы. Эта схема может сделать элементы далеко от правильного положения, чтобы быстро вернуться в соответствующее положение.Когда алгоритм проходит, расстояние между всеми элементами будет продолжать уменьшаться до конца данных, после чего сравниваются соседние элементы. .

Основная идея этого метода заключается в следующем: всю последовательность сортируемых элементов сначала разделить на несколько подпоследовательностей (состоящих из элементов, разделенных определенным «приращением») для прямой сортировки вставками, а затем уменьшать приращения по очереди перед сортировка и ожидание завершения. Когда элементы в последовательности в основном упорядочены (приращение достаточно мало), выполните прямую сортировку вставками для всех элементов. Поскольку прямая сортировка вставками очень эффективна, когда элементы в основном упорядочены (близко к лучшему случаю), сортировка Хилла значительно повышает эффективность времени.

Ну, я все же использую случай для объяснения, так будет понятнее, возьмем для примера следующий набор данных:

数据集
набор данных
  • Первый пробел (приращение) = 10/2 = 5, будет сгруппирован следующим образом, чтобы получить пять наборов данных (49, 13), (38, 27), (65, 49), (97, 55), (26 , 4), после сортировки внутри группы (13, 49), (27, 38), (49, 65), (55, 97), (4, 26)
第一次分组
первая группа

В этом случае данные будут расположены в следующей структуре

第一次排序
первый сорт
  • Второй промежуток времени = 5/2 = 2, вы можете получить две группы в это время следующим образом
第二次分组
вторая группа

После сортировки внутри группы можем получить

第二次排序
второго порядка
  • Третий пробел = 2/2=1, то есть без группировки, после сортировки
第三次排序
третий порядок
  • Четвертый промежуток времени = 1/2 = 0, вы можете получить отсортированный массив
排序完成
Сортировка сделана

Теперь вы можете иметь некоторое представление о сортировке по Хиллу, которая реализована в JS следующим образом:

//希尔排序

function shallSort(array) {
    var increment = array.length;
    var i
    var temp; //暂存
    do {
        //设置增量
        increment = Math.floor(increment / 3) + 1;
        for (i = increment ; i < array.length; i++) {
            if ( array[i] < array[i - increment]) {
                temp = array[i];
                for (var j = i - increment; j >= 0 && temp < array[j]; j -= increment) {
                    array[j + increment] = array[j];
                }
                array[j + increment] = temp;
            }
        }
    }
    while (increment > 1)

    return array;
}

Эффект следующий:

console.log( '原始数据:' + dataStore );
console.log( '希尔排序:' + shallSort( dataStore) );

// 原始数据:72,1,68,95,75,54,58,10,35,6,28,45,69,13,88,99,24,28,30,31,78,2,77,82,72
// 希尔排序:1,2,6,10,13,24,28,28,30,31,35,45,54,58,68,69,72,72,75,77,78,82,88,95,99

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

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

Этапы реализации следующие:

  1. Разделить входную последовательность длины n на две подпоследовательности длины n/2;
  2. Сортировка слиянием используется для этих двух подпоследовательностей соответственно;
  3. Объединить две отсортированные подпоследовательности в окончательную отсортированную последовательность

Движущееся изображение, иллюстрирующее процесс сортировки слиянием:

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

Конкретный код JS реализован следующим образом:

//归并排序

function mergeSort ( array ) {
    var len = array.length;
    if( len < 2 ){
        return array;
    }
    var middle = Math.floor(len / 2),
        left = array.slice(0, middle),
        right = array.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right)
{
    var result = [];
    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;
}

Результаты теста следующие:

console.log( '原始数据:' + dataStore );
console.log( '希尔排序:' + mergeSort( dataStore) );

// 原始数据:72,1,68,95,75,54,58,10,35,6,28,45,69,13,88,99,24,28,30,31,78,2,77,82,72
// 希尔排序:1,2,6,10,13,24,28,28,30,31,35,45,54,58,68,69,72,72,75,77,78,82,88,95,99

6. Быстрая сортировка (Quicksort)

Быстрая сортировка — это один из самых быстрых алгоритмов сортировки для обработки больших данных. Это также алгоритм «разделяй и властвуй», который рекурсивно разбивает данные на различные подпоследовательности, содержащие более мелкие и более крупные элементы. Этот шаг повторяется до тех пор, пока все последовательности не будут упорядочены, и наконец, эти подпоследовательности объединяются вместе для получения отсортированных данных.

Алгоритм сначала выбирает элемент из последовательности в качестве опорного. Затем все данные будут вращаться вокруг этой системы счисления, поместите элементы, меньшие, чем система счисления, слева от нее, а все числа, большие или равные ему, справа, повторите вышеуказанные шаги для левого и правого десятичных столбцов, пока каждый интервал имеет только 1 номер.

Весь процесс сортировки выглядит следующим образом:

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

Конкретная реализация выглядит следующим образом:

//快速排序

function quickSort( arr ){
    console.time('quickSort')
    if ( arr.length == 0) {
        return [];
    }
    var left = [];
    var right = [];
    var pivot = arr[0];
    for (var i = 1; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push( arr[i] );
        } else {
            right.push( arr[i] );
        }
    }
    console.timeEnd('quickSort');
    return quickSort( left ).concat( pivot, quickSort( right ));
}

Результаты теста следующие:

console.log( '原始数据:' + dataStore );
console.log( '快速排序:' + quickSort( dataStore) );

// 原始数据:72,1,68,95,75,54,58,10,35,6,28,45,69,13,88,99,24,28,30,31,78,2,77,82,72
// 快速排序:1,2,6,10,13,24,28,28,30,31,35,45,54,58,68,69,72,72,75,77,78,82,88,95,99

До сих пор мы в основном представили идеи и конкретные реализации некоторых распространенных алгоритмов сортировки (сортировка по основанию была представлена ​​в предыдущих статьях, если вы хотите знатькликните сюда), алгоритм сортировки широк и глубок, нам предстоит не только изучить теорию, но и продолжить практику, всем!

Категории