9.排序（上）

佚名 6年前 (2019-04-15) 随笔 543人围观抢沙发百度已收录

最经典、常用的排序：

提问：插入排序和冒泡排序的时间复杂度相同，都是O(n2),在实际开发中，为什么更倾向于使用插入排序？如何分析一个“排序算法”？ 排序算法的执行效率 1.最好、最坏、平均情况时间复杂度这样区分的原因： 1）有些排序算法会区分，为了好对比。 2）不同有序度的数据对排序执行有影响，我们需要知道排序算法在不同数据下的性能表现。 2.时间复杂度的系数、常数、低阶时间复杂度是反映数据规模n很大时的增长趋势，所以我们会忽略系数、常数、低阶等，但在实际开发中，排序常常可能是10，100，1000这样的规模很小的数据，因此我们也需要把系数、常数、低阶考虑进来。 3.比较次数和交换（或移动）次数基于比较的排序算法的执行过程，会涉及元素比较大小和元素移动或交换，我们所以也需要考虑。 排序算法的内存消耗 算法内存消耗可以用空间复杂度衡量，此外，针对排序算法的空间复杂度，用 原地排序（Sorted in place）特指空间复杂度是O(1)的排序算法。 排序算法的稳定性 稳定性：指待排序的序列中有值相等的元素，在排序后，那些值相等的元素之间的先后顺序不变。例如，2，5，2，7，排序后就是，2，2，5，7，如果，两个2排序后先后顺序不变就是稳定的排序算法。稳定性看起来没用，其实在应用场景中，很多都是根据key进行排序，但相同的key对应的value是不同的。例如希望给一系列订单先按订单金额排序，金额相同的再按订单时间排序。最容易想到的思路是先将订单按金额排序，再遍历订单，将金额相同的再按时间排序。思路简单，但实现困难。而借助稳定性算法，先按订单时间排序，再用稳定排序算法按金额排序就好了。

冒泡排序（Bubble Sort）

经过一次冒泡操作后，6这个元素已经在正确的位置上了，要完成所有的数据排序，只要进行6次冒泡操作。

冒泡优化：当某次冒泡操作没有数据交换时，说明已经达到完全有序，不再需要执行后面的操作，如

冒泡代码：

 1   // 冒泡排序，a 表示数组，n 表示数组大小
 2         public void bubbleSort(int[] a, int n) {
 3           if (n <= 1) return;
 4          
 5          for (int i = 0; i < n; ++i) {
 6             // 提前退出冒泡循环的标志位
 7             boolean flag = false;
 8             for (int j = 0; j < n - i - 1; ++j) {
 9               if (a[j] > a[j+1]) { // 交换
10                 int tmp = a[j];
11                 a[j] = a[j+1];
12                 a[j+1] = tmp;
13                 flag = true;  // 表示有数据交换      
14               }
15             }
16             if (!flag) break;  // 没有数据交换，提前退出
17           }
18         }

1）冒泡排序是原地排序算法吗？是，冒泡过程只涉及了相邻数据的操作，只需要常量级的临时空间，空间复杂度为O(1)。 2）冒泡排序是稳定的排序算法吗？是，冒泡中，两个相等值不交换位置，所以是稳定的。 3）冒泡排序时间复杂度是多少？最好情况下，要排序的数据已经有序，只要进行一次冒泡操作，时间复杂度为O(n)。最坏情况是刚好，倒序排列，需要进行n次冒泡，时间复杂度是O(n2)。

那么平均情况下时间复杂度是多少呢？ n个数据的数组，有n!种排列方式，如果用概率论定量分析平均时间复杂度，会很复杂。通过“有序度”和“逆序度”来分析。有序度就是数组中有序的元素对的个数：有序元素对：a[i] <= a[j], 如果 i < j

