各种排序算法汇总

目录

简介

交换排序

冒泡排序

快速排序

插入排序

直接插入排序

希尔排序

选择排序

简单选择排序

堆排序

归并排序

基数排序

总结

简介

排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序。若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。

将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程叫做排序。假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

交换排序

冒泡排序

已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先比较a[1]与a[2]的值，若a[1]大于a[2]则交换两者的值，否则不变。再比较a[2]与a[3]的值，若a[2]大于a[3]则交换两者的值，否则不变。再比较a[3]与a[4]，以此类推，最后比较a[n-1]与a[n]的值。这样处理一轮后，a[n]的值一定是这组数据中最大的。再对a[1]~a[n-1]以相同方法处理一轮，则a[n-1]的值一定是a[1]~a[n-1]中最大的。再对a[1]~a[n-2]以相同方法处理一轮，以此类推。共处理n-1轮后a[1]、a[2]、……a[n]就以升序排列了。降序排列与升序排列相类似，若a[1]小于a[2]则交换两者的值，否则不变，后面以此类推。 总的来讲，每一轮排序后最大（或最小）的数将移动到数据序列的最后，理论上总共要进行n(n-1）/2次交换。

代码实现

 1         /// <summary>  2         /// 冒泡排序  3         /// </summary>  4         /// <param name="arry">要排序的整数数组</param>  5         public static void BubbleSort(this int[] arry)  6         {  7             for (int i = 0; i < arry.Length; i++)  8             {  9                 for (int j = 0; j < arry.Length - 1 - i; j++) 10                 { 11                     //比较相邻的两个元素，如果前面的比后面的大，则交换位置 12                     if (arry[j] > arry[j + 1]) 13                     { 14                         int temp = arry[j + 1]; 15                         arry[j + 1] = arry[j]; 16                         arry[j] = temp; 17                     } 18                 } 19             } 20         }

简单测试

 1     class Program  2     {  3         static void Main(string[] args)  4         {  5             int[] arry = new int[] { 1, 2, 3, 4, 1, -1 };  6             arry.BubbleSort();  7             for (int i = 0; i < arry.Length; i++)  8             {  9                 Console.Write("/t" + arry[i]); 10             } 11             Console.Read(); 12         } 13     }

结果

这里采用的是为整型数组添加扩展方法实现的冒泡排序。

优点：稳定

缺点：慢，每次只移动相邻的两个元素。

时间复杂度：理想情况下（数组本来就是有序的），此时最好的时间复杂度为o(n),最坏的时间复杂度(数据反序的)，此时的时间复杂度为o(n*n) 。冒泡排序的平均时间负责度为o(n*n).

快速排序

代码实现

 1         /// <summary>  2         /// 快速排序  3         /// </summary>  4         /// <param name="arry">要排序的数组</param>  5         /// <param name="left">低位</param>  6         /// <param name="right">高位</param>  7         public static void QuickSort(this int[] arry, int left, int right)  8         {  9             //左边索引小于右边，则还未排序完成    10             if (left < right) 11             { 12                 //取中间的元素作为比较基准，小于他的往左边移，大于他的往右边移    13                 int middle = arry[(left + right) / 2]; 14                 int i = left - 1; 15                 int j = right + 1; 16                 while (true) 17                 { 18                     //移动下标，左边的往右移动，右边的向左移动 19                     while (arry[++i] < middle && i < right); 20                     while (arry[--j] > middle && j > 0); 21                     if (i >= j) 22                         break; 23                     //交换位置 24                     int number = arry[i]; 25                     arry[i] = arry[j]; 26                     arry[j] = number; 27  28                 } 29                 QuickSort(arry, left, i - 1); 30                 QuickSort(arry, j + 1, right); 31             } 32         }

简单测试

 1         static void Main(string[] args)  2         {  3             int[] arry = new int[] { 34,1,221,50,44,58,12,1,1};  4             //arry.BubbleSort();  5             arry.QuickSort(0, arry.Length-1 );  6             for (int i = 0; i < arry.Length; i++)  7             {  8                 Console.Write("/t" + arry[i]);  9             } 10             Console.Read(); 11         }

结果

插入排序

直接插入排序

代码实现

 1         /// <summary>  2         /// 直接插入排序  3         /// </summary>  4         /// <param name="arry">要排序的数组</param>  5         public static void InsertSort(this int[] arry)  6         {  7             //直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的  8             for (int i = 1; i < arry.Length; i++)  9             { 10                 //如果当前元素小于其前面的元素 11                 if (arry[i] < arry[i - 1]) 12                 { 13                     //用一个变量来保存当前待比较的数值，因为当一趟比较完成时，我们要将待比较数值置入比它小的数值的后一位  14                     int temp = arry[i]; 15                     int j = 0; 16                     for (j = i - 1; j >= 0 && temp < arry[j]; j--) 17                     { 18                         arry[j + 1] = arry[j]; 19                     } 20                     arry[j + 1] = temp; 21                 } 22             } 23         }

测试

 1         static void Main(string[] args)  2         {  3             int[] arry = new int[] { 34,1,221,50,44,58,12};  4             //arry.BubbleSort();  5             //arry.QuickSort(0, arry.Length-1 );  6             arry.InsertSort();  7             for (int i = 0; i < arry.Length; i++)  8             {  9                 Console.Write("/t" + arry[i]); 10             } 11             Console.Read(); 12         }

结果

希尔排序

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。

基本思想

代码实现

 1         /// <summary>  2         /// 希尔排序  3         /// </summary>  4         /// <param name="arry">待排序的数组</param>  5         public static void ShellSort(this int[] arry)  6         {  7             int length = arry.Length;  8             for (int h = length / 2; h > 0; h = h / 2)  9             { 10                 //here is insert sort 11                 for (int i = h; i < length; i++) 12                 { 13                     int temp = arry[i]; 14                     if (temp < arry[i - h]) 15                     { 16                         for (int j = 0; j < i; j += h) 17                         { 18                             if (temp<arry[j]) 19                             { 20                                 temp = arry[j]; 21                                 arry[j] = arry[i]; 22                                 arry[i] = temp; 23                             } 24                         } 25                     } 26                 } 27             } 28         }

测试

 1         static void Main(string[] args)  2         {  3             int[] arry = new int[] { 34,1,221,50,44,58,12};  4             //arry.BubbleSort();  5             //arry.QuickSort(0, arry.Length-1 );  6             //arry.InsertSort();  7             arry.ShellSort();  8             for (int i = 0; i < arry.Length; i++)  9             { 10                 Console.Write("/t" + arry[i]); 11             } 12             Console.Read(); 13         }

结果

选择排序

简单选择排序

设所排序序列的记录个数为n。i取1,2,…,n-1,从所有n-i+1个记录（Ri,Ri+1,…,Rn）中找出排序码最小的记录，与第i个记录交换。执行n-1趟 后就完成了记录序列的排序。

在简单选择排序过程中，所需移动记录的次数比较少。最好情况下，即待排序记录初始状态就已经是正序排列了，则不需要移动记录。最坏情况下，即待排序记录初始状态是按逆序排列的，则需要移动记录的次数最多为3（n-1）。简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。当i=1时，需进行n-1次比较；当i=2时，需进行n-2次比较；依次类推，共需要进行的比较次数是(n-1)+(n-2)+…+2+1=n(n-1)/2，即进行比较操作的时间复杂度为O(n^2)，进行移动操作的时间复杂度为O(n)。

代码实现

 1         /// <summary>  2         /// 简单选择排序  3         /// </summary>  4         /// <param name="arry">待排序的数组</param>  5         public static void SimpleSelectSort(this int[] arry)  6         {  7             int tmp = 0;  8             int t = 0;//最小数标记  9             for (int i = 0; i < arry.Length; i++) 10             { 11                 t = i; 12                 for (int j = i + 1; j < arry.Length; j++) 13                 { 14                     if (arry[t] > arry[j]) 15                     { 16                         t = j; 17                     } 18                 } 19                 tmp = arry[i]; 20                 arry[i] = arry[t]; 21                 arry[t] = tmp; 22             } 23         }

测试

 1         static void Main(string[] args)  2         {  3             int[] arry = new int[] { 34,1,221,50,44,58,12};  4             //arry.BubbleSort();  5             //arry.QuickSort(0, arry.Length-1 );  6             //arry.InsertSort();  7             //arry.ShellSort();  8             arry.SimpleSelectSort();  9             for (int i = 0; i < arry.Length; i++) 10             { 11                 Console.Write("/t" + arry[i]); 12             } 13             Console.Read(); 14         }

结果

堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

代码实现

 1         /// <summary>  2         /// 堆排序  3         /// </summary>  4         /// <param name="arry"></param>  5         public static void HeapSort(this int[] arry, int top)  6         {  7             List<int> topNode = new List<int>();  8   9             for (int i = arry.Length / 2 - 1; i >= 0; i--) 10             { 11                 HeapAdjust(arry, i, arry.Length); 12             } 13  14             for (int i = arry.Length - 1; i >= arry.Length - top; i--) 15             { 16                 int temp = arry[0]; 17                 arry[0] = arry[i]; 18                 arry[i] = temp; 19                 HeapAdjust(arry, 0, i); 20             } 21         } 22         /// <summary> 23         /// 构建堆 24         /// </summary> 25         /// <param name="arry"></param> 26         /// <param name="parent"></param> 27         /// <param name="length"></param> 28         private static void HeapAdjust(int[] arry, int parent, int length) 29         { 30             int temp = arry[parent]; 31  32             int child = 2 * parent + 1; 33  34             while (child < length) 35             { 36                 if (child + 1 < length && arry[child] < arry[child + 1]) child++; 37  38                 if (temp >= arry[child]) 39                     break; 40  41                 arry[parent] = arry[child]; 42  43                 parent = child; 44  45                 child = 2 * parent + 1; 46             } 47  48             arry[parent] = temp; 49         }

测试

 1         static void Main(string[] args)  2         {  3             int[] arry = new int[] { 34,1,221,50,44,58,12};  4             //arry.BubbleSort();  5             //arry.QuickSort(0, arry.Length-1 );  6             //arry.InsertSort();  7             //arry.ShellSort();  8             //arry.SimpleSelectSort();  9             arry.HeapSort(arry.Length); 10             for (int i = 0; i < arry.Length; i++) 11             { 12                 Console.Write("/t" + arry[i]); 13             } 14             Console.Read(); 15         }

结果

归并排序

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并过程为：比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。

代码实现

 1         /// <summary>  2         /// 归并排序  3         /// </summary>  4         /// <param name="arry"></param>  5         /// <param name="first"></param>  6         /// <param name="last"></param>  7         public static void MergeSort(this int[] arry, int first, int last)  8         {  9             if (first + 1 < last) 10             { 11                 int mid = (first + last) / 2; 12                 MergeSort(arry, first, mid); 13                 MergeSort(arry, mid, last); 14                 Merger(arry, first, mid, last); 15             } 16         } 17         /// <summary> 18         /// 归并 19         /// </summary> 20         /// <param name="arry"></param> 21         /// <param name="first"></param> 22         /// <param name="mid"></param> 23         /// <param name="last"></param> 24         private static void Merger(int[] arry, int first, int mid, int last) 25         { 26             Queue<int> tempV = new Queue<int>(); 27             int indexA, indexB; 28             //设置indexA，并扫描subArray1 [first,mid] 29             //设置indexB,并扫描subArray2 [mid,last] 30             indexA = first; 31             indexB = mid; 32             //在没有比较完两个子标的情况下，比较 v[indexA]和v[indexB] 33             //将其中小的放到临时变量tempV中 34             while (indexA < mid && indexB < last) 35             { 36                 if (arry[indexA] < arry[indexB]) 37                 { 38                     tempV.Enqueue(arry[indexA]); 39                     indexA++; 40                 } 41                 else 42                 { 43                     tempV.Enqueue(arry[indexB]); 44                     indexB++; 45                 } 46             } 47             //复制没有比较完子表中的元素 48             while (indexA < mid) 49             { 50                 tempV.Enqueue(arry[indexA]); 51                 indexA++; 52             } 53             while (indexB < last) 54             { 55                 tempV.Enqueue(arry[indexB]); 56                 indexB++; 57             } 58             int index = 0; 59             while (tempV.Count > 0) 60             { 61                 arry[first + index] = tempV.Dequeue(); 62                 index++; 63             } 64         }

测试

 1         static void Main(string[] args)  2         {  3             int[] arry = new int[] { 34,1,221,50,44,58,12};  4             //arry.BubbleSort();  5             //arry.QuickSort(0, arry.Length-1 );  6             //arry.InsertSort();  7             //arry.ShellSort();  8             //arry.SimpleSelectSort();  9             //arry.HeapSort(arry.Length); 10             arry.MergeSort(0, arry.Length); 11             for (int i = 0; i < arry.Length; i++) 12             { 13                 Console.Write("/t" + arry[i]); 14             } 15             Console.Read(); 16         }

结果

基数排序

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

代码实现

 1         /// <summary>  2         /// 基数排序  3         /// 约定:待排数字中没有0,如果某桶内数字为0则表示该桶未被使用,输出时跳过即可  4         /// </summary>  5         /// <param name="arry">待排数组</param>  6         /// <param name="array_x">桶数组第一维长度</param>  7         /// <param name="array_y">桶数组第二维长度</param>  8         public static void RadixSort(this int[] arry, int array_x = 10, int array_y = 100)  9         { 10             /* 最大数字不超过999999999...(array_x个9) */ 11             for (int i = 0; i < array_x; i++) 12             { 13                 int[,] bucket = new int[array_x, array_y]; 14                 foreach (var item in arry) 15                 { 16                     int temp = (item / (int)Math.Pow(10, i)) % 10; 17                     for (int l = 0; l < array_y; l++) 18                     { 19                         if (bucket[temp, l] == 0) 20                         { 21                             bucket[temp, l] = item; 22                             break; 23                         } 24                     } 25                 } 26                 for (int o = 0, x = 0; x < array_x; x++) 27                 { 28                     for (int y = 0; y < array_y; y++) 29                     { 30                         if (bucket[x, y] == 0) continue; 31                         arry[o++] = bucket[x, y]; 32                     } 33                 } 34             } 35  36         }

测试

 1         static void Main(string[] args)  2         {  3             int[] arry = new int[] { 34,1,221,50,44,58,12};  4             //arry.BubbleSort();  5             //arry.QuickSort(0, arry.Length-1 );  6             //arry.InsertSort();  7             //arry.ShellSort();  8             //arry.SimpleSelectSort();  9             //arry.HeapSort(arry.Length); 10             //arry.MergeSort(0, arry.Length); 11             arry.RadixSort(); 12             for (int i = 0; i < arry.Length; i++) 13             { 14                 Console.Write("/t" + arry[i]); 15             } 16             Console.Read(); 17         }

结果

总结

整数数组各种排序算法扩展类

  1     /// <summary>   2     /// 排序辅助类   3     /// </summary>   4     public static class SortExtention   5     {   6         /// <summary>   7         /// 冒泡排序   8         /// </summary>   9         /// <param name="arry">要排序的整数数组</param>  10         public static void BubbleSort(this int[] arry)  11         {  12             for (int i = 0; i < arry.Length; i++)  13             {  14                 for (int j = 0; j < arry.Length - 1 - i; j++)  15                 {  16                     //比较相邻的两个元素，如果前面的比后面的大，则交换位置  17                     if (arry[j] > arry[j + 1])  18                     {  19                         int temp = arry[j + 1];  20                         arry[j + 1] = arry[j];  21                         arry[j] = temp;  22                     }  23                 }  24             }  25         }  26         /// <summary>  27         /// 快速排序  28         /// </summary>  29         /// <param name="arry">要排序的数组</param>  30         /// <param name="left">低位</param>  31         /// <param name="right">高位</param>  32         public static void QuickSort(this int[] arry, int left, int right)  33         {  34             //左边索引小于右边，则还未排序完成     35             if (left < right)  36             {  37                 //取中间的元素作为比较基准，小于他的往左边移，大于他的往右边移     38                 int middle = arry[(left + right) / 2];  39                 int i = left - 1;  40                 int j = right + 1;  41                 while (true)  42                 {  43                     //移动下标，左边的往右移动，右边的向左移动  44                     while (arry[++i] < middle && i < right) ;  45                     while (arry[--j] > middle && j > 0) ;  46                     if (i >= j)  47                         break;  48                     //交换位置  49                     int number = arry[i];  50                     arry[i] = arry[j];  51                     arry[j] = number;  52   53                 }  54                 QuickSort(arry, left, i - 1);  55                 QuickSort(arry, j + 1, right);  56             }  57         }  58         /// <summary>  59         /// 直接插入排序  60         /// </summary>  61         /// <param name="arry">要排序的数组</param>  62         public static void InsertSort(this int[] arry)  63         {  64             //直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的  65             for (int i = 1; i < arry.Length; i++)  66             {  67                 //如果当前元素小于其前面的元素  68                 if (arry[i] < arry[i - 1])  69                 {  70                     //用一个变量来保存当前待比较的数值，因为当一趟比较完成时，我们要将待比较数值置入比它小的数值的后一位   71                     int temp = arry[i];  72                     int j = 0;  73                     for (j = i - 1; j >= 0 && temp < arry[j]; j--)  74                     {  75                         arry[j + 1] = arry[j];  76                     }  77                     arry[j + 1] = temp;  78                 }  79             }  80         }  81         /// <summary>  82         /// 希尔排序  83         /// </summary>  84         /// <param name="arry">待排序的数组</param>  85         public static void ShellSort(this int[] arry)  86         {  87             int length = arry.Length;  88             for (int h = length / 2; h > 0; h = h / 2)  89             {  90                 //here is insert sort  91                 for (int i = h; i < length; i++)  92                 {  93                     int temp = arry[i];  94                     if (temp < arry[i - h])  95                     {  96                         for (int j = 0; j < i; j += h)  97                         {  98                             if (temp < arry[j])  99                             { 100                                 temp = arry[j]; 101                                 arry[j] = arry[i]; 102                                 arry[i] = temp; 103                             } 104                         } 105                     } 106                 } 107             } 108         } 109         /// <summary> 110         /// 简单选择排序 111         /// </summary> 112         /// <param name="arry">待排序的数组</param> 113         public static void SimpleSelectSort(this int[] arry) 114         { 115             int tmp = 0; 116             int t = 0;//最小数标记 117             for (int i = 0; i < arry.Length; i++) 118             { 119                 t = i; 120                 for (int j = i + 1; j < arry.Length; j++) 121                 { 122                     if (arry[t] > arry[j]) 123                     { 124                         t = j; 125                     } 126                 } 127                 tmp = arry[i]; 128                 arry[i] = arry[t]; 129                 arry[t] = tmp; 130             } 131         } 132         /// <summary> 133         /// 堆排序 134         /// </summary> 135         /// <param name="arry"></param> 136         public static void HeapSort(this int[] arry, int top) 137         { 138             List<int> topNode = new List<int>(); 139  140             for (int i = arry.Length / 2 - 1; i >= 0; i--) 141             { 142                 HeapAdjust(arry, i, arry.Length); 143             } 144  145             for (int i = arry.Length - 1; i >= arry.Length - top; i--) 146             { 147                 int temp = arry[0]; 148                 arry[0] = arry[i]; 149                 arry[i] = temp; 150                 HeapAdjust(arry, 0, i); 151             } 152         } 153         /// <summary> 154         /// 构建堆 155         /// </summary> 156         /// <param name="arry"></param> 157         /// <param name="parent"></param> 158         /// <param name="length"></param> 159         private static void HeapAdjust(int[] arry, int parent, int length) 160         { 161             int temp = arry[parent]; 162  163             int child = 2 * parent + 1; 164  165             while (child < length) 166             { 167                 if (child + 1 < length && arry[child] < arry[child + 1]) child++; 168  169                 if (temp >= arry[child]) 170                     break; 171  172                 arry[parent] = arry[child]; 173  174                 parent = child; 175  176                 child = 2 * parent + 1; 177             } 178  179             arry[parent] = temp; 180         } 181         /// <summary> 182         /// 归并排序 183         /// </summary> 184         /// <param name="arry"></param> 185         /// <param name="first"></param> 186         /// <param name="last"></param> 187         public static void MergeSort(this int[] arry, int first, int last) 188         { 189             if (first + 1 < last) 190             { 191                 int mid = (first + last) / 2; 192                 MergeSort(arry, first, mid); 193                 MergeSort(arry, mid, last); 194                 Merger(arry, first, mid, last); 195             } 196         } 197         /// <summary> 198         /// 归并 199         /// </summary> 200         /// <param name="arry"></param> 201         /// <param name="first"></param> 202         /// <param name="mid"></param> 203         /// <param name="last"></param> 204         private static void Merger(int[] arry, int first, int mid, int last) 205         { 206             Queue<int> tempV = new Queue<int>(); 207             int indexA, indexB; 208             //设置indexA，并扫描subArray1 [first,mid] 209             //设置indexB,并扫描subArray2 [mid,last] 210             indexA = first; 211             indexB = mid; 212             //在没有比较完两个子标的情况下，比较 v[indexA]和v[indexB] 213             //将其中小的放到临时变量tempV中 214             while (indexA < mid && indexB < last) 215             { 216                 if (arry[indexA] < arry[indexB]) 217                 { 218                     tempV.Enqueue(arry[indexA]); 219                     indexA++; 220                 } 221                 else 222                 { 223                     tempV.Enqueue(arry[indexB]); 224                     indexB++; 225                 } 226             } 227             //复制没有比较完子表中的元素 228             while (indexA < mid) 229             { 230                 tempV.Enqueue(arry[indexA]); 231                 indexA++; 232             } 233             while (indexB < last) 234             { 235                 tempV.Enqueue(arry[indexB]); 236                 indexB++; 237             } 238             int index = 0; 239             while (tempV.Count > 0) 240             { 241                 arry[first + index] = tempV.Dequeue(); 242                 index++; 243             } 244         } 245  246         /// <summary> 247         /// 基数排序 248         /// 约定:待排数字中没有0,如果某桶内数字为0则表示该桶未被使用,输出时跳过即可 249         /// </summary> 250         /// <param name="arry">待排数组</param> 251         /// <param name="array_x">桶数组第一维长度</param> 252         /// <param name="array_y">桶数组第二维长度</param> 253         public static void RadixSort(this int[] arry, int array_x = 10, int array_y = 100) 254         { 255             /* 最大数字不超过999999999...(array_x个9) */ 256             for (int i = 0; i < array_x; i++) 257             { 258                 int[,] bucket = new int[array_x, array_y]; 259                 foreach (var item in arry) 260                 { 261                     int temp = (item / (int)Math.Pow(10, i)) % 10; 262                     for (int l = 0; l < array_y; l++) 263                     { 264                         if (bucket[temp, l] == 0) 265                         { 266                             bucket[temp, l] = item; 267                             break; 268                         } 269                     } 270                 } 271                 for (int o = 0, x = 0; x < array_x; x++) 272                 { 273                     for (int y = 0; y < array_y; y++) 274                     { 275                         if (bucket[x, y] == 0) continue; 276                         arry[o++] = bucket[x, y]; 277                     } 278                 } 279             } 280  281         } 282  283     }

SortExtention

各排序算法时间复杂度与空间复杂度

参考文章

递归算法学习系列二（归并排序） 张玉彬

经典排序算法 - 基数排序Radix sort kkun

八大排序算法 CSDN 真实的归宿

百度百科