Python Bubble Sort

Document 对象参考手册Python3 Examples

Bubble sort is a simpleexchange sort algorithm, and its core working principle is:

  1. Repeatedly traverse the list to be sorted, comparingtwo adjacent elements；
  2. If the order of the two elements does not meet the requirements (for example, in ascending sort, the previous element is greater than the next one), thenswap their positions；
  3. Each round of traversal will move thelargest element in the current unsorted part to the end by bubbling(ascending order scenario), just like bubbles floating up;
  4. Repeat the above process until the entire list is completely sorted (no swap operations occur or all elements have been traversed).

Key Features

  • Sorting type: exchange sort
  • Time complexity: worst case O(n²) (list completely in reverse order), average case O(n²), best case O(n) (optimized version, list already sorted)
  • Space complexity: O(1) (in-place sorting, no extra auxiliary space needed)
  • Stability: stable sort (the relative positions of equal elements will not change)

Example

def bubbleSort(arr): n = len(arr) # Traverse all array elements for i in range(n): # The last i elements are already in the correct position (no need to compare again) 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 ("Sorted array:") for i in range(len(arr)): print ("%d" %arr[i]),

The output of executing the above code is:

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

Document 对象参考手册Python3 Examples

Other Extensions