内部排序-直接插入排序·冒泡排序·快速排序对比

内部排序-内部排序-直接插入排序·冒泡排序·快速排序对比

写在前面：参考《数据结构（C语言版）》严蔚敏 吴伟民 编著 清华大学出版社 2008年10月第27次印刷

📋 算法概述

直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，它的基本操作是将一个记录插入到已排号序的有序表中，从而得到一个新的、记录数增1的有序表。

冒泡排序（参考书里面叫作起泡排序）（Bubble Sort）。重复地遍历待排序序列，依次比较相邻的两个元素，如果它们的顺序错误就把它们交换过来。每次遍历都会将当前未排序部分的最大（或最小）元素“浮”到顶端，如同水中的气泡一样。

快速排序（Quick Sort）是对起泡排序的一种改进。采用分治法。首先选择一个基准元素，通过一趟排序将待排序列分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小。然后再按此方法对这两部分数据分别进行快速排序，整个过程递归进行。

🎯 算法特点

特性	直接插入排序	冒泡排序	快速排序
核心思想	插入	交换	分治
时间复杂度（平均）	O(n²)	O(n²)	O(n log n)
时间复杂度（最好）	O(n) (序列已基本有序)	O(n) (序列已有序)	O(n log n)
时间复杂度（最坏）	O(n²) (序列逆序)	O(n²) (序列逆序)	O(n²) (基准选择不当，如序列已有序)
空间复杂度	O(1)	O(1)	O(log n) ~ O(n) (递归栈的深度)
稳定性	稳定	稳定	不稳定
排序方式	In-Place (内部排序)	In-Place (内部排序)	In-Place (内部排序)
优点	1. 算法简单。 2. 对基本有序的序列效率极高。 3. 原地排序，空间效率高。	1. 算法极其简单，易于理解。 2. 原地排序，空间效率高。	1. 平均性能极快，是基于比较的内部排序中最好的方法之一。 2. 原地排序，缓存友好。
缺点	平均和最坏情况时间复杂度高，不适合大规模乱序数据。	效率非常低下，移动次数多，实际应用中几乎不被使用。	1. 最坏情况性能较差。 2. 递归实现需要额外的栈空间。 3. 不稳定。
适用场景	1. 数据量较小。 2. 序列基本有序。 3. 作为高级排序算法的子过程（如快速排序优化后的小数组用插入排序）。	主要用于教学，帮助理解排序概念。实际应用中几乎不会被使用。	1. 适用于大规模、乱序的数据集，是应用最广泛的通用排序算法。 2. 对时间复杂度要求高的场景。

🔍 算法原理

待补充

💻 C# 实现代码

🚀示例

