13.排序：经典排序算法原理解析与对比

之前章节我们学到了二分查找法，使用二分查找法要求原数组必须有序。所以，排序问题也是我们常见的一类问题。本章节我们就来学习常见的4种排序算法，包括冒泡排序、插入排序、归并排序以及快排序。

13-1 什么是排序问题

排序，就是让一组无序数组变成有序的过程(一般默认有序都是从小到大的排列顺序)，下面我们来讲讲如何判断不同的排序算法优劣

• 1.时间复杂度：具体包括最好时间复杂度，最坏时间复杂度以及平均时间复杂度
• 2.空间复杂度：如果空间复杂度为1，也叫做原地排序
• 3.稳定性：排序的稳定性是指相等的数据对象，在排序后，顺序是否能保证不变

13-2 常见的排序算法及其思想

13-2-1 冒泡排序

• 1.冒泡排序的原理

从第一个数据开始，依次比较相邻元素的大小。如果前者大于后者，则进行交换操作，把大的元素往后交换。通过多轮迭代，直到没有交换操作为止。冒泡排序就像是一个水池中数据处理一样，每次会把最大的那个数据传递到最后

• 2.冒泡排序的性能

冒泡排序最好时间复杂度为O(n),也就是当输入数组刚好是顺序的时候，只需要挨个比较一遍就行，不需要做交换操作，所以时间复杂度为O(n).

冒泡排序最坏时间复杂度会比较惨，是O(nn).也就是说，当数组刚好是完全逆序的时候，每轮排序都需要挨个比较n次，并且重复n次，所以时间复杂度为O(nn)

当输入组杂乱无序时，它的平均时间复杂度也是O(n*n)

冒泡排序不需要额外的空间，所以空间复杂度为O(1),冒泡排序过程中，当元素相同时不做交换，所以冒泡排序是稳定排序算法

 function main(){
   let arr = [1,0,3,4,5,-6,7,8,9,10];
   document.write(`原始数据${arr}`);
   let isAsc = true;
   for(let i = 1; i < arr.length; i++){
     //第一层循环
     for(let j = 0; j< arr.length - i;j++){
       //第二层循环，转换数字类型
       console.log(Number(arr[j]) , Number(arr[j+1]))
       //比较前后两个数据大小，符合条件则交换位置
       if(Number(arr[j]) > Number(arr[j+1])){
         let temp = arr[j];
         arr[j] = arr[j+1];
         arr[j+1] = temp;
       }
     }
   }
   document.write(`冒泡排序${arr}`);
 }

13-2-2 插入排序

• 1.插入排序的原理

选取未排序元素，插入到已排序区间的合适位置，直到未排序区间为空，插入排序顾名思义，就是从左到右维护一个已经排好序的序列。直到所有的待排数据全部完成插入动作。

• 2.插入排序的性能
  • 插入排序最好时间复杂度为O(n),即当数组刚好是完全顺序时，每次只用比较一次就能找到正确的位置，这个过程重复n次，就可以清空未排区间
  • 插入排序最坏时间复杂度则需要O(nn).即当数组刚好完全逆序时，每次都要比较n次才能找到正确位置，这个过程重复n次，就可以清空未排序区间，所以最坏时间复杂度为O(nn)
  • 插入排序的平均时间复杂度为O(nn),这是因为往数组插入一个元素的平均时间复杂度为O(n),而插入排序可以理解为重复n次的数组插入操作，所以平均时间复杂度为O(nn)
  • 插入排序不需要开辟额外的空间，所以时间复杂度是O(1)

 function main(){
   let arr = [2,3,5,1,23,6,78,34];
   document.write(`原始数据${arr}`);
   //i应该从1开始，j-i为0
   for(let i = 1;i < arr.length;i++){
     //数组循环体
     var temp = arr[i];//取当前值为对比标准值
     var j = i - 1;//向前比较
     //与数组之前的元素做比较
     for(;j>=0;j--){
       //如果当前的arr[j]大于arr[i],则应该交换位置
       if(Number(arr[j] > Number(temp))){
         //arr[j+1]与arr[j]交换位置,这里是j+1 和j交换，不是和temp做交换
         arr[j+1] = arr[j];
       }else{
         //否则，跳出循环
         break
       }
     };
     //此时的j应该是循环里面最后一个值，如果符合，就是最小的值，比如i-2，0等，如果不符合，则是i-1;
     arr[j+1] = temp;
   }
   document.write(`插入排序结果${arr}`);
 }

