当前位置：首页 > news >正文

【简单实用框架】【十大排序算法直接调用】【可移植】

news 2025/7/2 14:07:05

☀️博客主页：CSDN博客主页
💨本文由 萌萌的小木屋 原创，首发于 CSDN💢
🔥学习专栏推荐：面试汇总
❗️游戏框架专栏推荐：游戏实用框架专栏
⛅️点赞 👍 收藏 ⭐留言 📝，如有错误请指正

📆 未来很长，值得我们全力奔赴更美好的生活✨

------------------❤️分割线❤️-------------------------

Unity 小科普

老规矩，先介绍一下Unity的科普小知识：

Unity 是行业领先的实时3D开发平台。
包括游戏开发，电影，AR/VR，虚拟现实在内的所有创作者，可以将梦想照进现实。
Unity提供了一套完整完善的软件解决方案，可用于创作，运营和模拟任何2D和3D的内容，进本全平台支持。
实际上Unity就是一个游戏引擎，大名鼎鼎的原神就是用它制作的。

MGameFrame：慢慢积累的属于自己的框架

目的：自己工作期间凭当前水准自己写的代码框架，持续更新中，方便以后自己使用，现在开源，需要自取

需求：工程中，经常会使用到排序函数，但是每次去搜索，可能最常见的就是冒泡排序，现自己总结了所有的排序，方便自己在工程中快速的使用

十大排序

冒泡，插入，归并，桶，基数，二叉树，选择，希尔，堆，快速

参考链接

参考学习

注意事项

可以直接复制源码，也可以从我的GitCode中自取

源码

