数据结构排序算法实验报告_数据结构与算法(8)(上)：冒泡排序、插入排序和选择排序...

(文中图片出自王争老师的课程:数据结构与算法之美，侵删）

今天主要学习冒泡排序，插入排序和选择排序。

我们分析一个排序算法主要从以下方面入手：

一.排序算法的执行效率

1.最好、最坏、平均情况时间复杂度

2.时间复杂度的系数、常数和低阶

3.比较次数和移动次数

二.排序算法的内存消耗

内存消耗主要通过空间复杂度来衡量，同时还引入一个新的概念--原地排序。原地排序算法特指空间复杂度是O(1)的排序算法。

三.排序算法的稳定性

衡量算法的一个重要因素就是稳定性。如果带排序元素中存在值相等的元素，经过排序之后，原有的相等元素顺序不变，成为稳定的排序算法。反之，则是不稳定的排序算法。

冒泡排序

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。如下图所示：

元素到达最后的状态，是经过了6次这样的冒泡操作(最后一次是和自己比较)。

实际上，冒泡过程可以优化。当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作。如下图6个元素，值需要4次冒泡操作。

因此，我们把它翻译成代码就是

public void bubbleSorts(int[] a,int n){
   if(n<=1) return;
   for(int i=0;i<n-1;i++){
      boolean flag = false;
      for(int j=0;j<n-i-1;j++){
           if(a[j] > a[j+1]){
              int temp = a[j];
              a[j] = a[j+1];
              a[j+1] = temp;
              flag = true;
           }else{
              break;
           }
      }
      if(!flag){
        break;
      }
   }  
}

通过冒泡排序的原理，我们可以确定：

冒泡排序是原地排序算法，它只涉及相邻元素的交换，需要常量级的内存空间，所以空间复杂度是O(1)。

冒泡排序是稳定的排序算法。在排序过程中，只有前后两个元素不等才会交换顺序，相等的时候不做交换，因此没有改变原有相等数据的顺序。

冒泡排序的时间复杂度，

假设待排序的元素本身就是有序的，那么只需要一次冒泡，即最好时间复杂度为O(n)。

假设待排序的元素本身是倒序的，那么就需要n次冒泡，时间复杂度为O(

)。

平均情况时间度的计算就稍微复杂一点。假设有n个数据的数组，就有n！种排列方式，不同的排列方式，对应的冒泡次数肯定不同。我们可以通过 有序度 和 逆序度 来进行分析。

有序度的情况是

a[i] <= a[j] ,  i<j;

如图所示，下图的有序度等于11.

逆序度的情况则是

a[i] > a[j], i < j;

一个完全有序的数组，有序度等于 n!=(n*(n-1))/2，以6个数据数组为例就是15。此时的有序度叫做满有序度。排序的过程即是减少逆序度，增加有序度，直到最后达到满有序度的过程。

逆序度 = 满有序度 - 有序度

以n个数据的数组为例，有序度为0的时候，需要进行 n*(n-1)/2次交换，平均交换次数取中间值n*(n-1)/4，那么平均时间复杂度就是O(

)。

插入排序

插入排序实现排序思想：

将需要的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，也就是第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

如图所示，要排序的数据是 4，5，6，1，3，2，其中左侧为已排序区间，右侧是未排序区间。

根据以上原理，我们可以用代码实现插入排序

public void insertSorts(int[] a,int n){
   if(n<=1) return;
   for(int i=1;i<n;i++){
      int data = a[i];
      int j = i-1;
      for(;j>=0;j--){
         if(a[j] > data){
           a[j+1] = a[j];
         }else{
           break;
         }
      }
      a[j+1] = data;
   }   
}

根据以上可以发现，插入排序和冒泡排序一样，是原地排序算法，同时也是稳定行排序算法，时间复杂度为O(

)。

选择排序

选择排序的原理和插入排序的原理类似，分为已排序区间和未排序区间。不同的是，选择排序是在未排序区间里选择最小的元素，将其放在已排序区间的尾部。

根据可以写出下列代码：

public void selectSorts(int[] a,int n){
    if(n<=1) return;
    for(int i=0;i<n-1;i++){
        int min=i;
        for(int j=i+1;j<n;j++){
           if(a[j] < a[min]){
              min = j;
           }
        }
        int temp = a[i];
        a[i] = a[min];
        a[min] = temp;
    } 
 
}

首先，选择排序空间复杂度为 O(1)，是一种原地排序算法。选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为 O(n2)。

但是选择排序不是稳定排序，选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。因此一般在排序中，选择排序的效率是低于冒泡和插入排序的。

那冒泡排序和插入排序的效率哪个更高一点呢？

从我们写的代码来看

//冒泡
 int temp = a[j];
 a[j] = a[j+1];
 a[j+1] = temp;
 
//插入
 a[j+1] = a[j];

冒泡执行了三次交换，而插入只执行了一次，因此，理论上讲插入排序效率高于冒泡排序的。