一、冒泡排序的三种表现形式

---

 

---

[【视频】15种排序算法的可视化展示]{.ul}

[视频: 舞动的排序算法
冒泡排序]{.ul}

1.思路

1）比较前后两个数据，如果前面的数据大于后面，则交换

2）第0个数据到第N-1个数据进行一次遍历之后，最大的一个数据沉到数组的最后

3）N=N-1，如果N不为0就重复前面二步，否则排序完成。

第一种实现方法

1. void BubbleSort1(int a[], int n)

2. {

3. int i, j;

4. for (i = 0; i < n; i++)

5. {

6. //长度越来越小

7. for (j = 1; j < n - i; j++)

8. {

9. if (a[j - 1] > a[j])

10. {

11. Swap(&a[j - 1], &a[j]);

12. }

13. }

14. }

15. }

 

第二种实现方法

设置了一个标志，如果某一趟比较没有发生交换，即a[0]<a[1]<a[2]…….<a[n]，则无需在比较了

比第一种更优化时间复杂度为O（1）-O（n^2^）

1. void BubbleSort2(int a[], int n)

2. {

3. int j, k;

4. bool flag;

5. k = n;

6. flag = true;

7. while (flag)

8. {

9. flag = false;

10. for (j = 1; j < k; j++)

11. if (a[j - 1] > a[j])

12. {

13. Swap(&a[j - 1], &a[j]);

14. flag = true;

15. }

16. k–;

17. }

18. }

第三种实现方法

当有100个数，后90个数已经按从小到大排好序，之后前10个数需要排序，则第一趟遍历之后，只需要比较前面10个数就行了

1. void BubbleSort3(int a[], int n)

2. {

3. int j, k;

4. int flag;

5. flag = n;

6. while (flag > 0)

7. {

8. k = flag;

9. flag = 0;

10. for (j = 1; j < k; j++)

11. {

12. if (a[j - 1] > a[j])

13. {

14. Swap(&a[j - 1], &a[j]);

15. //把最后发生交换的位置赋给flag

16. flag = j;

17. }

18. }

19. }

20. }

总结：冒泡排序是一种效率低下的排序方法，在数据规模很小时，可以采用，数据规模比较大时，不适用