重生之数据结构与算法—-常见排序算法(一)

简介

排序算法有三个重要的指标：

1. 时间/空间复杂度
   在前面的文章中，虽然经常强调空间换时间能解决大多数问题。但如果时间与空间都比较小，自然是更好的选择。
2. 排序稳定性
   相同的元素，如果排序之后相对位置没有发生改变，那可以被称为稳定排序，否则就是不稳定排序。
   比如说两个相同的数，排序前它们的顺序是 a 在前，b 在后，排序后如果 a 仍然在 b 前面，那么这个排序算法就是稳定的

   Date    OrderId 2025-03-01  1 2025-03-01  2 2025-03-02  1 2025-03-02  1 2025-03-03  1 2025-03-03  2 //根据OrderId降序排序后，依旧根据Data有序排序，这被称为稳定排序。 2025-03-01  2 2025-03-01  1 2025-03-02  2 2025-03-02  1 2025-03-03  2 2025-03-03  1 ... 

3. 是否原地排序
   是否需要额外的空间来辅助排序的过程，比如temp等。对于大数据量的排序来说，原地排序肯定是更优解。

万物的起源：选择排序(SelectionSort)

选择排序是最简单的算法，属于最笨的办法。且不是稳定排序，所以其它排序算法都是基于选择排序的优化。

    public class SelectionSort     {         public static void Run()         {             var arr = new int[] { 5, 7, 1, 8, 6,2,-1,100,15 ,-2};             new SelectionSort().Sort(arr);              foreach (var item in arr)             {                 Console.WriteLine(item);             }         }          /// <summary>         /// 时间复杂度O(n^2)         /// 空间复杂度O(1)         /// </summary>         /// <param name="arr"></param>         public void Sort(int[] arr)         {             //从一个位置开始遍历,找到最小的，然后再找第二小，第三小。             for (int i = 0; i < arr.Length; i++)             {                 for (int j = i+1; j< arr.Length; j++)                 {                     if (arr[i] > arr[j])                     {                         //swap                         var temp = arr[i];                         arr[i] = arr[j];                         arr[j] = temp;                     }                                          }             }         }     } 

进一步优化：冒泡排序(BubbleSort)

上面的选择排序有很多问题：

1. 排序不稳定
   每次都是拿最小元素与当前元素对比，这样可能会改变元素位置
2. 时间复杂度高
   由于嵌套两层for循环，无法突破O(n^2)的限制
3. 有序初素不敏感
   如果初始元素本身就是有序，复杂度依旧是O(n^2)，并没有提前终止。

优化第一步，让排序变稳定

var arr = new int[] {2,2,2,1,3};  [2, (另一个2), (再另外一个2), 1, 3]  //这里可以看到，如果在选择排序中，会发生什么情况呢？ [1, (另一个2), (再另外一个2), 2, 3] 当交换后，2的位置发生了变化。相对之前的位置，它从 (另一个2)之前移动到了(再另外一个2)后。这就破坏了相对位置。 根据定义，同样的元素不应该产生移动，所以我们的代码优化一下，变成这个样子          public void Sort2(int[] arr)         {             for (int i = 0; i < arr.Length; i++)             {                 for (int j = i + 1; j < arr.Length ; j++)                 {                     if (arr[i] > arr[j])                     {                         var temp = arr[i];                         arr[i] = arr[j];                           //主要在这一步，不换位置。而是将元素整体往后移                         //arr[j] = temp;                          for (int k = j; k >i+1 ; k--)                         {                             arr[k] = arr[k - 1];                         }                         arr[i + 1] = temp;                     }                 }             }         } 

这样的话，相同元素的相对位置是没有变化的。保证了相对稳定性！
但又出现了一个新的问题，引入的一个新的for循环，复杂度又退化到了O(n^3)。

优化第二步，复杂度重回O(n^2)

观察上述代码，其核心主要在做两件事。

1. 找到当前循环最小的那个值
2. 填补最小值的空缺，保持排序相对稳定

思考一个问题:有没有一种可能将两步合二为一？找到最小的值的时候交换位置的同时又不影响排序稳定。

        public void Sort3(int[] arr)         {             for (int i = 0; i < arr.Length; i++)             {                 for (int j = 0 ; j < arr.Length-1; j++)                 {                     //当前元素与右边对比大小，并顺带移动位置，这样并不会破坏同元素的相对位置                     //同元素，在左边的始终在左边，不可能移动到右边。                     if (arr[j] > arr[j+1])                     {                         var temp = arr[j + 1];                         arr[j + 1] = arr[j];                         arr[j] = temp;                     }                  }             }         } 

经过这样一优化，复杂度又升级为O(N^2)，同时又具备了排序稳定性。
这就是冒泡排序法，只与相邻元素对比，这样就不会破坏排序稳定性。

优化第三步，有序提前终止

上面的排序算法中，有可能循环几轮后，元素就已经完成了排序，但程序并不知道，还是傻乎乎的完成整个循环。
因此，我们需要当排序完成后，提前终止循环。

        public void Sort4(int[] arr)         {                          for(int i = 0;i < arr.Length; i++)             {                 int notSwapNum = 1;                 for (int j = 0; j < arr.Length-1; j++)                 {                     if (arr[j] > arr[j + 1])                     {                         (arr[j], arr[j + 1]) = (arr[j + 1], arr[j]);                     }                     else                     {                         notSwapNum++;                     }                 }                  //说明元素已经是全部有序的，提前终止循环                 if (notSwapNum == arr.Length)                 {                     break;                 }             }         } 

这就是完整版的冒泡排序，针对选择排序，我们优化了排序稳定性以及在数据有序时提前退出。唯一遗憾的是时间复杂度并没有降低。

倒序对比：插入排序(InsertionSort)

在冒泡排序中，虽然我们能在数组有序时提前提出。但面对如下场景

var arr = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, -1 }; 

冒泡排序还是会完成整个循环，这明显还有很大的优化空间。接下来我们再思考，如何在大部分都有序的情况下完成快速排序。

        public void Sort(int[] arr)         {             for (int i = 0; i < arr.Length; i++)             {                 for (int j = i ; j > 0; j--)                 {                     //与左边已排好序的元素进行对比，因为有序，所以插入很快速。                     //有点类似打扑克，把抓到的牌按序排列                     if (arr[j] < arr[j - 1])                     {                         //swap                         (arr[j], arr[j - 1]) = (arr[j - 1], arr[j]);                     }                     else                     {                         break;                     }                 }              }         } 

与冒泡排序相比，插入排序在面对初始数据有序程度高时，时间复杂度会降低不少，直逼O(n)，但面对完全无序的情况，时间复杂度依旧是O(n^2)。
但总体来说，插入排序的综合性能要高于冒泡排序。

突破O(N^2):希尔排序(ShellSort)

在上面的插入排序中，对数组初始有序度要求很高。所以我们优化的重点就是降低时间复杂度，我们可以通过预处理数据的局部数据，从而突破O(N^2).

希尔排序（Shell Sort），也称为缩小增量排序，是插入排序的一种改进版本。它通过将原始数据分成多个子序列来改善插入排序的性能，使得元素能够更快地移动到它们大致所在的位置，最终完成整个排序过程。

简单来说就是分而治之思想

        public void Sort(int[] arr)         {                          var h = 1;             //根据数组长度确定h高度，也就是分多少组             while (h < arr.Length / 3)             {                 h = h * 3 + 1;             }              while (h >= 1)             {                 //初始化为h,从h开始对比                 for (var i = h; i < arr.Length; i++)                 {                     for (var j = i; j >= h; j = j - h)                     {                         //因为不再是对比相邻元素，所以排序不稳定                         if (arr[j] < arr[j - h])                         {                             (arr[j], arr[j - h]) = (arr[j - h], arr[j]);                         }                         else                         {                             break;                         }                     }                 }                 //完成有序数组分组后，h高度降低                 h = h / 3;              }         } 

不过由于h>1，所以不是对比相邻元素，因此排序失去了稳定性。终究有所取舍

如何证明复杂度突破了O(N^2)？

从代码伤看，循环也一个都没少啊。而且还多了一个算高度的过程，这真的降低了时间复杂度吗？
我也不好解释，使用LeetCode作为佐证吧，前面几个算法都会超时，而希尔排序能成功。
https://leetcode.cn/problems/sort-an-array/submissions/609504025/

插入排序	希尔排序