Java实现冒泡排序算法及对其的简单优化示例

原理

冒泡排序大概是所有程序员都会用的算法,也是最熟悉的算法之一。
它的思路并不复杂:
设现在要给数组arr[]排序,它有n个元素。
1.如果n=1:显然不用排了。(实际上这个讨论似乎没什么必要)
2.如果n>1:
(1)我们从第一个元素开始,把每两个相邻元素进行比较,如果前面的元素比后面的大,那么在最后的结果里面前者肯定排在后面。所以,我们把这两个元素交换。然后进行下两个相邻的元素的比较。如此直到最后一对元素比较完毕,则第一轮排序完成。可以肯定,最后一个元素一定是数组中最大的(因为每次都把相对大的放到后面了)。
(2)重复上述过程,这次我们无需考虑最后一个,因为它已经排好了。
(3)如此直到只剩一个元素,这个元素一定是最小的,那么我们的排序可以结束了。显然,进行了n-1次排序。
上述过程中,每次(或者叫做“轮”)排序都会有一个数从某个位置慢慢“浮动”到最终的位置(画个示意图,把数组画成竖直的就可以看出来),就像冒泡一样,所以,它被称为“冒泡排序法”。

代码实现:

public class BubbleSort{
   public static void main(String[] args){
     int score[] = {67, 69, 75, 87, 89, 90, 99, 100};
     for (int i = 0; i < score.length -1; i++){  //最多做n-1趟排序
       for(int j = 0 ;j < score.length - i - 1; j++){  //对当前无序区间score[0......length-i-1]进行排序(j的范围很关键,这个范围实在逐步缩小的)
         if(score[j] < score[j + 1]){  //把小的值交换到后面
           int temp = score[j];
           score[j] = score[j + 1];
           score[j + 1] = temp;
         }
       }
       System.out.print("第" + (i + 1) + "次排序结果:");
       for(int a = 0; a < score.length; a++){
         System.out.print(score[a] + "\t");
       }
       System.out.println("");
     }
       System.out.print("最终排序结果:");
       for(int a = 0; a < score.length; a++){
         System.out.print(score[a] + "\t");
     }
   }
 }

算法性能/复杂度
我们忽略掉循环变量自增和初始化的时间。先分析算法的比较次数。容易看出,上面这种未经任何改进的冒泡排序无论输入数据如何都会进行n-1轮排序,而每轮排序需要比较的次数从n-1递减到0。那么,总的比较次数即是 (n-1)+(n-2)+...+2+1 = (n-1)n/2≈(n^2)/2。(由于不知道这里如何打出平方,这里,我用n^2代表平方,下同)
再来看下赋值次数。这里的赋值是指其中的交换操作,对于上述代码,1次交换等于三次赋值。由于并非每次都必须交换,因此,赋值操作的次数与输入数据有关。最佳情况(best case)下,即一开始就是有序的情况下,赋值次数为0。 而最坏情况(worst case)下,赋值次数为(n-1)n/2。假设输入数据平均(或者说“完全随机”)分布,那么大约有交换次数为比较次数的一半。由上面的结果,可以得到平均情况(average case)下,赋值次数为 3/2 * (n^2)/2 = 3/4*(n^2).
综上,无论在何种情况下,冒泡排序空间复杂度(额外空间)总是O(1)。

改进
在数据完全有序的时候展现出最优时间复杂度,为O(n)。其他情况下,几乎总是O(n^2)。因此,算法在数据基本有序的情况下,性能最好。
但是,上面的代码怎么可能出现O(n)复杂度呢?实际上,因为上面注重的是基本思路,因此只是最简单情况,要使算法在最佳情况下有O(n)复杂度,需要做一些改进,改进后的代码为:

public static void bubbleSort(int[] arr) {
  int temp = 0;
  boolean swap;
  for (int i = arr.length - 1; i > 0; --i) { // 每次需要排序的长度
    swap=false;
    for (int j = 0; j < i; ++j) { // 从第一个元素到第i个元素
      if (arr[j] > arr[j + 1]) {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swap=true;
      }
    }//loop j
    if (swap==false){
      break;
    }
  }//loop i
}// method bubbleSort

实际上,由于在大量数据的情况下几乎不使用冒泡排序,而使用小数据的时候增加的布尔变量反而会造成额外的开销。所以个人认为上面改进后的算法只是纯理论的,通常,冒泡排序就写前面一种就行了。

