看图说话排序算法之冒泡排序

2018-04-12 本文已影响0人涂印

排序算法的种类非常多，这里总结冒泡排序和对冒泡排序的改进---快速排序的循环实现和递归实现。

一丶冒泡排序

假设待排序的数组A为{7，6，4，8，9，1，2}。冒泡排序的算法原理和何其名字十分的贴切，第一次将最大的数字交换到数组的末尾，第二次将第二大的数交换到数组的末尾的前一个，这样循环交换N-1次后，原数组中的每一个元素都找到了合适的位置，排序完成。

图1 待排序数组
依据算法的思路，第一次应该将最大的数字9交换到数组的末尾。下面按照图例的形式介绍如何将最大的数字9交换到数组的末尾。

取数组的第一个元素(7)，依次和后面的元素进行比较，如果大于后面的元素，则进行交换。

image
指针i+1，和后面的元素比较。如果大于后面的元素，则进行交换。

image
指针i+1继续，重复上述的比较过程。发现7小于8，所以不交换元素位置。

image
指针i+1继续，重复上述比较过程。发现8小于9，同样不交换元素的位置。

image
指针继续i+1，重复上述比较过程，发现9大于1，交换元素位置。

image
指针继续i+1，重复上述比较过程，发现9大于2，交换元素位置。

image

通过上述的六个步骤，可以清晰的看见待排序数组中的最大元素交换到数组的末尾的过程。这六个过程就是一次冒泡交换的过程。通过上述的六个过程，我们不仅需要知道最大的元素冒泡原理，对待排序数组A，还需要提炼出如下的规律：

待排序数组的长度为N，则需要进行N-1次冒泡交换，才能完成对数组的排序操作。
第1次冒泡交换，指在[0,N-1]的下标范围内，将最大元素冒泡交换至A[N-1]处。其中最大交换次数为N-1次。
第i次冒泡交换，指在[0,N-i]的下标范围内，将最大元素冒泡交换至A[N-i]处。其中最大交换次数为N-i次。（1<=i<=N-1）
总共的交换次数为(1+N-1)(N-1)/2,冒泡排序的时间复杂度为O(n²)。
完整的冒泡排序，就是对待排序数组A，进行N-1的冒泡交换。得到排序后的数组。

代码:

public classbubbleSort {
   publicstatic void main(String[] args){
      int[] array = new int[]{7,6,4,8,9,1,2};
      Sort(array);
      for(int i =0;i<array.length;i++){
        System.out.print(array[i]+" ");
      }
   }
   publicstatic void Sort(int []array){
      for(int i = 0;i<array.length;i++){
        for(int j = 0;j<array.length-i-1;j++){
           if(array[j]>array[j+1]){
              int temp =array[j+1];
              array[j+1] = array[j];
              array[j] = temp;
           }
        }
      }
   }
}

二丶冒泡排序改进思路

上述的原理是冒泡排序算法的基本原理和实现，在某些情况下上述的算法是可以进行某种程度的优化的，比如基本有序的数组{9，1，2，3，4，5，6，7}。对于该数组而言，如果采用原始冒泡排序的话，该语句（array[j]>array[j+1]）依然会进行O(n²)的比较。但是我们发现，经过第一次冒泡交换以后，数组就已经有序了，后面的比较都是没有意义的。在这种情况下，可以对冒泡排序进行优化，也就是在基本有序的情况下对冒泡排序进行优化。

设置一个标志位flag，在每次冒泡交换之前置flag=false；如果该次冒泡交换没有进行元素交换，则代表数组已经是有序的了，flag=true。结束排序。

public classbubbleSort {
   publicstatic void main(String[] args){
      int[] array = new int[]{7,6,4,8,9,1,2};
      Sort(array);
      for(int i =0;i<array.length;i++){
        System.out.print(array[i]+" ");
      }
   }
   publicstatic void Sort(int []array){
      boolena flag =false;
      for(int i = 0;i<array.length;i++){
        flag =false;
        for(int j = 0;j<array.length-i-1;j++){
           if(array[j]>array[j+1]){
              false =true;
              int temp =array[j+1];
              array[j+1] = array[j];
              array[j] = temp;
           }
        }
        if(!flag){
           break;
         }
      }
   }
}

Reference:
[1] 数据结构与算法 java语言描述版
[2] 原文博客链接

看图说话排序算法之冒泡排序

代码:

猜你喜欢

热点阅读