欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  网络运营

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

程序员文章站 2022-06-22 17:25:51
说明:前几节我们特意讲了几种重要的基本数据结构数组,队列,栈,链表,以及基本的代码实现,从现在起,我们来学习一下典型的排序算法,只有不断的努力,不断的尝试,我们的技术才能做到极致. 1>提出问题?什么是冒泡排序? 冒泡排序:针对一系列数据,只会进行前后数据进行比较,在比较的同时,如果满足大小关系不互换位置,如果不满足大小关系,则2数据进行互换,根据这个原理......

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

   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