冒泡排序
冒泡排序
冒泡排序是比较两个相邻元素，如果它们不符合预期的顺序就交换的一个排序过程。
冒泡排序就像水中气泡上升到水面的运动一样，数组的每个元素在每次迭代中都把当前迭中最大(或最小)的元素移动到最后，因此被称为冒泡排序。
冒泡排序的工作流程
1. 第一次迭代（比较和交换） 
2. 后续的迭代过程 
复杂度
|Time Complexity|| |—|—| |Best | O(n) | |Worst | O(n^2) | |Average | O(n^2) | |Space Complexity | O(1) | |Stability | Yes |
代码实现
Swift实现
import Foundation
func bubbleSort(array:inout Array<Int>) {
//遍历数组的每个元素,让每个元素都走一遍冒泡流程
for i in 0 ..< array.count - 1 {
//第i个元素走冒泡流程，因为i前面的元素走过冒泡交换流程后，就都已经有序的浮到尾(顶)部了，所以越遍历到后面需要冒泡的层次就会越少
for j in 0 ..< array.count - 1 - i {
//冒泡过程：比较大小，并交换，把大的元素交换到后面
if array[j] > array[j + 1] {
array.swapAt(j, j+1)
}
}
}
}
//打印
func printBubbleSort(_ array:inout [Int]){
bubbleSort(array: &array)
print(array)
}
var arr:[Int] = [3, 2, 5, 7, 1, 5, 4, 8, 11, 0]
printBubbleSort(&arr);
Python实现
# Bubble sort in Python
def bubbleSort(array):
# loop to access each array element
for i in range(len(array)):
# loop to compare array elements
for j in range(0, len(array) - i - 1):
# compare two adjacent elements
# change > to < to sort in descending order
if array[j] > array[j + 1]:
# swapping elements if elements
# are not in the intended order
temp = array[j]
array[j] = array[j+1]
array[j+1] = temp
data = [-2, 45, 0, 11, -9]
bubbleSort(data)
print('Sorted Array in Ascending Order:')
print(data)
Java的实现
// Bubble sort in Java
import java.util.Arrays;
class Main {
// perform the bubble sort
static void bubbleSort(int array[]) {
int size = array.length;
// loop to access each array element
for (int i = 0; i < size - 1; i++)
// loop to compare array elements
for (int j = 0; j < size - i - 1; j++)
// compare two adjacent elements
// change > to < to sort in descending order
if (array[j] > array[j + 1]) {
// swapping occurs if elements
// are not in the intended order
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
public static void main(String args[]) {
int[] data = { -2, 45, 0, 11, -9 };
// call method using class name
Main.bubbleSort(data);
System.out.println("Sorted Array in Ascending Order:");
System.out.println(Arrays.toString(data));
}
}
C实现
// Bubble sort in C
#include <stdio.h>
// perform the bubble sort
void bubbleSort(int array[], int size) {
// loop to access each array element
for (int step = 0; step < size - 1; ++step) {
// loop to compare array elements
for (int i = 0; i < size - step - 1; ++i) {
// compare two adjacent elements
// change > to < to sort in descending order
if (array[i] > array[i + 1]) {
// swapping occurs if elements
// are not in the intended order
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
}
}
// print array
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
int main() {
int data[] = {-2, 45, 0, 11, -9};
// find the array's length
int size = sizeof(data) / sizeof(data[0]);
bubbleSort(data, size);
printf("Sorted Array in Ascending Order:\n");
printArray(data, size);
}
C++实现
// Bubble sort in C++
#include <iostream>
using namespace std;
// perform bubble sort
void bubbleSort(int array[], int size) {
// loop to access each array element
for (int step = 0; step < (size-1); ++step) {
// loop to compare array elements
for (int i = 0; i < size - (step-1); ++i) {
// compare two adjacent elements
// change > to < to sort in descending order
if (array[i] > array[i + 1]) {
// swapping elements if elements
// are not in the intended order
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
}
}
// print array
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
cout << " " << array[i];
}
cout << "\n";
}
int main() {
int data[] = {-2, 45, 0, 11, -9};
// find array's length
int size = sizeof(data) / sizeof(data[0]);
bubbleSort(data, size);
cout << "Sorted Array in Ascending Order:\n";
printArray(data, size);
}