Алгоритм — это набор четко определенных правил, используемых для решения проблемы за ограниченное количество шагов. Проще говоря, это процесс компьютерного решения задач. В этом процессе, формируете ли вы идею решения проблемы или пишете программу, вы реализуете определенный алгоритм. Первый — это алгоритм, реализуемый посредством рассуждений, а второй — алгоритм, реализуемый посредством операции.
Алгоритм должен обладать следующими пятью важными характеристиками:
1. Конечность. Алгоритм должен гарантировать, что он завершится после выполнения конечного числа шагов;
2. Точность: каждый шаг алгоритма должен быть четко определен;
3. Входные данные. Алгоритм имеет 0 или более входных данных для описания исходной ситуации операнда;
4. Выход. Алгоритм имеет один или несколько выходов, отражающих результаты обработки входных данных. Алгоритм без вывода бессмысленен;
5. Осуществимость. В принципе, алгоритм может работать точно, и его могут выполнить люди, использующие ручку и бумагу для выполнения ограниченного числа операций.
Сортировка слиянием (MERGE SORT) — это еще один тип другого метода сортировки. Смысл слияния заключается в объединении двух или более упорядоченных последовательностей данных в новую упорядоченную последовательность данных, поэтому его также называют алгоритмом слияния. Его основная идея состоит в том, чтобы предположить, что массив A имеет N элементов, тогда массив A можно рассматривать как состоящий из N упорядоченных подпоследовательностей, каждая подпоследовательность имеет длину 1, а затем объединить два на два, чтобы получить N/2. Затем длина 2 или 1 объединяется по два, и это повторяется до тех пор, пока не будет получена упорядоченная последовательность данных длины N. Этот метод сортировки называется двухсторонней сортировкой слиянием.
Например, массив A имеет 7 данных, а именно: 49 38 65 97 76 13 27. Тогда рабочий процесс использования алгоритма сортировки слиянием показан на рисунке 7:
Начальное значение[49][38][65][97][76][13][27]
Рассматривается как состоящая из 7 подпоследовательностей длины 1. После первого слияния [38 49] [65 97] [13 76] [27]
Рассматривается как состоящая из 4 подпоследовательностей длиной 1 или 2. После второго слияния [38 49 65 97] [13 27 76]
Рассматривается как состоящая из 2 подпоследовательностей длиной 4 или 3. После третьего слияния [13 27 38 49 65 76 97]
Рис. 6. Схема процесса алгоритма сортировки слиянием. Основная операция алгоритма слияния заключается в объединении двух соседних упорядоченных последовательностей в одномерном массиве в одну упорядоченную последовательность. Алгоритм слияния также можно реализовать с помощью рекурсивного алгоритма, который относительно прост по форме, но имеет низкую практичность.
Количество слияний в алгоритме слияния — очень важная величина. Согласно расчетам, при наличии в массиве от 3 до 4 элементов количество слияний равно 2, при 5–8 элементах — 3. , а при наличии от 9 до 16 элементов число слияний равно 4. Согласно этому правилу при наличии N подпоследовательностей можно сделать вывод, что число слияний равно
X (2>=N, наименьший X, удовлетворяющий подусловию).
Описание пузырькового алгоритма:
Прежде чем объяснять алгоритм пузырьковой сортировки, давайте сначала представим алгоритм, который помещает наибольшее число из 10 чисел (в массиве A) в последнюю позицию. Алгоритм описывается следующим образом:
(1) От массива A[1] до A[10] сравните два соседних числа попарно. То есть A[1] сравнивается с A[2], а после сравнения A[2] сравнивается с A[3],... и, наконец, A[9] сравнивается с A[10].
(2) Во время каждого сравнения, если предыдущее число больше последнего, два числа будут заменены местами, то есть большее число будет перемещено назад, а меньшее число будет перемещено вперед. Например, при первом сравнении, если A[1] больше, чем A[2], значения A[1] и A[2] меняются местами. На рисунке ниже используются 6 данных для иллюстрации приведенного выше алгоритма.
Предположим, что 6 данных: A[]=5 7 4 3 8 6
А[1] А[2] А[3] А[4] А[5] А[6]
5 7 4 3 8 6 При первом сравнении A[1]=5 и A[2]=7, 7>5, замена не выполняется.
5 7 4 3 8 6 Во второй раз сравниваются A[2]=7 и A[3]=4, 4<7, меняем местами.
Тогда данные после второго сравнения будут 5 4 7 3 8 6
5 4 7 3 8 6 В третий раз сравниваются A[3]=7 и A[4]=3, 3<7, меняем местами.
Тогда данные после третьего сравнения будут 5 4 3 7 8 6
5 4 3 7 8 6 В четвертый раз сравниваются A[4]=7 и A[5]=8, 8>7, замена не выполняется.
5 4 3 7 8 6 В пятый раз сравниваются A[6]=6 и A[5]=8, 6<8, меняем местами.
Тогда пятый и последний результат:
5 4 3 7 6 8
************************************************* * *****
Описание алгоритма сортировки выбором:
Прежде чем представить метод сортировки выбором, давайте представим алгоритм, который помещает наименьшее число в первую позицию. Конечно, вы также можете использовать метод пузырьковой сортировки, упомянутый выше. Теперь мы используем новый алгоритм: его руководящая идеология мне не известна. поспеши сначала поменять позиции, но начни с A[1] начинает проверять одно за другим. Чтобы узнать, какое число является наименьшим, запишите позицию P числа. После завершения сканирования поменяйте местами A[P] и A[1]. От [1] до A[10] перемещаются на переднее положение. Шаги алгоритма следующие:
1) Во-первых, предположим, что число в A[1] является наименьшим, и обратите внимание на позицию P=1 в этот момент;
2) Сравнить A[P] и A[I] последовательно (I меняется от 2 до 10. При каждом сравнении, если число в A[I] меньше числа в A[P], то I Значение. присваивается P, так что P всегда указывает на позицию наименьшего числа, сканируемого в данный момент, то есть A[P] всегда равно наименьшему числу всех сканируемых чисел. После сравнения по одному P указывает на позицию наименьшего числа среди 10 чисел, то есть A[P] — наименьшее число среди 10 чисел;
3) Поменяйте местами числа A[P] и A[1], тогда наименьшее число будет в A[1], то есть спереди.
Если теперь повторить этот алгоритм, но при каждом его повторении диапазон сравниваемого ряда смещается на одну позицию назад. То есть во втором сравнении диапазон находится от 2-го числа до N-го числа. Найдите позицию P наименьшего числа в этом диапазоне, а затем поменяйте местами A[P] и A[2], чтобы получить от 2-го числа. Наименьшее число от начала до N-го числа находится в A [2] успешен, в третий раз нужно найти наименьшее число от 3-го числа до N-го числа, а затем поменять местами A[P] и A[3]... Повторив этот процесс N-1 раз, просто расположите N чисел в массиве A от меньшего к большему. Этот метод сортировки является сортировкой выбором.
************************************************* * ***************
Описание алгоритма сортировки вставками:
Изучив два вышеуказанных метода, вы сможете понять основную идею сортировки, а также сможете упорядочить любой неупорядоченный массив от большого к меньшему (по убыванию) или от малого к большому (по возрастанию). Теперь предположим, что существует уже упорядоченная последовательность данных, и необходимо вставить число в эту уже упорядоченную последовательность данных, но требуется, чтобы последовательность данных все еще была упорядочена после вставки. В это время будет использоваться новый метод сортировки. Использовать метод сортировки вставкой. Основная операция сортировки вставкой заключается в вставке данных в упорядоченные данные, которые были отсортированы, чтобы получить новые упорядоченные данные с числом плюс один.
Вопрос: В массиве A имеется N фрагментов данных, расположенных в порядке от меньшего к большему. Введите число X и вставьте значение X в массив A так, чтобы вставленный массив A по-прежнему располагался в порядке от меньшего к большему. .
Тогда алгоритм решения этой задачи следующий:
1) Найдите позицию, куда следует вставить X, сравнив размер, если он должен располагаться на I-й позиции;
2) Переместить все элементы массива, начиная с I (включая I), на одну позицию назад, то есть A[I+1]:=A[I];
Быстрая сортировка — это усовершенствованная версия пузырьковой сортировки. Его основная идея состоит в том, чтобы разделить данные, подлежащие сортировке, на две независимые части посредством односторонней сортировки. Все данные в одной части меньше, чем все данные в другой части, а затем две части данных сортируются последовательно. Для быстрой сортировки весь процесс сортировки можно выполнить рекурсивно, чтобы все данные стали упорядоченной последовательностью.
Предположим, что сортируемый массив имеет вид A[1]...A[N]. Сначала случайным образом выберите данные (обычно первые данные) в качестве ключевых данных, а затем поместите перед ними все числа, большие, чем они. и все числа, превышающие его. Большие числа помещаются за ним. Этот процесс называется быстрой сортировкой. Алгоритм быстрой сортировки:
1) Задайте две переменные I и J. Когда начнется сортировка, I:=1, J:=N;
2) Использовать первый элемент массива в качестве ключевых данных и присвоить его X, то есть X:=A[1];
3) Поиск вперед от J, то есть поиск вперед сзади (J:=J-1), нахождение первого значения меньше X и обмен ими местами;
4) Поиск назад от I, то есть поиск спереди назад (I:=I+1), нахождение первого значения, большего, чем X, и обмен ими местами;
5) Повторяйте шаги 3 и 4, пока I=J;
Например: значения массива A для сортировки: (начальные ключевые данные X:=49)
А[1] А[2] А[3] А[4] А[5] А[6] А[7]:
49 38 65 97 76 13 27
После первого обмена: 27 38 65 97 76 13 49
(После поиска сзади по третьему шагу алгоритма второго обмена: 27 38 49 97 76 13 65
(Выполните четвертый шаг алгоритма и начните с начала, чтобы найти значение>
После третьего обмена: 27 38 13 97 76 49 65
(Согласно пятому шагу алгоритма, третий шаг алгоритма будет выполнен снова с конца для поиска четвертого обмена: 27 38 13 49 76 97 65
(Следуйте четвертому шагу алгоритма и начните с начала, чтобы найти значение больше X, 97>49, поменяйте местами два, в этот момент J:=4)
В это время при выполнении третьего шага обнаруживается, что I=J, что завершает быструю сортировку. Результат после быстрой сортировки: 27 38 13 49 76 97 65, то есть все числа больше 49 находятся в числе 49. , поэтому все числа меньше 49 стоят перед 49.
Быстрая сортировка заключается в вызове этого процесса рекурсивно: разделите последовательность данных со средней точкой 49, выполните аналогичную быструю сортировку на передней и задней части соответственно, тем самым завершив быструю сортировку всей последовательности данных, и, наконец, переверните последовательность данных. в упорядоченную последовательность. Согласно этой идее, весь процесс быстрой сортировки вышеуказанного массива A показан на рисунке 6:
Исходное состояние {49 38 65 97 76 13 27}
После быстрой сортировки он делится на {27 38 13} 49 {76 97 65}
Быстрая сортировка передней и задней части соответственно {13} 27 {38}
конец конец {49 65} 76 {97} 49 {65} конец конец
************************************************* * *************************
Рисунок 6 Описание алгоритма быстрой сортировки на протяжении всего процесса быстрой сортировки
1). Предположим, что N (при условии, что N = 10) чисел хранятся в массиве S;
2), в S[1. . Возьмите любой элемент из N] в качестве основы сравнения, например, T=S[1]. Первоначальная цель — определить позицию K, где T должен находиться в результате сортировки. Позиция K: S[1]. . . K-1]<=S[K]<=S[K+1..N], то есть все числа перед S[K] меньше, чем S[K], а числа после S[K] равны все больше, чем S[ K];
3) Использование идеи «разделяй и властвуй» (то есть стратегии превращения большого и малого в маленькое) может еще больше улучшить S[1. . К-1] и S[К+1. . N] Затем два набора данных быстро сортируются до тех пор, пока в группирующем объекте не останется только один данные.
Если конкретные данные следующие, то первый процесс быстрой сортировки:
Индекс массива: 1 2 3 4 5 6 7 8 9 10
45 36 18 53 72 30 48 93 15 36
ij
(1) 36 36 18 53 72 30 48 93 15 45
(2) 36 36 18 45 72 30 48 93 15 53
(3) 36 36 18 15 72 30 48 93 45 53
(4) 36 36 18 15 45 30 48 93 72 53
(5) 36 36 18 15 30 45 48 93 72 53