принцип
Сортировка пузырьков, вероятно, является алгоритмом, который могут использовать все программисты, а также является одним из самых знакомых алгоритмов.
Его идеи не сложны:
Предположим, что массив ARR [] теперь отсортирован, и в нем есть элементы.
1. Если n = 1: Очевидно, нет необходимости в очереди. (Фактически, это обсуждение кажется ненужным)
2. Если n> 1:
(1) Мы начинаем с первого элемента и сравниваем каждые два соседних элемента. Если предыдущий элемент больше, чем следующий, то первое определенно будет оцениваться в конечном результате. Итак, мы обмениваемся этими двумя элементами. Затем сравните следующие два соседних элемента. Таким образом, до сравнения последней пары элементов, первый раунд сортировки завершен. Несомненно, что последний элемент должен быть самым большим в массиве (потому что относительно большой расположен сзади каждый раз).
(2) Повторите приведенный выше процесс, на этот раз нам не нужно рассматривать последний, потому что он уже расположен.
(3) Таким образом, пока не останется только один элемент, элемент должен быть наименьшим, и тогда наша сортировка может закончиться. Видимо, сортировка N-1 была выполнена.
В приведенном выше процессе каждый раз (или «колесо» отсортируется, число будет медленно «плавать» из определенной позиции до конечной позиции (нарисуйте схему схемы и нарисуйте массив вертикально), как пузырьки, так что это называется «метод сортировки пузырьков».
Реализация кода:
Public Class Bubblesort {public static void main (string [] args) {int acly [] = {67, 69, 75, 87, 89, 90, 99, 100}; для (int i = 0; i <chyll.length -1; i ++) {// Делать не только n -1 упорядочение для (int j = 0; j <scord.length -i -1; j ++) {// Сортировать текущий неупорядоченный интервал -оценка [0 ...... длина -I -1] (диапазон j очень критичен, этот диапазон в постепенном диапазоне). позже int temp = score [j]; счет [j] = оценка [j + 1]; Оценка [J + 1] = TEMP; }} System.out.print ("th" + (i + 1) + "Результат сортировки последовательности:"); for (int a = 0; a <score.length; a ++) {System.out.print (score [a]+"/t"); } System.out.println ("" "); } System.out.print ("Окончательная результат сортировки:"); for (int a = 0; a <score.length; a ++) {System.out.print (score [a]+"/t"); }}}
Производительность алгоритма/сложность
Мы игнорируем время, когда переменные цикла автоматически увеличиваются и инициализируются. Сначала проанализируйте количество сравнений алгоритма. Легко увидеть, что приведенная выше сортировка пузырьков без какого-либо улучшения будет выполнена в раундах N-1 независимо от входных данных, и количество раз в каждом раунде сортировки необходимо сравнивать, уменьшается с N-1 до 0. Тогда общее количество сравнений составляет (n-1)+(n-2)+...+2+1 = (N-1) N/2 (N^2)/2. (Поскольку я не знаю, как делать здесь квадраты, здесь я использую n^2, чтобы представлять квадраты, то же самое ниже)
Давайте посмотрим на количество заданий. Задание здесь относится к операции обмена. Для приведенного выше кода 1 обмен равен трем назначениям. Поскольку не каждый раз, когда необходимо обмениваться, количество операций назначения связано с входными данными. В лучшем случае, то есть, когда порядок в начале, количество назначений составляет 0. В худшем случае количество назначений составляет (N-1) N/2. Предполагая, что входные данные составляют среднее (или «совершенно случайное») распределение, то около половины количества обменов. Из приведенных выше результатов мы можем получить средний случай, причем количество назначений составляет 3/2 * (n^2)/2 = 3/4 * (n^2).
Таким образом, в любом случае, сложность пространства сортировки пузырьков (дополнительное пространство) всегда o (1).
улучшать
Оптимальная сложность времени показана, когда данные полностью упорядочены, что является O (n). В других случаях это почти всегда o (n^2). Следовательно, алгоритм работает лучше всего, когда данные в основном упорядочены.
Однако как приведенный выше код может иметь сложность O (n)? На самом деле, поскольку вышеперечисленное фокусируется на основных идеях, это только самый простой случай. Чтобы алгоритм обладал сложностью O (n) в лучшем случае, необходимо сделать некоторые улучшения. Улучшенный код:
public static void bubblesort (int [] arr) {int temp = 0; логический обмен; for (int i = arr.length -1; i> 0; --I) {// Длина каждого вида должна быть SWAP = false; for (int j = 0; j <i; ++ j) {// от первого элемента к элементу i-th if (arr [j]> arr [j +1]) {temp = arr [j]; arr [j] = arr [j + 1]; arr [j + 1] = temp; Swap = true; }} // loop j if (swap == false) {break; }} // цикл I} // метод BubblesortФактически, поскольку сортировка пузырьков вряд ли используется в случае больших объемов данных, добавленные логические переменные при использовании небольших данных фактически вызывают дополнительные накладные расходы. Поэтому я лично считаю, что улучшенный алгоритм выше только теоретический. Обычно просто пишите предыдущий, пузыривая сортировку.
Стабильность алгоритма
Легко видеть, что когда соседние элементы равны, нам не нужно менять их позиции, поэтому пузырьковые сортировки - стабильная.
Алгоритм применимых сценариев
Идея сортировки пузырьков проста, а код проста, что особенно подходит для сортировки небольших данных. Однако из -за высокой сложности алгоритма он не подходит для использования, когда объем данных большой. Если вы должны использовать его, когда есть больше данных, лучше всего улучшить алгоритм, например, выбор метода сортировки.