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

Document 对象参考手册Python3 Примеры

Пузырьковая сортировка — это простойалгоритм обменной сортировки, и её основной принцип работы таков:

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

Ключевые особенности

  • Тип сортировки: обменная сортировка
  • Временная сложность: худший случай O(n²) (список полностью в обратном порядке), средний случай O(n²), лучший случай O(n) (оптимизированная версия, список уже отсортирован)
  • Пространственная сложность: O(1) (сортировка на месте, дополнительная вспомогательная память не требуется)
  • Устойчивость: устойчивая сортировка (относительные позиции равных элементов не изменяются)

Пример

def bubbleSort(arr): n = len(arr) # Пройти по всем элементам массива for i in range(n): # Последние i элементов уже находятся в правильной позиции (не нужно сравнивать снова) for j in range(0, n-i-1): if arr[j] > arr[j+1] : arr[j], arr[j+1] = arr[j+1], arr[j] arr = [64, 34, 25, 12, 22, 11, 90] bubbleSort(arr) print ("Отсортированный массив:") for i in range(len(arr)): print ("%d" %arr[i]),

Результат выполнения приведённого выше кода:

排序后的数组:
11
12
22
25
34
64
90

Document 对象参考手册Python3 Примеры

Другие расширения