数据结构之冒泡排序

冒泡排序(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 高虎 数据结构之冒泡排序

 上一篇
数据结构之插入排序 数据结构之插入排序
基本思想:在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。 插入排序是最简单的排序算法,插入排序最差的复杂度是
下一篇 
编程珠玑 编程珠玑
计算机编程充满乐趣。有时候,它是一门优雅的科学,有时候,它要去开发和使用新的软件工具。编程与人息息相关:客户实际想解决什么问题? ① 二维数组中的查找题目描叙:在一个二维数组中, 每一行都按照 从左到右递增的顺序排序,每一列都 按照从上
  目录