Loading... # 算法描述 比较相邻的元素,如果前一个比后一个大,则进行交换。 时间复杂度:O(n²) 空间复杂度:O(1) # 排序过程 假设有n个元素:`6、9、4、5、3、8` 排序的规则:依次比较两个数,如果前者大于后者,则交换。经过一趟排序,第一大的数会被置于底部。 第一趟结果:`6、9、4、5、3、8` 第一趟结果:`6、4、9、5、3、8` 第一趟结果:`6、4、5、9、3、8` 第一趟结果:`6、4、5、6、9、8` 第一趟结果:`6、4、5、6、8、9` 可以看到最大数经过一趟排序已被找到并在所有元素后面,第一趟我们需要比较n-1次才能找出第一大的数,i代表第几趟,所以下方嵌套循环中使用`length -i - 1`,所以经过n-1趟排序后。 # 伪代码实现 ``` void BubbleSort(elements, length){ for(i = 0; i < length; i++){ for(j = 0; j < length -i - 1; j++){ if(elements[j] > elements[j + 1]) Swap(&elements[j], &elements[j + 1]) } } } ``` # C语言实现 ```C #include <stdio.h> #define ARRSIZE(arr) (sizeof(arr) / sizeof(arr[0])) void Swap(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; } void BubbleSort(int elements[], int length) { int flag = 0; //记录排序是否完成 for (int i = 0; i < length; i++) { flag = 0; for (int j = 0; j < length - i - 1; j++) { if (elements[j] > elements[j + 1]) { flag = 1; //这趟循环进行了元素交换 Swap(&elements[j], &elements[j + 1]); } } if (!flag)//如果没有进行元素交换则代表集合已经是有序的,退出循环 break; } } int main(int argc, char const *argv[]) { int elems[] = {3, 4, 2, 1, 5, 9, 2, 1, 0, 22, 33, 5, 112, 11, 22, 55, 22, 61, 97}; int len = ARRSIZE(elems); BubbleSort(elems, len); for (int i = 0; i < len; i++) printf("%4d", elems[i]); printf("\n"); return 0; } ``` ## 程序输出 ``` 0 1 1 2 2 3 4 5 5 9 11 22 22 22 33 55 61 97 112 ``` Last modification:April 11, 2020 © Allow specification reprint Support Appreciate the author AliPayWeChat Like 0 If you think my article is useful to you, please feel free to appreciate
One comment
专业专业,牛逼牛逼