using System.Diagnostics;namespace CsharpOne
{internal class Test0912{private delegate void DoSort(List<int> list);public void JustDoIt(){try{List<int> list = new List<int>() { 49, 38, 99, 13, 49, 57 };//list = new List<int>() { 11, 22, 33, 44, 55, 66 };//list = new List<int>();for (int i = 0; i < 10000; i++){list.Add(new Random().Next(1, 10000));//list.Add(i + 100);//list.Add(100000 - i);}Console.WriteLine(string.Join(",", list));List<int> list1 = [.. list];List<int> list2 = [.. list];List<int> list3 = [.. list];DoSort doSort1 = DoStraightInsertionSort;DoSort doSort2 = DoBubbleSort;DoSort doSort3 = DoQuickSort;DoStopwatch(doSort1, list1);DoStopwatch(doSort2, list2);DoStopwatch(doSort3, list3);}catch (Exception ex){Console.WriteLine(ex.Message);Console.WriteLine(ex.StackTrace);}}private void DoStopwatch(DoSort doSort, List<int> list){Stopwatch sw = Stopwatch.StartNew();sw.Start();var memory1 = GC.GetTotalMemory(true);doSort(list);// 通过委托调用排序方法Console.WriteLine($"{doSort.GetType().Name}****{doSort.Method.Name}************************");//Console.WriteLine(string.Join(",", list));var memory2 = GC.GetTotalMemory(true);Console.WriteLine($"memory1:{memory1}, memory2:{memory2}, diff:{memory2 - memory1} bytes");sw.Stop();Console.WriteLine($"time:{sw.ElapsedMilliseconds} ms");}private void DoStraightInsertionSort(List<int> list){StraightInsertionSort(list);}private void DoBubbleSort(List<int> list){BubbleSort(list);}private void DoQuickSort(List<int> list){QuickSort(list, 0, list.Count - 1);// list.Sort();}/// <summary>/// 对 list 直接插入排序 从小到大/// </summary>/// <param name="list">数据列表</param>private void StraightInsertionSort(List<int> list){if (list == null || list.Count == 0) return;/**初始化：49, 38, 99, 13, 49, 57* 第一趟： 38, 49, 99, 13, 49, 57* 第二趟： 38, 49, 99, 13, 49, 57* 第三趟： 38, 49, 空, 99, 49, 57* 第三趟： 38, 空, 49, 99, 49, 57* 第三趟： 空, 38, 49, 99, 49, 57* 第三趟： 13, 38, 49, 99, 49, 57* 第四趟： 13, 38, 49, 49, 99, 57* 第五趟： 13, 38, 49, 49, 57, 99*/for (int i = 1; i < list.Count; i++){int current = list[i];int j = i - 1;// 移动元素而不是交换while (j >= 0 && list[j] > current){list[j + 1] = list[j];j--;}list[j + 1] = current;}}/// <summary>/// 对 list 冒泡排序 从小到大/// </summary>/// <param name="list">数据列表</param>private void BubbleSort(List<int> list){if (list == null || list.Count == 0) return;/**初始化：49, 38, 99, 13, 49, 57* 第一趟： 38, 49, 99, 13, 49, 57* 第一趟： 38, 49, 99, 13, 49, 57* 第一趟： 38, 49, 13, 99, 49, 57* 第一趟： 38, 49, 13, 49, 99, 57* 第一趟： 38, 49, 13, 49, 57, 99* * 第二趟： 38, 49, 13, 49, 57, 99* 第二趟： 38, 13, 49, 49, 57, 99* 第二趟： 38, 13, 49, 49, 57, 99* 第二趟： 38, 13, 49, 49, 57, 99* * 第三趟： 13, 38, 49, 49, 57, 99* 第三趟： 13, 38, 49, 49, 57, 99* 第三趟： 13, 38, 49, 49, 57, 99* * 第四趟： 13, 38, 49, 49, 57, 99* 第四趟： 13, 38, 49, 49, 57, 99* * 第五趟： 13, 38, 49, 49, 57, 99*/int flagData = 0;bool isSort = true;for (int i = 0; i < list.Count - 1; i++){isSort = true;for (int j = 0; j < list.Count - i - 1; j++){if (list[j] > list[j + 1]){isSort = false;flagData = list[j];list[j] = list[j + 1];list[j + 1] = flagData;}}if (isSort)// 若存在一次遍历发现已排序好，则无需继续遍历return;}}/// <summary>/// 对 list 进行快速排序 从小到大/// </summary>/// <param name="list">数据列表</param>/// <param name="left">左侧对比下标</param>/// <param name="right">右侧对比下标</param>private void QuickSort(List<int> list, int left, int right){if (list == null || list.Count == 0 || left < 0 || right >= list.Count) return;/**初始化：49, 38, 99, 13, 49, 57* 第一趟： P                                P位置的在下标为0，指向49* 第一趟： 49, 38, 99, 13, 49, 57*         L                   R    首先移动R①* 第一趟： 49, 38, 99, 13, 49, 57*         L               R         R位置的57不比49小，R左移* 第一趟： 49, 38, 99, 13, 49, 57*         L           R               R位置的49不比49小，R左移* 第一趟： 13, 38, 99, 空, 49, 57*         L           R               R位置的13比49小，相当于将13和49调换位置* 第一趟： 13, 38, 99, 空, 49, 57*             L       R              然后移动L②* 第一趟： 13, 38, 99, 空, 49, 57*                 L   R               L位置的38不比49大，L右移* 第一趟： 13, 38, 空, 99, 49, 57*                 L   R               L位置的99比49大，相当于将99和49调换位置* 第一趟： 13, 38, 49, 99, 49, 57*                 LR                   再次移动R，发现R和L重合（若R和L没有重合就重复步骤①②，直到R和L重合），停止* 第一趟：                                   P（49）左边都是小于49，P（49）右边都是大于或者等于49。返回Pivot = 2* * 递归调用P左边* 第二趟： P                                P位置的在下标为0，指向13* 第二趟： 13, 38                         *         L   R                          首先移动R* 第二趟： 13, 38                         *         LR                              R位置的38不比13小，R左移* 第二趟：                                   发现R和L重合，停止* 第二趟：                                   P（13）左边都是小于13，P（13）右边都是大于或者等于13。返回Pivot = 0** 递归调用P右边* 第三趟： P                                P位置的在下标为0，指向99* 第三趟： 99, 49, 57*         L       R                    首先移动R* 第三趟： 57, 49, 空*         L       R                     R位置的57比99小，相当于将57和99调换位置* 第三趟： 57, 49, 空*             L   R                     然后移动L* 第三趟： 57, 49, 99*                 LR                   发现R和L重合，停止。返回Pivot = 5* * 第四趟： P                                P位置的在下标为0，指向57* 第四趟： 57, 49                         * 第四趟： L   R                          首先移动R* 第四趟： 49, 空                          R位置的49比57小，相当于将49和57调换位置* 第四趟： L   R                          然后移动L* 第四趟： 49, 57                         R位置的49比57小，相当于将49和57调换位置* 第四趟：     LR                         发现R和L重合，停止。返回Pivot = 4* * * 最终修改集合为： 13, 38, 49, 49, 57, 99*/if (left < right){int pivot = GetPivot(list, left, right);// 获取枢轴QuickSort(list, left, pivot - 1);// 对枢轴左侧进行快速排序QuickSort(list, pivot + 1, right);// 对枢轴右侧进行快速排序}}/// <summary>/// 获取枢轴(列表下标)/// </summary>/// <param name="list">数据列表</param>/// <param name="left">左侧对比下标</param>/// <param name="right">右侧对比下标</param>/// <returns></returns>private int GetPivot(List<int> list, int left, int right){int pivot = list[left];while (left < right){while (left < right && list[right] >= pivot){right--;}list[left] = list[right];while (left < right && list[left] < pivot){left++;}list[right] = list[left];}list[left] = pivot;return left; // 返回枢轴位置，列表下标}}
}

代码移位了，截图辅助理解

耗时对比

10000数据，多次调用排序并计时。耗时单位为ms。生成的都是从小到大的顺序。

排序	随机数	随机数	随机数	顺序数	顺序数	顺序数	逆序数	逆序数	逆序数
直接插入排序	489	309	423	16	9	15	779	637	706
冒泡排序	1549	1436	1587	5	2	4	1714	1799	1843
快速排序	8	6	25	369	343	316	328	331	399

---

📝 实践

扩展思考题：

1. 如何修改算法实现降序排序？
2. 使用不同举例感受排序过程、稳定性（11，22，33，44，55或者55，44，33，22，11或者11，33，22，33，22等）？
3. 在实际项目中，什么情况下会选择使用何种排序？