1. Обзор:

　　

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

  • Простая сортировка: пузырьковая сортировка, сортировка выбором, сортировка вставками
  • Продвинутая сортировка: быстрая сортировка, сортировка слиянием, сортировка Шелла
  • Связанные знания об алгоритмах: разбиение, рекурсия, бинарный поиск

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

(1) Принцип:

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

(2) Пример:

Данные для сортировки: 7, 6, 9, 8, 5, 1

Процесс сортировки в первом раунде:

指针先指向7，7和6比较，6<7，交换6和7的位置，结果为：6,7,9,8,5,1
指针指向第二个元素7，7和9比较，9>7，不用交换位置，结果仍为：6,7,9,8,5,1
指针指向第三个元素9，比较9和8，8<9，交换8和9的位置，结果为：6,7,8,9,5,1
指针指向第四个元素9，比较9和5，5<9，交换5和9，结果为：6,7,8,5,9,1
指针指向第五个元素9，比较9和1，1<9，交换1和9的位置，结果为6,7,8,5,1,9

После первого раунда сортировки наибольшее число, 9, перемещается в крайнее правое положение.

Переходим ко второму раунду сортировки. Процесс такой же, как выше, за исключением того, что поскольку наибольшее число 9 уже находится в крайнем правом положении, нет необходимости снова сравнивать 9, что экономит одно сравнение. Результат после второго раунда: 6,7,5,1,8,9

Результат третьего раунда: 6,5,1,7,8,9

Результат сравнения в четвёртом раунде: 5,1,6,7,8,9

Результат сравнения в пятом раунде: 1,5,6,7,8,9

Итоговый результат сортировки: 1,5,6,7,8,9. Из вышесказанного видно, что для сортировки N элементов данных требуется N-1 раундов сортировки; количество сравнений, необходимых в i-м раунде, равно N-i.

(3) Подход к написанию кода:

Требуются два уровня циклов. Первый цикл, i, представляет количество раундов сортировки, а второй цикл, j, — количество сравнений.

(4) Реализация кода:

Пример

package com.test.insertsort; /** * Сортировка выбором * @author Администратор * */ public class ChooseSort { private int[] array; private int length; public ChooseSort(int[] array){ this.array = array; this.length = array.length; } /** * Вывести все элементы массива **/ public void display(){ for(int i: array){ System.out.print(i+" "); } System.out.println(); } /** * Алгоритм сортировки выбором **/ public void chooseSort(){ for(int i=0; i<length-1; i++){ int minIndex = i; for(int j=minIndex+1;j<length;j++){ if(array[j]<array[minIndex]){ minIndex = j; } } int temp = array[i]; array[i] = array[minIndex]; array[minIndex] = temp; } } public static void main(String[] args){ int[] array={100,45,36,21,17,13,7}; ChooseSort cs = new ChooseSort(array); System.out.println("Данные до сортировки:"); cs.display(); cs.chooseSort(); System.out.println("Данные после сортировки:"); cs.display(); } }

(5) Сводка по сортировке выбором:

Для N элементов требуется N-1 раундов сортировки;

В i-м раунде требуется N-i сравнений;

Для сортировки N элементов требуется n(n-1)/2 сравнений;

Алгоритмическая сложность сортировки выбором по-прежнему O(n*n);

По сравнению с пузырьковой сортировкой сортировка выбором значительно сокращает количество обменов, поэтому она быстрее пузырьковой сортировки.

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

Сортировка вставками — самый быстрый алгоритм сортировки среди простых сортировок. Хотя её временная сложность по-прежнему O(n*n), она намного быстрее пузырьковой сортировки и сортировки выбором.

(1) Принцип:

  • 1. Установите указатель на элемент. Предположите, что все элементы слева от него упорядочены. Извлеките этот элемент, затем сравните его с элементами слева от него справа налево. Если встретится элемент больше него, переместите этот элемент вправо. Остановитесь, когда найдёте элемент меньше него или когда дойдёте до крайнего левого края и обнаружите, что все элементы слева от него больше него.
  • 2. В этот момент появляется пустая позиция. Поместите элемент в эту пустую позицию. Теперь все элементы слева от этого элемента меньше него, а все элементы справа больше него.
  • 3. Переместите указатель на одну позицию назад и повторите описанный выше процесс. После каждого раунда операций количество упорядоченных элементов слева увеличивается на один, а количество неупорядоченных элементов справа уменьшается на один.

(2) Пример:

