十大排序算法——冒泡排序

主要思想：

外层循环从1到n-1，内循环从当前外层的元素的下一个位置开始，依次和外层的元素比较，出现逆序就交换。

Java实现代码：

public class Bubble {
    public static void main(String[] args) {
        int[ ] array = new int[]{2, 3, 5, 8, 9, 0, 4, 5, 1, 6, 8, 7};
        sort(array);
        System.out.println(Arrays.toString(array));

    }
    private static void sort(int[] array) {
        int n = array.length;
        for (int i = 0; i < n-1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (array[j] < array[i]) {
                    int temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                }
            }
        }
    }
}

C实现代码：

//从小到大排n个个数
void Bubble() 
{ 
      for(int i=1;i<n;i++) 
      { 
        for(int j=0;i<n-i;j++) 
         { 
              if(a[j]>a[j+1])//比较交换相邻元素 
               { 
                   int temp; 
                   temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; 
               } 
         } 
      } 
} 

最优复杂度：

当输入数组就是排好序的时候，复杂度为O(n)，而快速排序在这种情况下会产生
O(n²)的复杂度。

最差复杂度：

当输入数组为倒序时，复杂度为O(n²) ，适用于排序小列表。