完全倒序排列的数组，如6，5，4，3，2，1，有序度是0，完全有序数组，如1，2，3，4，5，6，有序度是n*(n-1)/2,即15，这种完全有序的数组的有序度叫做 满有序度。逆序度，可类比逆序元素对：a[i] > a[j], 如果 i < j。公式：逆序度 = 满有序度 - 有序度排序过程就是增加有序度，减少逆序度的过程，直至满有序度。举例：数组4，5，6，3，2，1，其中，有序元素对有（4，5），（4，6）（5，6），有序度是3，n = 6,满有序度是15。

冒泡操作包含两个子操作比较和交换，每交换一次有序度加1，不管算法怎么改进，交换次数总是确定的，即为逆序度，为n*(n-1)/2 - 初始有序度，此例中为15-3=12。因此最坏的交换次数为n*(n-1)/2 ，最好为0，取中间值表示情况n*(n-1)/4。平均情况下要交换n*(n-1)/4次，比较次数肯定比交换多，因此，平均情况下时间复杂度为O(n2)。这个推导不严谨，但很多时候很实用。 插入排序（Insertion Sort） 有序数组中插入数据，保持有序：

插入排序借助上面的思想实现：先将数据分为两个区间，已排序区间和未排序区间。插入排序算法的核心就是取未排序区间的元素插入到有序区间中，直到未排序区间为空。如下图，左侧是已排序区间，右侧是未排序区间

插入排序也包含两种操作，一种是比较，一种是移动。而移动数等于逆序度，如下图 4，5，6，1，3，2的有序度为5，满有序度为n * (n - 1) / 2 = 15,逆有序度为10。

代码实现：

 1    // 插入排序，a 表示数组，n 表示数组大小
 2                 public void insertionSort(int[] a, int n) {
 3                   if (n <= 1) return;
 4                 
 5                   for (int i = 1; i < n; ++i) {
 6                     int value = a[i];
 7                     int j = i - 1;
 8                     // 查找插入的位置
 9                     for (; j >= 0; --j) {
10                       if (a[j] > value) {
11                         a[j+1] = a[j];  // 数据移动
12                       } else {
13                         break;
14                       }
15                     }
16                     a[j+1] = value; // 插入数据
17                   }
18                 }

1）插入算法是原地排序算法吗？是，插入排序算法运行并不需要额外的存储空间，空间复杂度为O(1)。 2）插入排序算法是稳定的排序算法吗？是，插入排序中，值相同的元素，可以将后面出现的元素插入到前面出现的元素后面。 3）插入排序算法那的时间复杂度是多少？ O(n2),最好是完全有序时，只需要遍历一次，每次比较一次就能确定插入位置，时间复杂度为O(n)。注意，这里是从尾到头遍历有序的数据。如果数组逆序的，每次插入都相当于在数组第一个位置插入新的数据，所以需要移动大量数据，最坏情况时间复杂度为O(n2)。数组中插入一个数据的平均时间复杂度是O(n),对于插入排序，每次插入操作都相当于在数组中插入一个数据，循环执行n次插入操作，所以平均时间复杂度为O（n2）。 选择排序（Selection Sort） 也分排序区间和位排序区间，但是每次选择排序会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

1）选择算法是原地排序算法吗？是，选择排序算法运行并不需要额外的存储空间，空间复杂度为O(1)。 2）选择排序算法是稳定的排序算法吗？不是，选择排序每次都要找剩余未排序元素中最小值，并和前面元素交换位置，破坏了稳定性。 3）选择排序算法那的时间复杂度是多少？最好、最坏、平均时间复杂度都是O(n2)。 开篇解答 冒泡和插入排序不管如何优化，元素交换次数都等于原始数据的逆序度，时间复杂度为O(n2)。但冒泡排序的数据交换比插入排序的数据交换要更复杂，冒泡需要3个复制操作，而插入只需要1个。冒泡排序中数据的交换操作：

 if (a[j] > a[j+1]) { // 交换
       int tmp = a[j];
       a[j] = a[j+1];
       a[j+1] = tmp;
       flag = true;
    }
    
    插入排序中数据的移动操作：
    if (a[j] > value) {
      a[j+1] = a[j];  // 数据移动
    } else {
      break;
    }