数据结构之冒泡排序

冒泡排序(Bubble Sort)也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。

走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

算法步骤

1)比较相邻的元素。如果第一个比第二个大,就交换他们两个。

2)对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。

3)针对所有的元素重复以上的步骤,除了最后一个。

4)持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较

算法实现(java):

public class BubbleSort {
    public static void main(String[] args) {
        int[] a={2,6,4,9,1,0,8,3};
        bubbleSort(a);
        for(int i=0;i<a.length;i++){
            System.out.println(a[i]);
        }
    }
    public static void bubbleSort(int[] a){
        int i,j;
        for(i=0;i<a.length;i++){
            for(j=1;j<a.length-i;j++){
                if(a[j-1]>a[j]){
                    int temp=a[j];
                    a[j]=a[j-1];
                    a[j-1]=temp;
                }
            }
        }
    }

}

算法分析:

时间复杂度:

在最好情况下,即要排序的数组本身就是有序的,则其时间复杂度为Θ(n);
在最坏的情况下,即要排序的数组是逆序的,其时间复杂度为Θ(n2)。

空间复杂度:

很明显,其空间复杂度为Θ(1)。

稳定性:

冒泡排序是稳定的


  转载请注明: Hi 高虎 数据结构之冒泡排序

 上一篇
数据结构之选择排序 数据结构之选择排序
基本思想:在要排序的一组数中,选出最小的一个数与第一个位置的数交换;然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。 选择排序(Selection sort)也是一种简单直观的排序算法。 选择排
下一篇 
java集合框架 java集合框架
java集合框架① 定义:集合(collection)就是一个存储一组对象的容器对象,一般将这些对象称为集合的元素(element),Java集合框架支持三种类型的集合:规则集(set),线性表(list)和图(map),他们分别定义在接口
2016-07-27
  目录