算法稳定性
容易看出,在相邻元素相等时,我们并不需要交换它们的位置,所以,冒泡排序是稳定排序。

算法适用场景
冒泡排序思路简单,代码也简单,特别适合小数据的排序。但是,由于算法复杂度较高,在数据量大的时候不适合使用。如果一定要在较多数据的时候使用,最好对算法加以改进,例如选择排序法。

(0)

相关推荐

  • 图文讲解Java中实现quickSort快速排序算法的方法

    相对冒泡排序.选择排序等算法而言,快速排序的具体算法原理及实现有一定的难度.为了更好地理解快速排序,我们仍然以举例说明的形式来详细描述快速排序的算法原理.在前面的排序算法中,我们以5名运动员的身高排序问题为例进行讲解,为了更好地体现快速排序的特点,这里我们再额外添加3名运动员.实例中的8名运动员及其身高信息详细如下(F.G.H为新增的运动员): A(181).B(169).C(187).D(172).E(163).F(191).G(189).H(182) 在前面的排序算法中,这些排序都是由教练主

  • java实现的各种排序算法代码示例

    折半插入排序 折半插入排序是对直接插入排序的简单改进.此处介绍的折半插入,其实就是通过不断地折半来快速确定第i个元素的 插入位置,这实际上是一种查找算法:折半查找.Java的Arrays类里的binarySearch()方法,就是折半查找的实现,用 于从指定数组中查找指定元素,前提是该数组已经处于有序状态.与直接插入排序的效果相同,只是更快了一些,因 为折半插入排序可以更快地确定第i个元素的插入位置 代码: package interview; /** * @author Administrat

  • 堆排序算法的讲解及Java版实现

    堆是数据结构中的一种重要结构,了解了"堆"的概念和操作,可以快速掌握堆排序. 堆的概念 堆是一种特殊的完全二叉树(complete binary tree).如果一棵完全二叉树的所有节点的值都不小于其子节点,称之为大根堆(或大顶堆):所有节点的值都不大于其子节点,称之为小根堆(或小顶堆). 在数组(在0号下标存储根节点)中,容易得到下面的式子(这两个式子很重要): 1.下标为i的节点,父节点坐标为(i-1)/2: 2.下标为i的节点,左子节点坐标为2*i+1,右子节点为2*i+2. 堆

  • 详解堆排序算法原理及Java版的代码实现

    概述 堆排序是一种树形选择排序,是对直接选择排序的有效改进. 堆的定义如下:具有n个元素的序列(k1,k2,...,kn), 当且仅当满足: 时称之为堆.由堆的定义可以看出,堆顶元素(即第一个元素)必为最小项(小顶堆)或最大项(大顶堆). 若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点(有子女的结点)的值均不大于(或不小于)其子女的值,根结点(堆顶元素)的值是最小(或最大)的. (a)大顶堆序列:(96, 83, 27, 38, 11, 09) (b)小顶堆序列:(12, 36,

  • 三种简单排序算法(使用java实现)

    一.冒泡排序 算法思想:遍历待排序的数组,每次遍历比较相邻的两个元素,如果他们的排列顺序错误就交换他们的位置,经过一趟排序后,最大的元素会浮置数组的末端.重复操 作,直到排序完成. 示例演示: 算法实现: for(int i=0;i<array.length-1;i++){//最多排序n-1次 for(int j=0;j<array.length-i-1;j++){//需要交换的次数 if(array[j]>array[j+1]){ int temp=array[j]; array[j]

  • Java实现冒泡排序算法及对其的简单优化示例

    原理 冒泡排序大概是所有程序员都会用的算法,也是最熟悉的算法之一. 它的思路并不复杂: 设现在要给数组arr[]排序,它有n个元素. 1.如果n=1:显然不用排了.(实际上这个讨论似乎没什么必要) 2.如果n>1: (1)我们从第一个元素开始,把每两个相邻元素进行比较,如果前面的元素比后面的大,那么在最后的结果里面前者肯定排在后面.所以,我们把这两个元素交换.然后进行下两个相邻的元素的比较.如此直到最后一对元素比较完毕,则第一轮排序完成.可以肯定,最后一个元素一定是数组中最大的(因为每次都把相对

  • 用java实现冒泡排序算法

    冒泡排序的算法分析与改进 交换排序的基本思想是:两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止. 应用交换排序基本思想的主要排序方法有:冒泡排序和快速排序. 复制代码 代码如下: public class BubbleSort implements SortUtil.Sort{ public void sort(int[] data) { int temp; for(int i=0;i<data.length;i++){ for(int j=data.le

  • 浅析java双向冒泡排序算法

    以整数升序排序为例来简单说明一下双向冒泡排序的过程:首先从前往后把最大数移到最后,然后反过来从后往前把最小的一个数移动到数组最前面,这一过程就是第一轮,然后重复这一过程,最终就会把整个数组从小到大排列好.双向冒泡排序要稍微优于传统的冒泡排序,因为双向排序时数组的两头都排序好了,我们只需要处理数组的中间部分即可,而单向即传统的冒泡排序只有尾部的元素是排好序的,这时每轮处理都需要从头一直处理到已经排好序元素的前面一个元素.虽然它在效率上有了点改进,但它也不能大幅度提高其排序的效率,这是由冒泡排序的基

  • Java实现冒泡排序算法

    冒泡排序: 就是按索引逐次比较相邻的两个元素,如果大于/小于(取决于需要升序排还是降序排),则置换,否则不做改变 这样一轮下来,比较了n-1次,n等于元素的个数:n-2,n-3 ... 一直到最后一轮,比较了1次 所以比较次数为递减:从n-1 到 1 那么总的比较次数为:1+2+3+--+(n-1),  以等差公式计算:(1+n-1)/2*(n-1) ==> n/2*(n-1) ==> (n^2-n) * 0.5 用大O表示算法的时间复杂度:O(n^2) ,  忽略了系数0.5和常数-n. 算

  • 冒泡排序算法及Ruby版的简单实现

    算法原理: 比较相邻的元素.如果第一个比第二个大,就交换他们两个. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.在这一点,最后的元素应该会是最大的数. 针对所有的元素重复以上的步骤,除了最后一个. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较. 实现 假设有这样一个数组: [4, 1, 3, 2] 冒泡排序为从第一个数开始,吧这个数与后面的数比较,如果这个数比后面的大,就交换他们的位置. 比如,第一次比较4和1,发现4比1大,交换 -> [1, 4, 3,

  • Java实现插入排序算法可视化的示例代码

    参考文章 图解Java中插入排序算法的原理与实现 实现效果 示例代码 import java.awt.*; public class AlgoVisualizer { private static int DELAY = 40; private InsertionSortData data; private AlgoFrame frame; public AlgoVisualizer(int sceneWidth, int sceneHeight, int N){ // 初始化数据 data =

  • java数据结构与算法之冒泡排序详解

    本文实例讲述了java数据结构与算法之冒泡排序.分享给大家供大家参考,具体如下: 前面文章讲述的排序算法都是基于插入类的排序,这篇文章开始介绍交换类的排序算法,即:冒泡排序.快速排序(冒泡排序的改进). 交换类的算法:通过交换逆序元素进行排序的方法. 冒泡排序:反复扫描待排序记录序列,在扫描的过程中,顺次比较相邻的两个元素的大小,若逆序就交换位置. 算法实现代码如下: package exp_sort; public class BubbleSort { public static void b

  • Java实现的各种排序算法(插入排序、选择排序算法、冒泡排序算法)

    一.插入排序算法实现java版本 public static int[] insert_sort(int[] a) { for (int i = 0; i < a.length; i++) { for(int j=i+1;j>0&&j<a.length;j--) { if(a[j]<a[j-1]) { int tmp = a[j]; //这样定义初始化逻辑上是可以的,j变量,每次tmp的值变化的 a[j] = a[j-1]; a[j-1] = tmp; } } }

  • java实现的冒泡排序算法示例

    本文实例讲述了java实现的冒泡排序算法.分享给大家供大家参考,具体如下: public class PaoPaixu { public static void sort(int[] data){ int tmp; for (int i = 0; i < data.length; i++) { for (int j = i+1; j < data.length; j++) { if(data[i]>data[j]){ /*tmp=data[i]; data[i]=data[j]; dat

  • Java数据结构和算法之冒泡排序(动力节点Java学院整理)

    冒泡排序(Bubble Sort)是一种简单的排序算法.它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端. 冒泡排序算法的运作如下: 1. 比较相邻的元素.如果第一个比第二个大,就交换他们两个. 2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.在这一点,最后的元素应该会是最大的数. 3. 针对所有

随机推荐