首页 > 代码库 > 排序算法---冒泡排序

排序算法---冒泡排序

一、简介

        冒泡排序:重复地走访要排序的数列,一次比较相邻的两个元素,如果他们的顺序错误(取决于升序还是降序)就把他们的位置进行交换。一直到数列中元素顺序不在需要交换。算法的名字由来是因为较大(或较小)的元素会经由比较交换位置慢慢浮到数列的顶端,像是气泡浮出水面,故名。

二、算法原理

       在内部循环中就是一个冒泡,从头到尾,比较左右两个,如果逆序就交换位置,最大的那一项会一直被交换,直到排最后。1,2比较,(交换),2,3比较,3和4比较,4和5比较。这里的数字指的是位置,假如2是5个数据中最大的一个,1和2比较,不变,2和3比较,二者交换位置,最大值到了3位置,3和4比较,最大值到了4位置,再到5位置。冒泡,冒上来,如此循环,直到数列中的所有元素顺序正确。

技术分享

由它的特性可以知道,它的运算次数为(n-1)+(n-1)+....+1 = (n-2)(n-1)/2,它的时间复杂度是O(n^2)

三、代码实现

private static int[] bubbleSort(int[] arr) {
 
    for(int i = 0; i < arr.length-1; i ++){//外层循环 循环次数为数组的长度-1
            for(int j =0; j < arr.length-i-1; j ++){//内层循环 比较相邻元素 每次比较次数都减少i个
                    if(arr[j]<arr[j+1]){//按从大到小的顺序
                    int temp = 0;
                    temp  =  arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                   }
            }
    }
    return arr;
}

  

总结:冒泡排序是比较简单的排序算法,但是由于它是循环比较,所以效率比较低。

排序算法---冒泡排序