# 冒泡排序算法 > 原文： [https://www.programiz.com/dsa/bubble-sort](https://www.programiz.com/dsa/bubble-sort) #### 在本教程中，您將學習冒泡排序的工作原理。 此外，您還將找到 C，C++ ，Java 和 Python 中冒泡排序的工作示例。 冒泡排序是一種算法，用于比較相鄰元素，如果相鄰元素之間的位置不符合預期順序，則會交換它們的位置。 順序可以是升序或降序。 * * * ## 冒泡排序如何工作？ 1. 從第一個索引開始，比較第一個和第二個元素，如果第一個元素大于第二個元素，則將它們交換。 現在，比較第二個和第三個元素。 如果它們不正常，請交換它們。 上面的過程一直進行到最后一個元素。  比較相鄰元素 2. 其余迭代將繼續相同的過程。 每次迭代后，未排序元素中的最大元素將放置在末尾。 在每次迭代中，都會進行比較直到最后一個未排序的元素。 當所有未排序的元素都放在其正確位置時，對數組進行排序。  比較相鄰的元素 [  比較相鄰的元素  比較相鄰的元素 * * * ## 冒泡排序算法 ``` bubbleSort(array) for i <- 1 to indexOfLastUnsortedElement-1 if leftElement > rightElement swap leftElement and rightElement end bubbleSort ``` * * * ## Python，Java 和 C/C++ 示例 ```py # Bubble sort in Python def bubbleSort(array): # run loops two times: one for walking throught the array # and the other for comparison for i in range(len(array)): for j in range(0, len(array) - i - 1): # To sort in descending order, change > to < in this line. if array[j] > array[j + 1]: # swap if greater is at the rear position (array[j], array[j + 1]) = (array[j + 1], array[j]) data = [-2, 45, 0, 11, -9] bubbleSort(data) print('Sorted Array in Asc ending Order:') print(data) ``` ```java // Bubble sort in Java import java.util.Arrays; class BubbleSort { void bubbleSort(int array[]) { int size = array.length; // run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - 1; i++) for (int j = 0; j < size - i - 1; j++) // To sort in descending order, change > to < in this line. if (array[j] > array[j + 1]) { // swap if greater is at the rear position int temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } } // driver code public static void main(String args[]) { int[] data = { -2, 45, 0, 11, -9 }; BubbleSort bs = new BubbleSort(); bs.bubbleSort(data); System.out.println("Sorted Array in Ascending Order:"); System.out.println(Arrays.toString(data)); } } ``` ```c // Bubble sort in C #include <stdio.h> void bubbleSort(int array[], int size) { // run loops two times: one for walking throught the array // and the other for comparison for (int step = 0; step < size - 1; ++step) { for (int i = 0; i < size - step - 1; ++i) { // To sort in descending order, change">" to "<". if (array[i] > array[i + 1]) { // swap if greater is at the rear position int temp = array[i]; array[i] = array[i + 1]; array[i + 1] = temp; } } } } // function to print the array void printArray(int array[], int size) { for (int i = 0; i < size; ++i) { printf("%d ", array[i]); } printf("\n"); } // driver code int main() { int data[] = {-2, 45, 0, 11, -9}; int size = sizeof(data) / sizeof(data[0]); bubbleSort(data, size); printf("Sorted Array in Ascending Order:\n"); printArray(data, size); } ``` ```cpp // Bubble sort in C++ #include <iostream> using namespace std; void bubbleSort(int array[], int size) { // run loops two times: one for walking throught the array // and the other for comparison for (int step = 0; step < size - 1; ++step) { for (int i = 0; i < size - step - 1; ++i) { // To sort in descending order, change > to < in this line. if (array[i] > array[i + 1]) { // swap if greater is at the rear position int temp = array[i]; array[i] = array[i + 1]; array[i + 1] = temp; } } } } // function to print the array void printArray(int array[], int size) { for (int i = 0; i < size; ++i) { cout << " " << array[i]; } cout << "\n"; } // driver code int main() { int data[] = {-2, 45, 0, 11, -9}; int size = sizeof(data) / sizeof(data[0]); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:\n"; printArray(data, size); } ``` * * * ## 優化冒泡排序 在上面的代碼中，即使數組已經排序，也進行了所有可能的比較。 它增加了執行時間。 通過引入`swapped`額外變量可以優化代碼。 每次迭代之后，如果沒有交換發生，則無需執行其他循環。 在這種情況下，將變量`swapped`設置為`false`。 因此，我們可以防止進一步的迭代。 優化冒泡排序的算法是 ``` bubbleSort(array) swapped <- false for i <- 1 to indexOfLastUnsortedElement-1 if leftElement > rightElement swap leftElement and rightElement swapped <- true end bubbleSort ``` * * * ### 優化的冒泡排序示例 ```py # Optimized bubble sort in python def bubbleSort(array): # Run loops two times: one for walking throught the array # and the other for comparison for i in range(len(array)): # swapped keeps track of swapping swapped = True for j in range(0, len(array) - i - 1): # To sort in descending order, change > to < in this line. if array[j] > array[j + 1]: # Swap if greater is at the rear position (array[j], array[j + 1]) = (array[j + 1], array[j]) swapped = False # If there is not swapping in the last swap, then the array is already sorted. if swapped: break data = [-2, 45, 0, 11, -9] bubbleSort(data) print('Sorted Array in Ascending Order:') print(data) ``` ```java // Optimized bubble sort in Java import java.util.Arrays; class BubbleSort { void bubbleSort(int array[]) { int size = array.length; // Run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - 1; i++) { // swapped keeps track of swapping boolean swapped = true; for (int j = 0; j < size - i - 1; j++) { // To sort in descending order, change > to < in this line. if (array[j] > array[j + 1]) { // Swap if greater is at the rear position int temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; swapped = false; } } // If there is not swapping in the last swap, then the array is already sorted. if (swapped == true) break; } } // Driver code public static void main(String args[]) { int[] data = { -2, 45, 0, 11, -9 }; BubbleSort bs = new BubbleSort(); bs.bubbleSort(data); System.out.println("Sorted Array in Ascending Order:"); System.out.println(Arrays.toString(data)); } } ``` ```c // Optimized bubble sort in C #include <stdio.h> void bubbleSort(int arrayay[], int size) { for (int step = 0; step < size - 1; ++step) { // Swapped keeps track of swapping int swapped = 0; // Run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - step - 1; ++i) { // To sort in descending order, change > to < in this line. if (arrayay[i] > arrayay[i + 1]) { // Swap if greater is at the rear position int temp = arrayay[i]; arrayay[i] = arrayay[i + 1]; arrayay[i + 1] = temp; swapped = 1; } } // If there is not swapping in the last swap, then the array is already sorted. if (swapped == 0) break; } } // Function to print an array void printarrayay(int arrayay[], int size) { for (int i = 0; i < size; ++i) { printf("%d ", arrayay[i]); } printf("\n"); } // Driver code int main() { int data[] = {-2, 45, 0, 11, -9}; int size = sizeof(data) / sizeof(data[0]); bubbleSort(data, size); printf("Sorted Array in Ascending Order:\n"); printarrayay(data, size); } ``` ```cpp // Optimized bubble sort in C++ #include <iostream> using namespace std; void bubbleSort(int array[], int size) { for (int step = 0; step < size - 1; ++step) { // Run loops two times: one for walking throught the array // and the other for comparison int swapped = 0; for (int i = 0; i < size - step - 1; ++i) { // To sort in descending order, change > to < in this line. if (array[i] > array[i + 1]) { // Swap if greater is at the rear position int temp = array[i]; array[i] = array[i + 1]; array[i + 1] = temp; swapped = 1; } } // If there is not swapping in the last swap, then the array is already sorted. if (swapped == 0) break; } } // Function to print an array void printArray(int array[], int size) { for (int i = 0; i < size; ++i) { cout << " " << array[i]; } cout << "\n"; } // Driver code int main() { int data[] = {-2, 45, 0, 11, -9}; int size = sizeof(data) / sizeof(data[0]); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:\n"; printArray(data, size); } ``` * * * ## 復雜度 冒泡排序是最簡單的排序算法之一。 該算法實現了兩個循環。 | 周期 | 比較次數 | | --- | --- | | 第一 | （`n-1`） | | 第二 | （`n-2`） | | 第三 | （`n-3`） | | ....... | ...... | | 最后 | 1 | 比較次數：`(n-1) + (n-2) + (n-3) + ..... + 1 = n(n-1) / 2`幾乎等于`n^2` **復雜度**： `O(n^2)` 同樣，我們可以通過簡單地觀察循環數來分析復雜度。 有 2 個循環，因此復雜度為`n*n = n^2` **時間復雜度**： * **最壞情況的復雜度**： `O(n^2)` 如果我們要以升序排序，而數組是以降序排序，那么會發生最壞情況。 * **最佳情況復雜度**： `O(n)` 如果數組已經排序，則無需排序。 * **平均情況復雜度**： `O(n^2)` 當數組的元素處于混亂順序（既不升也不降）時，會發生這種情況。 **空間復雜度**： 空間復雜度為`O(1)`，因為交換使用了額外的變量`temp`。 在優化算法中，變量`swapped`會增加空間復雜度，從而使其成為`O(2)`。 * * * ## 冒泡排序應用 在以下情況下使用冒泡排序： 1. 代碼的復雜程度無關緊要。 2. 短代碼是首選的。