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

简介

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

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

1.    Date    OrderId
2. 2025-03-01  1
3. 2025-03-01  2
4. 2025-03-02  1
5. 2025-03-02  1
6. 2025-03-03  1
7. 2025-03-03  2
8. //根据OrderId降序排序后，依旧根据Data有序排序，这被称为稳定排序。
9. 2025-03-01  2
10. 2025-03-01  1
11. 2025-03-02  2
12. 2025-03-02  1
13. 2025-03-03  2
14. 2025-03-03  1
15. ...

复制代码

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

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

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

1.     public class SelectionSort
2.     {
3.         public static void Run()
4.         {
5.             var arr = new int[] { 5, 7, 1, 8, 6,2,-1,100,15 ,-2};
6.             new SelectionSort().Sort(arr);
8.             foreach (var item in arr)
9.             {
10.                 Console.WriteLine(item);
11.             }
12.         }
14.         /// <summary>
15.         /// 时间复杂度O(n^2)
16.         /// 空间复杂度O(1)
17.         /// </summary>
18.         /// <param name="arr"></param>
19.         public void Sort(int[] arr)
20.         {
21.             //从一个位置开始遍历,找到最小的，然后再找第二小，第三小。
22.             for (int i = 0; i < arr.Length; i++)
23.             {
24.                 for (int j = i+1; j< arr.Length; j++)
25.                 {
26.                     if (arr[i] > arr[j])
27.                     {
28.                         //swap
29.                         var temp = arr[i];
30.                         arr[i] = arr[j];
31.                         arr[j] = temp;
32.                     }
33.                         
34.                 }
35.             }
36.         }
37.     }

复制代码

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

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

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

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

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

复制代码

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

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

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

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

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

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

复制代码

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

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

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

1.         public void Sort4(int[] arr)
2.         {
3.             
4.             for(int i = 0;i < arr.Length; i++)
5.             {
6.                 int notSwapNum = 1;
7.                 for (int j = 0; j < arr.Length-1; j++)
8.                 {
9.                     if (arr[j] > arr[j + 1])
10.                     {
11.                         (arr[j], arr[j + 1]) = (arr[j + 1], arr[j]);
12.                     }
13.                     else
14.                     {
15.                         notSwapNum++;
16.                     }
17.                 }
19.                 //说明元素已经是全部有序的，提前终止循环
20.                 if (notSwapNum == arr.Length)
21.                 {
22.                     break;
23.                 }
24.             }
25.         }

复制代码

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

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

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

复制代码

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

1.         public void Sort(int[] arr)
2.         {
3.             for (int i = 0; i < arr.Length; i++)
4.             {
5.                 for (int j = i ; j > 0; j--)
6.                 {
7.                     //与左边已排好序的元素进行对比，因为有序，所以插入很快速。
8.                     //有点类似打扑克，把抓到的牌按序排列
9.                     if (arr[j] < arr[j - 1])
10.                     {
11.                         //swap
12.                         (arr[j], arr[j - 1]) = (arr[j - 1], arr[j]);
13.                     }
14.                     else
15.                     {
16.                         break;
17.                     }
18.                 }
20.             }
21.         }

复制代码

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

在上面的插入排序中，对数组初始有序度要求很高。所以我们优化的重点就是降低时间复杂度，我们可以通过预处理数据的局部数据，从而突破O(N^2).
希尔排序（Shell Sort），也称为缩小增量排序，是插入排序的一种改进版本。它通过将原始数据分成多个子序列来改善插入排序的性能，使得元素能够更快地移动到它们大致所在的位置，最终完成整个排序过程。

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

1.         public void Sort(int[] arr)
2.         {
3.             
4.             var h = 1;
5.             //根据数组长度确定h高度，也就是分多少组
6.             while (h < arr.Length / 3)
7.             {
8.                 h = h * 3 + 1;
9.             }
11.             while (h >= 1)
12.             {
13.                 //初始化为h,从h开始对比
14.                 for (var i = h; i < arr.Length; i++)
15.                 {
16.                     for (var j = i; j >= h; j = j - h)
17.                     {
18.                         //因为不再是对比相邻元素，所以排序不稳定
19.                         if (arr[j] < arr[j - h])
20.                         {
21.                             (arr[j], arr[j - h]) = (arr[j - h], arr[j]);
22.                         }
23.                         else
24.                         {
25.                             break;
26.                         }
27.                     }
28.                 }
29.                 //完成有序数组分组后，h高度降低
30.                 h = h / 3;
32.             }
33.         }

复制代码

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

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

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

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！