Данные для сравнения: 7, 6, 9, 8, 5, 1

  • Первый раунд: Указатель указывает на второй элемент, 6. Предположим, что элементы слева от 6 упорядочены. Извлекаем 6, получая 7,_,9,8,5,1. Начиная с 7, сравниваем 6 с 7 и находим 7>6. Перемещаем 7 вправо, получая _,7,9,8,5,1. Вставляем 6 в пустую позицию перед 7. Результат: 6,7,9,8,5,1
  • Второй раунд: Указатель указывает на третий элемент, 9. В этот момент элементы слева от него, 6,7, упорядочены. Извлекаем 9, получая 6,7,_,8,5,1. Начиная с 7, поочерёдно сравниваем каждый элемент с 9 и обнаруживаем, что все элементы слева от 9 меньше 9, поэтому перемещать ничего не нужно. Помещаем 9 в пустую позицию. Результат остаётся прежним: 6,7,9,8,5,1
  • Третий раунд: Указатель указывает на четвёртый элемент, 8. В этот момент элементы слева от него, 6,7,9, упорядочены. Извлекаем 8, получая 6,7,9,_,5,1. Начиная с 9, поочерёдно сравниваем каждый элемент с 8 и обнаруживаем, что 8<9. Перемещаем 9 вправо, получая 6,7,_,9,5,1. Вставляем 8 в пустую позицию. Результат: 6,7,8,9,5,1
  • Четвёртый раунд: Указатель указывает на пятый элемент, 5. В этот момент элементы слева от него, 6,7,8,9, упорядочены. Извлекаем 5, получая 6,7,8,9,_,1. Начиная с 9, поочерёдно сравниваем каждый элемент с 5 и обнаруживаем, что 5 меньше всех элементов слева от него. Все элементы слева от 5 сдвигаются вправо, получая _,6,7,8,9,1. Помещаем 5 в пустую позицию. Результат: 5,6,7,8,9,1.
  • Пятый раунд: Аналогично вышеописанному. 1 перемещается в самый левый край. Итоговый результат: 1,5,6,7,8,9.

(3) Анализ кода:

Нужны два уровня циклов. Первый цикл, index, представляет указатель в приведённом выше примере, то есть он перебирает каждый элемент, начиная с координаты 1. Второй цикл начинается с leftindex=index-1 и проходит влево с leftindex--, сравнивая каждый элемент с элементом в i, пока элемент в j не станет меньше элемента в i или leftindex<0. Пройти по каждому элементу от i до j, чтобы сдвинуть его вправо, и в конце поместить элемент с индексом index в пустую позицию в leftindex.

(4) Реализация кода:

Пример

