冒泡排序,顾名思义就像水中的气泡一样,气泡越大,上浮的越快。
以整数数组为例,数值越大的元素我们就认为它越应该出现在数组的右边,这样就构成了一个递增数组。
对于含有n个元素的数组values,我们每次从左向右扫描出一个最大的,可以得知,经过n-1次扫描我们即可得到一个有序数组。
c++版本:
#include <iostream> #include <stdlib.h> #include <time.h> void buddle_sort(int a[], int n) { for (int i = 0; i < n - 1; ++i) for (int j = 0; j < n - i - 1; ++j) if (a[j] > a[j + 1]) { int tmp = a[j]; a[j] = a[j + 1]; a[j + 1] = tmp; } } void print(int a[], int n) { for (int i = 0; i < n; ++i) std::cout << a[i] << " "; std::cout << std::endl; } int main() { ::srand(::time(NULL)); const int num = 40; int a[num] = {0}; for (int i = 0; i < num; ++i) a[i] = ::rand() % 10; buddle_sort(a, num); print(a, num); return 0; }
该排序算法是稳定的,时间复杂度是O(n2)
附上go语言版本
package main import "fmt" import "math/rand" import "time" func buddle_sort(values []int) { for i := 0; i < len(values)-1; i++ { for j := 0; j < len(values)-i-1; j++ { if values[j] > values[j+1] { values[j], values[j+1] = values[j+1], values[j] } } } } func main() { values := make([]int, 10) fmt.Print(len(values), " ", cap(values), "\n") rand.Seed(int64(time.Now().Nanosecond())) for i := 0; i < len(values); i++ { values[i] = rand.Int() % 10 } buddle_sort(values) for _, v := range values { fmt.Print(v, " ") } fmt.Println() }