数据结构与算法(冒泡排序比拼插入排序)

 说明:前几节我们特意讲了几种重要的基本数据结构数组,队列,栈,链表,以及基本的代码实现,从现在起,我们来学习一下典型的排序算法,只有不断的努力,不断的尝试,我们的技术才能做到极致.

   1>提出问题?什么是冒泡排序?

            冒泡排序:针对一系列数据,只会进行前后数据进行比较,在比较的同时,如果满足大小关系不互换位置,如果不满足大小关系,则2数据进行互换,根据这个原理,每次进行冒泡都会找到一个大元素,比如第一次冒泡找到第一大元素,第2次冒泡找到底2大元素,经过n次冒泡, 

      列子:用冒泡排序排序4，5，6，3，2，1从小到大进行排序.

     解释：上图中是经过第一次冒泡排序的示意图,通过图中可以看出,,经过第一次冒泡排序就可以找到该序列的最大数据,为达到数据的有序性,必须经过6次的冒泡排序.结构图如下所示.

关于冒泡排序还有另一种说法,那就是根据数学知识来进行计算,即有序度,满有序度,逆有序度的关系进行计算

        有序度满足的关系是  a[i] <= a[j]  i<j

        逆有序度满足的关系是  a[i] > a[j] i<j

       比如数据：4,5,6,3,2,1,即有序度的个数分布是(4,5),(4,6),(5,6)所以有序度是3,逆序度的个数是:(4,3)(4,2)(4,1),(5,3)(5,2)(5,1)(6,3)(6,2)(6,1)(3,2)(3,1)(2,1)，即逆虚度=12

     满有序度则是数据在经过排序之后,满足a[i] <=a[j]且i<j   如456321在经过排序后为1,2,3,4,5,6,则满有序度为n(n-1) /2=15

     总结得出满有序度= 有序度+逆序度，在进行冒泡排序的过程就是增加有序度的过程, 每交换一次数据,有序度就增加1,则该数据的冒泡排序交换数据的次数是15-3=12;即数据的交换次数=满有序度-初始有序度.

   2>应该怎样分析冒泡排序的时间复杂度呢？

      分析冒泡排序的时间复杂度我们应该从这几个角度分析:最好,最坏,是否是稳定,是否是原地排序

           冒泡排序在排序期间,只需要交换前后的数据，且只需要常量级的临时空间,所以时间复杂度为O(1)，所以冒泡排序是原地排序

        冒泡排序在排序期间,如果前后数据相等，不需要做数据的交换,所以冒泡排序是稳定排序

      冒泡排序在排序期间,如果数据是有序的,我们只需要经过一次冒泡排序数据就是有序的,所以在最好的情况下,时间复杂度为O(1),当数据完全无序,倒序的，这种情况下，我们需要进行n次冒泡,最坏情况下时间复杂度为O(n^2)

   3>冒泡排序的的java代码实现

public  class Bubble{
   
 public void bub(int[] items){
   int n = items.length()
   for(int i=0;i<=n;i++){
     for(int j=0;j<n-i-1;j++){
        boolean flag = false;如果数据是有序的，则提前退出冒泡排序,该是标志
        if(items[j] > items[j+1])
        int tmp = items[j]
        itms[j] = items[j+1]
        items[j+1] = tmp
        flag = true;表示有数据交换
    }
  }
   if(!flag) break;
 }
}

  4>插入排序

        插入排序的思想是将已经存在的数组分为2个区间，一个是已排序区间和未排序区间,初始的已排序区间是数组中的第一个数字,插入排序的核心思想是，在未排序的区间取出元素，和已经排序的区间的每一个元素做数据比较,插入到已经排序区间的对应位置,直到未排序区间的数据为空为止.

      我们用图来解说下插入排序的思想；

解释:插入排序也包含2种操作,一种是元素的比较,一种是元素的移动,当我们要将数据a插入到已经排序的区间,需要拿数据a与已经排序区间的数据一一比较,插入到合适的位置,插入入点需要腾出位置空间,a才可以插入,插入排序也可用有序度，逆虚度，满有序度解释,

    5>插入排序的复杂度分析.

         插入排序在排序区间,不需要额外的存储空间,所以插入排序是原地排序

        插入排序在排序区间,当2个数据相等时候，前后原有的位置不互换,所以插入排序是稳定排序,

       当所需要排序的数据是有序的,需要将这些数据遍历一遍,所以最好的情况下，插入排序的时间复杂度为O(n)，

        当排序的数据是完全无序,每次想当与需要将插入的数据插入到已经排序区间的第一个位置,需要大量的数据移动，所以插入排序最坏情况下，时间复杂度为O(n^2)

   6>实现插入排序的java代码.

public void insertsort(int[] a,int n){
    if(n<=1) return;
    for(int i=1;i<n;++i){
       int value = a[i];
       int j=j-1;
//查找插入的位置
         for(;j>=0;--j){
           if(a[j]>value){
             a[j+1] =a[j];//数据的移动
         }else{
               break;
        }
       }
   a[j+1] = value;//插入数据
       
}

}

  总结:为什么插入排序比冒泡排序更收到人们的欢呢？

              2者的时间复杂度都是O(n^2)，，且都是原地，稳定排序,不管怎么优化,数据的交换次数总是等于原始数据的逆序度,插入排序不管怎么优化,数据的移动次数总是等于原始数据的逆序度,这是因为在代码实现中,冒泡排序需要3次的赋值操作,而插入排序仅仅只需要一次的赋值操作,而赋值操作也是需要一定时间的 ，所以一定数据量的前提下，插入时间的赋值时间远远小于冒泡排序的赋值时间，所以插入排序更受到欢迎....

本文地址：https://blog.csdn.net/w5201314ws6123/article/details/85961575