package com.test.insertsort; /** * Алгоритм сортировки вставками: * 1. Использовать определённую позицию в массиве как разделительную, например, index=1, и предположить, что левая часть полностью упорядочена. * * 2. Извлечь данные из позиции index и поместить их во временную переменную. Теперь позиция index пуста. * * 3. Начиная с leftindex=index-1, сравнить данные слева с данными по текущему index (т.е. temp). Если array[leftindex]>temp, * то сдвинуть array[leftindex] назад на одну позицию, т.е. array[leftindex+1]=array[leftindex]. В этот момент leftindex становится пустым. * * 4. Затем сравнить данные по index-2 (т.е. leftindex=leftindex-1) с temp, повторить шаг 3, * пока не будут найдены данные <=temp или пока сравнение не дойдёт до самого левого края (это значит, что temp — наименьший), прекратить сравнение и поместить temp в текущую пустую позицию. * * 5. Сдвинуть index назад на 1, т.е. index=index+1, temp=array[index], повторять шаги 2-4, пока index=array.length, сортировка завершится, * и данные в массиве теперь упорядочены по возрастанию. * * @author bjh * */ public class InsertSort { private int[] array; private int length; public InsertSort(int[] array){ this.array = array; this.length = array.length; } public void display(){ for(int a: array){ System.out.print(a+" "); } System.out.println(); } /** * Метод сортировки вставками **/ public void doInsertSort(){ for(int index = 1; index<length; index++){//Внешний index перемещается вправо, то есть это индекс данных, используемых как объект сравнения. int temp = array[index];//Данные, используемые для сравнения. int leftindex = index-1; while(leftindex>=0 && array[leftindex]>temp){//Когда сравнение достигает крайнего левого элемента или встречает данные меньше temp, завершите цикл. array[leftindex+1] = array[leftindex]; leftindex--; } array[leftindex+1] = temp;//Поместите temp в пустую позицию. } } public static void main(String[] args){ int[] array = {38,65,97,76,13,27,49}; InsertSort is = new InsertSort(array); System.out.println("Данные до сортировки:"); is.display(); is.doInsertSort(); System.out.println("Данные после сортировки:"); is.display(); } }

(5) Анализ сортировки вставками:

Временная сложность: поскольку всё ещё нужны два уровня циклов, временная сложность сортировки вставками по-прежнему O(n*n).

Количество сравнений: В первом раунде сортировки сортировка вставками выполняет не более одного сравнения; во втором раунде — не более двух; и так далее. В последнем раунде она выполняет не более N-1 сравнений. Следовательно, максимальное количество сравнений для сортировки вставками равно 1+2+...+N-1=N*(N-1)/2. Тем не менее, сортировка вставками редко действительно выполняет столько сравнений, потому что как только слева обнаруживается элемент, меньший целевого, сравнение прекращается. Поэтому среднее количество сравнений для сортировки вставками равно N*(N-1)/4.

Количество перемещений: количество перемещений в сортировке вставками почти такое же, как количество сравнений, но перемещение намного быстрее, чем обмен.

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

Быстрая сортировка, пузырьковая сортировка, сортировка выбором, сортировка вставками, сортировка слиянием

1. Обзор:

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

2. Разбиение:

Разбиение — это предпосылка быстрой сортировки, то есть разделение данных на две группы: данные больше определённого значения в одной группе, а данные меньше определённого значения — в другой. Быстрая сортировка выполняется посредством разбиения и рекурсивных операций.

(1) Принцип:

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

(2) Пример:

Данные для разбиения: 7, 6, 9, 8, 5, 1, предположим, что пороговое значение равно 5

Первый раунд: левый указатель указывает на 7, правый указатель указывает на 1. Левый указатель движется назад, а правый указатель движется влево. Находит, что первый элемент больше 5 слева — это 7, а первый элемент меньше 5 справа — это 1. Меняем местами 7 и 1. Результат: 1, 6, 9, 8, 5, 7;

Второй раунд: начиная с 6, найти число больше 5 и находим 6. Справа, начиная с 5, найти число меньше 5 и находим 1. Но теперь, поскольку 6 находится справа от 1, то есть правый указатель < левый указатель, левый и правый указатели пересекаются, и разбиение завершается. Исходная последовательность делится на две части. Левая подпоследовательность содержит только один элемент, 1, — это подпоследовательность меньше порогового значения; правая подпоследовательность включает 5 элементов, все больше порогового значения 5.

(3) Реализация кода:

Пример

package com.test.insertsort; /** * Разбиение, рекурсия, быстрая сортировка * @author bjh * */ public class QuickSort { /** Массив для сортировки/разбиения*/ private int[] array; /** Длина массива*/ private int length; public QuickSort(int[] array){ this.array = array; this.length = array.length; } /** * Печать элемента*/ public void printArray(){ for(int i=0; i<length; i++){ System.out.print(array[i]+" "); } System.out.println(); } /** * Разбиение @return Граничная точка разбиения*/ public int partition(int left, int right, int pivot){ //Начальная позиция левого указателя. left-1 — это потому, что в последующем цикле при каждом выполнении цикла левый указатель перемещается вправо. //Это гарантирует, что левый указатель начинает работу с первого элемента слева; иначе он начинался бы со второго. int leftpoint = left-1; //Начальная позиция правого указателя. right+1 — это потому, что в последующем цикле при каждом выполнении цикла правый указатель перемещается влево. //Это гарантирует, что правый указатель начинает работу с крайнего правого элемента; иначе он начинался бы с предпоследнего. int rightpoint = right+1; while(true){ //Найти данные слева, которые больше pivot, или, если он дойдёт до крайнего правого края, не найдя данных больше pivot. while(leftpoint<right && array[++leftpoint]<pivot); //Найти данные справа, которые меньше pivot, или, если он дойдёт до крайнего левого края, не найдя данных меньше pivot. while(rightpoint>left && array[--rightpoint]>pivot); //Левый и правый указатели перекрываются или пересекаются. if(leftpoint >= rightpoint){ break; }else{ //Поменять местами больший элемент слева с меньшим элементом справа. swap(leftpoint,rightpoint); } } //Вернуть граничную точку, т. е. самую левую точку в правом подмассиве. return leftpoint; } /** * Обменять данные*/ public void swap(int leftpoint,int rightpoint){ int temp = array[leftpoint]; array[leftpoint] = array[rightpoint]; array[rightpoint] = temp; } public static void main(String args[]){ int[] array = {99,78,26,17,82,36,9,81,22,100,30,20,17,85}; QuickSort qs = new QuickSort(array); System.out.println("Данные до разбиения:"); qs.printArray(); int bound = qs.partition(0, array.length-1, 50); System.out.println("Данные после разбиения:"); qs.printArray(); System.out.println("Граничная точка разбиения:" + array[bound] + ", координата граничной точки:" + предел); } }

Результат выполнения:

Исходная ссылка: https://www.cnblogs.com/bjh1117/p/8335628.html