小结：插入排序与冒泡排序算法的异同点

• 1.相同点

  • 插入排序和冒泡排序的平均时间复杂度都是O(n*n),且都是稳定的排序算法，都属于原地排序

• 2.差异点

  • 冒泡排序每轮交换操作都是动态的，所以需要三个赋值操作才能完成
  • 而插入排序每轮交换动作会固定待插入的数据，因此只需要一步赋值操作

以上两种排序算法都比较简单，通过这种算法可以帮助我们对排序的思想建立基本了解，接下来再介绍一些时间复杂度更低的排序算法，它们的时间复杂度可以达到O(nlogn)

13-2-3 归并排序

• 1.归并排序的原理

归并排序的原理其实就是我们上一课时讲的分治法，它首先将数组不断的二分，直到最后每个部分只包含1个数据。然后再对每个部分分别进行排序，最后将排序好的相邻两部分合并在一起，这样整个数组就有序了。

• 2.归并排序的性能

对于归并排序，它采用了二分迭代方式，复杂度为logn
每次的迭代，需要两个有序数组进行合并，这样的动作在O(n)的时间复杂度下可以完成。因此，归并排序的复杂度是二者的乘积O(nlogn).同时，它的执行频次与输入序列无关，因此，归并排序最好，最坏，平均时间复杂度都是O(nlogn).

空间复杂度方面，由于每次合并的操作都需要开辟基于数组的临时内存空间，所以空间复杂度为O(n).归并排序合并的时候，相同元素的前后顺序不变，所以归并排序是稳定的排序算法

13-2-4 快速排序

• 1.快速排序的原理

快速排序法的原理也是分治法，它的每轮迭代，会选取数组中任意一个数据做为分区点，将小于它的元素放在左侧，大于它的放在右侧，再利用分治思想，继续分别对左右两侧进行同样的操作，直到每个区间缩小为1，则完成排序。

• 2.快速排序的性能

在快排的最好时间复杂度下，如果每次选取分区点时，都能选中中位数，把数组等分为两个，那么此时时间复杂度和归并一样，都是O(nlogn)

在最坏时间复杂度下，也就是如果每次分区都选中了最小值和最大值，得到不均等的两组，那么就需要n次的分区操作，每次分区平均扫描n/2个元素，此时时间复杂度就是O(n*n)了

快速排序法在大部分情况下，统计上是很难选到极端情况的，因此它平均的时间复杂度是O(nlogn)

快速排序法在空间方面，使用了交换法，因此空间复杂度为O(1)

很显然，快速排序的分区过程及交换操作，所以快排是不稳定的排序算法

13-3 排序算法的性能分析

• 排序最暴力的方法，时间复杂度就是O(n*n),这恰如冒泡排序和插入排序
• 当我们利用算法思维去解决问题时，就会想到使用分治法，此时，利用归并排序就能让时间复杂度降至O(nlogn).然而，归并排序需要额外开辟空间，一方面是为了稳定性，一方面是在归并时，由于在数组中插入元素导致了数据移挪问题。
• 为了规避因此带来的时间损耗，此时我们采用快速排序。可以解决插入元素导致的移挪问题，而且降低了不必要的空间开销，但是由于二分交换数据，会导致得到的结果并不稳定。

13-4 总结

• 冒泡排序，插入排序，归并排序，快速排序；这些算法没有好坏之分，只是各有利弊，工作中可以根据实际情况选择最优算法
• 如果对数据规模比较小的数据进行排序，可以选择时间复杂度为O(nn)的排序算法。因为当数据结构小时，O(nn)和O(nlogn)的差距只要几十毫秒，实际影响不大。
• 但对于数据规模较大但数据进行排序时，就需要选择时间复杂度为O(nlogn)的排序算法
• 归并排序的空间复杂度为O(n),也就意味着但排序100M的数据时，就需要200M的空间，所以对空间资源消耗会很多
• 快速排序的平均时间复杂度为O(nlogn),但是如果分区选择的不好的话，最坏时间复杂度也有可能逼近O(n*n).而且快速排序不具备稳定性，这样需要看你所面对的问题是否有稳定性的要求