数据结构与算法从零开始系列：冒泡排序

2019-11-06 09:49:43

字体：大中小

来源：转载

供稿：网友

本篇内容包含

冒泡排序的介绍冒泡排序的C的实现冒泡排序的java的实现冒泡排序的时间复杂度的计算

冒泡排序的介绍

冒泡排序从文字上理解不明思议就是河塘里的水，从地上冒泡上来到水面，下面有两张图很贴切的说明冒泡排序

这张图就是将数字12，35，99，18，76竖起来，然后从底部有一个气泡，圈住第一个数，然后自己上面的一个数对比，如果比上面小就交换，最后能将最小数12换到第一个数上，然后再经过同样的操作，从底部的气泡开始，到12之前的数结束，可以将18交换到12的前面

这张图模拟了冒泡排序的整个过程，数字横着放，第一个红色框表示气泡，两个红色框表示比较大小，而黑色框表示已经排好的数字，最后排成有序的数字

冒泡排序的C的实现

这里加了一个flag作为优化程序的条件，如果程序未进入内循环，说明数字已经排序好了，这个时候就可以退出外循环，直接程序结束，减少了剩余部分排序的循环

#include<stdio.h>void bubbleSort(int arr[],int n){ int i,j,flag; for (i = 1; i < n; i++) { flag = 0; for (j = 0; j < n-i; j++) { if(arr[j]<arr[j+1]){ int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; flag =1; } } if(flag == 0)break; }}void main(){ int i; int arr[10] = {1, 4, 8, 3, 2, 9, 5, 0, 7, 6}; bubbleSort(arr, 10); for(i=0; i<10; i++){ PRintf("%d,", arr[i]); }}

冒泡排序的Java的实现

public class BubbleSort { public void bubbleSort(int[] arr,int n){ boolean flag; for (int i = 1; i < n; i++) { flag = false; for (int j = 0; j < n-i; j++) { if(arr[j]<arr[j+1]){ int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; flag =true; } } if(!flag)break; } } public static void main(String[] args) { int[] arr = {1, 4, 8, 3, 2, 9, 5, 0, 7, 6}; BubbleSort sort = new BubbleSort(); sort.bubbleSort(arr, arr.length); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i]+","); } }}