冒泡排序(Bubble Sort)
冒泡排序介绍
- 列表每两个相邻的数,如果前面比后面大(升序),则交换这两个数。
- 一趟排序完成后,则无序区减少一个数,有序区增加一个数。
- 时间复杂度:O(n^2)
#include<stdio.h> void Print(int li[], int n) { int i = 0; for (i = 0; i < n; i++) { printf("%d ", li[i]); } printf("n"); } void bubble_sort(int li[], int n) { int i = 0; int j = 0; for (i = 0; i < n - 1; i++) //第i趟 { for (j = 0; j < n - i - 1; j++) { if (li[j] > li[j + 1]) //大于号——>升序,小于号——>降序 { int tmp = li[j]; li[j] = li[j + 1]; li[j + 1] = tmp; } } Print(li, n);//验证 } Print(li, n);//验证 } int main() { int li[] = { 3,5,8,6,9,2,4,1,7 }; int n = sizeof(li) / sizeof(li[0]); bubble_sort(li, n); return 0; }
- 冒泡排序-优化:如果冒泡排序中的一趟排序没有发生交换,则说明列表已经有序,可以直接结束算法。
- 操作:在外重循环增加一个标志位exchange
- 时间复杂度:O(nlogn)
#include<stdio.h> #define FALSE 0 #define TURE 1 void Print(int li[], int n) { int i = 0; for (i = 0; i < n; i++) { printf("%d ", li[i]); } printf("n"); } void bubble_sort(int li[], int n) { int i = 0; int j = 0; for (i = 0; i < n - 1; i++) //第i趟 { int exchange = FALSE; //标志位 for (j = 0; j < n - i - 1; j++) { if (li[j] > li[j + 1]) //大于号——>升序,小于号——>降序 { int tmp = li[j]; li[j] = li[j + 1]; li[j + 1] = tmp; exchange = TURE; } } if (!exchange) { break; } Print(li, n);//验证 } Print(li, n);//验证 } int main() { int li[] = { 7,8,9,1,2,3,4,5,6 }; //冒泡三趟即得到有序列表 int n = sizeof(li) / sizeof(li[0]); bubble_sort(li, n); return 0; }
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
二维码