using System;
using System.Collections.Generic;
public class SortTool
{//整体参考：https://blog.csdn.net/weixin_43199474/article/details/93067441?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522167782546316800215039843%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=167782546316800215039843&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-1-93067441-null-null.142^v73^insert_down2,201^v4^add_ask,239^v2^insert_chatgpt&utm_term=%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E5%8F%8A%E5%85%B6%E5%A4%8D%E6%9D%82%E5%BA%A6&spm=1018.2226.3001.4187#region 冒泡排序/// <summary>/// 冒泡排序（优化版本）/// 时间复杂度:最差：O(n^2)，最好O(n)/// 空间复杂度:O(1)/// https://blog.csdn.net/qq_48718409/article/details/120866840?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522167782824716800222841549%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=167782824716800222841549&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-1-120866840-null-null.142^v73^insert_down2,201^v4^add_ask,239^v2^insert_chatgpt&utm_term=%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E5%AE%9E%E7%8E%B0&spm=1018.2226.3001.4187/// </summary>/// <param name="list"></param>public static void BubbleSort(List<int> list){bool flag = false;for (int i = 0; i < list.Count - 1; i++){flag = false;for (int j = 0; j < list.Count - 1 - i; j++){if (list[j] > list[j + 1]){int temp = list[j];list[j] = list[j + 1];list[j + 1] = list[j];flag = true;}}if (flag == false){break;}}}#endregion#region 插入排序/// <summary>/// 插入排序/// 时间复杂度:最差：O(n^2)，最好O(n)/// 空间复杂度:O(1)/// https://blog.csdn.net/qq_48718409/article/details/120866840?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522167782824716800222841549%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=167782824716800222841549&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-1-120866840-null-null.142^v73^insert_down2,201^v4^add_ask,239^v2^insert_chatgpt&utm_term=%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E5%AE%9E%E7%8E%B0&spm=1018.2226.3001.4187/// </summary>/// <param name="list"></param>public static void InsertSort(List<int> list){for (int i = 1; i < list.Count; i++){ //控制循环轮数int temp = list[i]; //定义待交换元素int j; //定义待插入的位置for (j = i; j > 0 && temp < list[j - 1]; j--){list[j] = list[j - 1];}list[j] = temp;}}#endregion #region 归并排序/// <summary>/// 归并排序/// 时间复杂度:O(nlog(n))/// 空间复杂度:O(n)</summary>/// https://www.cnblogs.com/chengxiao/p/6194356.html/// <param name="list"></param>public static void MergerSort(List<int> list){int[] temp = new int[list.Count];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间sort(list, 0, list.Count - 1, temp);}private static void sort(List<int> list, int left, int right, int[] temp){if (left < right){int mid = (left + right) / 2;sort(list, left, mid, temp);//左边归并排序，使得左子序列有序sort(list, mid + 1, right, temp);//右边归并排序，使得右子序列有序merge(list, left, mid, right, temp);//将两个有序子数组合并操作}}private static void merge(List<int> list, int left, int mid, int right, int[] temp){int i = left;//左序列指针int j = mid + 1;//右序列指针int t = 0;//临时数组指针while (i <= mid && j <= right){if (list[i] <= list[j]){temp[t++] = list[i++];}else{temp[t++] = list[j++];}}while (i <= mid){//将左边剩余元素填充进temp中temp[t++] = list[i++];}while (j <= right){//将右序列剩余元素填充进temp中temp[t++] = list[j++];}t = 0;//将temp中的元素全部拷贝到原数组中while (left <= right){list[left++] = temp[t++];}}#endregion#region 桶排序/// <summary>/// 归并排序/// 时间复杂度:O(N+M)，近似O(N)/// 空间复杂度:O(N+M)/// https://www.cnblogs.com/skywang12345/p/3602737.html/// </summary>/// <param name="list"></param>public static void BucketSort(List<int> list, int maxVal){int[] buckets;if (list == null || maxVal < 1)return;// 创建一个容量为max的数组buckets，并且将buckets中的所有数据都初始化为0。buckets = new int[maxVal];// 1. 计数for (int i = 0; i < list.Count; i++)buckets[list[i]]++;// 2. 排序for (int i = 0, j = 0; i < maxVal; i++){while ((buckets[i]--) > 0){list[j++] = i;}}buckets = null;}#endregion#region 基数排序/// <summary>/// 基数排序/// 时间复杂度:O( k*n ) ；其中k为常数，n为元素个数；/// 空间复杂度:（10 × length）= O （length）/// https://www.cnblogs.com/skywang12345/p/3603669.html/// </summary>/// <param name="list"></param>public static void RadixSort(List<int> list){int exp;    // 指数。当对数组按各位进行排序时，exp=1；按十位进行排序时，exp=10；...int max = getMax(list);    // 数组a中的最大值// 从个位开始，对数组a按"指数"进行排序for (exp = 1; max / exp > 0; exp *= 10)countSort(list, exp);}/// <summary>/// 获取数组a中最大值/// </summary>/// <param name="list"></param>/// <returns></returns>private static int getMax(List<int> list){int mlistx;mlistx = list[0];for (int i = 1; i < list.Count; i++)if (list[i] > mlistx)mlistx = list[i];return mlistx;}/** 对数组按照"某个位数"进行排序(桶排序)** 参数说明：*     a -- 数组*     exp -- 指数。对数组a按照该指数进行排序。** 例如，对于数组a={50, 3, 542, 745, 2014, 154, 63, 616}；*    (01) 当exp=1表示按照"个位"对数组a进行排序*    (02) 当exp=10表示按照"十位"对数组a进行排序*    (03) 当exp=100表示按照"百位"对数组a进行排序*    ...*/private static void countSort(List<int> list, int exp){//int output[list.length];    // 存储"被排序数据"的临时数组int[] output = new int[list.Count];    // 存储"被排序数据"的临时数组int[] buckets = new int[10];// 将数据出现的次数存储在buckets[]中for (int i = 0; i < list.Count; i++)buckets[(list[i] / exp) % 10]++;// 更改buckets[i]。目的是让更改后的buckets[i]的值，是该数据在output[]中的位置。for (int i = 1; i < 10; i++)buckets[i] += buckets[i - 1];// 将数据存储到临时数组output[]中for (int i = list.Count - 1; i >= 0; i--){output[buckets[(list[i] / exp) % 10] - 1] = list[i];buckets[(list[i] / exp) % 10]--;}// 将排序好的数据赋值给list[]for (int i = 0; i < list.Count; i++)list[i] = output[i];output = null;buckets = null;}#endregion#region 二叉树排序//待更新#endregion#region 选择排序/// <summary>/// 选择排序/// 时间复杂度:O(N^2)/// 空间复杂度:O(N^2)/// https://blog.csdn.net/zhuo_wp/article/details/78223481?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522167783001016800213086400%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=167783001016800213086400&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-2-78223481-null-null.142^v73^insert_down2,201^v4^add_ask,239^v2^insert_chatgpt&utm_term=C%23%20%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F&spm=1018.2226.3001.4187/// </summary>/// <param name="list"></param>public static void SelectionSort(int[] array){for (int i = 0; i < array.Length - 1; i++){int minValueIndex = i;for (int j = i + 1; j < array.Length; j++){if (array[minValueIndex] > array[j]){minValueIndex = j;}}if (minValueIndex != i){Exchange(ref array[i], ref array[minValueIndex]);}}}private static void Exchange(ref int x, ref int y){int temp = x;x = y;y = temp;}private static void Exchange<T>(ref T x, ref T y){T temp = x;x = y;y = temp;}#endregion#region 希尔排序/// <summary>/// 希尔排序（移动法）:先选择区间在用插入排序/// 时间复杂度:O(N^2)/// 空间复杂度:O(N^2)/// https://www.cnblogs.com/chengxiao/p/6104371.html/// </summary>/// <param name="list"></param>public static void XierSortForMove(List<int> list){//增量gap，并逐步缩小增量for (int gap = list.Count / 2; gap > 0; gap /= 2){//从第gap个元素，逐个对其所在组进行直接插入排序操作for (int i = gap; i < list.Count; i++){int j = i;int temp = list[j];if (list[j] < list[j - gap]){while (j - gap >= 0 && temp < list[j - gap]){//移动法list[j] = list[j - gap];j -= gap;}list[j] = temp;}}}}private static void XierSwap(List<int> list, int a, int b){list[a] = list[a] + list[b];list[b] = list[a] - list[b];list[a] = list[a] - list[b];}/// <summary>/// 希尔排序（交换法）:先选择区间在用插入排序/// 时间复杂度:O(N^2)/// 空间复杂度:/// https://www.cnblogs.com/chengxiao/p/6104371.html/// </summary>/// <param name="list"></param>public static void XierSortForSwap(List<int> list){//增量gap，并逐步缩小增量for (int gap = list.Count / 2; gap > 0; gap /= 2){//从第gap个元素，逐个对其所在组进行直接插入排序操作for (int i = gap; i < list.Count; i++){int j = i;while (j - gap >= 0 && list[j] < list[j - gap]){//插入排序采用交换法XierSwap(list, j, j - gap);j -= gap;}}}}#endregion#region 堆排序/// <summary>/// 堆排序/// 时间复杂度:O(nlogn)/// 空间复杂度:O(1)/// https://blog.csdn.net/qq_35552025/article/details/77995524?ops_request_misc=&request_id=&biz_id=102&utm_term=%E5%A0%86%E6%8E%92%E5%BA%8F%20C&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-1-77995524.142^v73^insert_down2,201^v4^add_ask,239^v2^insert_chatgpt&spm=1018.2226.3001.4187#%E5%AE%9E%E7%8E%B0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-1-77995524.142^v73^insert_down2,201^v4^add_ask,239^v2^insert_chatgpt/// </summary>/// <param name="list"></param>public static void HeapSort(List<int> list){//将最大的值推到堆顶//x根据最后一个子节点的位置计算出父节点int x = Convert.ToInt32(Math.Floor(Convert.ToDouble((list.Count - 2) / 2)));for (int i = x; i >= 0; i--){//如果子元素只存在左子元素是 让右子元素等于左子元素while (list[i] < list[i * 2 + 1] || list[i] < list[(i * 2 + 2) > (list.Count - 1) ? (i * 2 + 1) : i * 2 + 2]){if (list[i * 2 + 1] >= list[(i * 2 + 2) > (list.Count - 1) ? (i * 2 + 1) : i * 2 + 2]){int index = list[i];list[i] = list[i * 2 + 1];list[i * 2 + 1] = index;}else{int index = list[i];list[i] = list[i * 2 + 2];list[i * 2 + 2] = index;}}}//输出堆顶最大的元素int max = list[0];list[0] = list[list.Count - 1];Console.Write("{0}\t", max);//将数组中的最后一个元素删除List<int> num = new List<int>(list.Count - 1);for (int j = 0; j < list.Count - 1; j++){num[j] = list[j];}Adjust(num);}public static void Adjust(List<int> list){if (list.Count > 1){HeapSort(list);}}#endregion#region 快速排序/// <summary>/// 快速排序/// 时间复杂度:O(nlogn)/// 空间复杂度:O(1)/// https://blog.csdn.net/enternalstar/article/details/106932822?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522167783146916800188592132%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=167783146916800188592132&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-2-106932822-null-null.142^v73^insert_down2,201^v4^add_ask,239^v2^insert_chatgpt&utm_term=C%23%20%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F&spm=1018.2226.3001.4187/// </summary>/// <param name="list"></param>public void QuickSort(List<int> list, int lo, int hi){if (lo > hi)//递归退出条件{return;}int i = lo;int j = hi;int temp = list[i];//取得基准数，空出一个位置while (i < j)//当i=j时推出，表示temp左边的数都比temp小，右边的数都比temp大{while (i < j && temp <= list[j])//从后往前找比temp小的数，将比temp小的数往前移{j--;}list[i] = list[j];//将比基准数小的数放在空出的位置，j的位置又空了出来while (i < j && temp >= list[i])//从前往后找比temp大的数，将比temp大的数往后移{i++;}list[j] = list[i];//将比基准数大的数放在hi空出来的位置,如此，i所在的位置又空了出来}list[i] = temp;QuickSort(list, lo, i - 1);//对lo到i-1之间的数再使用快速排序，每次快速排序的结果是找到了基准数应该在的位置//其左边的数都<=它，右边的数都>=它，它此时在数组中的位置就是排序好时其应该在的位置。QuickSort(list, i + 1, hi);//对i+1到hi之间的数再使用快速排序}#endregion
}