首页 > 代码库 > 插入排序与归并排序的C#实现
插入排序与归并排序的C#实现
算法导论在介绍算法时列举了插入排序与并归排序，以此来说明什么事算法，算法效率以及提出了算法设计中重要的思想--分治，也就是将问题划分为规模较小的子问题。这种思想在大规模运算时具有显著的时间开销优势，例如插入排序和并归排序，其时间开销大致分别等于C1N2和C2Nlog2N。
下面介绍具体的代码：
首先是插入排序：
1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Text; 5 6 namespace algorithm 7 { 8 class Program 9 {10 class InsertionSortFun11 {12 public void InsertionSort(int[] A)13 {14 int n = A.Length;15 for (int j = 1; j < n; j++) 16 {17 //所要插入的新值18 int key = A[j]; 19 int i = j - 1;20 //将新值与原有序列比较21 while ((i >= 0) && (A[i] > key)) 22 {23 //交换顺序24 A[i + 1] = A[i]; 25 i = i - 1;26 }27 //插入新值28 A[i + 1] = key; 29 }30 }31 }32 33 static void Main(string[] args)34 {35 //待排序数组36 int[] X = { 45, 32, 87, 1, 8, 0, 4, 2, 55, 6, 34, 23, 82, 12, 8 };37 //实例化插入排序38 InsertionSortFun ISF = new InsertionSortFun();39 ISF.InsertionSort(X);40 //控制台打印输出41 foreach (int item in X)42 {43 Console.WriteLine(item);44 }45 }46 }47 }
输出结果为：
接下来是归并排序：
1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Text; 5 6 namespace algorithm 7 { 8 class Program 9 {10 class MergeSortFun11 {12 //合并函数--用于将两个已排序的数组合并13 private void Merge(int[] num, int start, int middle, int end)14 {15 int n1 = middle - start + 1;16 int n2 = end - middle;17 18 //声明两个数组用来容纳左右两个数组19 int[] L = new int[n1 + 1];20 int[] R = new int[n2 + 1];21 22 //为新建的数组赋值23 for (int i = 0; i < n1; i++) 24 {25 L[i] = num[start + i];26 }27 for (int i = 0; i < n2; i++)28 {29 R[i] = num[middle + i + 1];30 }31 //设置哨兵元素32 L[n1] = 1000000;33 R[n2] = 1000000;34 35 int p = 0;36 int q = 0;37 //进行合并38 for (int k = start; k <= end; k++) 39 {40 if (L[p] <= R[q]) 41 {42 num[k] = L[p];43 p++;44 } 45 else46 {47 num[k] = R[q];48 q++;49 }50 } 51 }52 53 //递归函数54 public void MergeSort(int[] num, int start, int end)55 {56 int middle;57 if (start < end) 58 {59 middle = (start + end) / 2;60 //归并的基本思想61 //左排序62 MergeSort(num, start, middle);63 //右排序64 MergeSort(num, middle + 1, end);65 //合并66 Merge(num, start, middle, end);67 }68 }69 }70 static void Main(string[] args)71 {72 //待排序数组73 int[] X = { 45, 32, 87, 1, 8, 0, 4, 2, 55, 6, 34, 23, 82, 12, 8 };74 //实例化归并排序75 MergeSortFun MSF = new MergeSortFun();76 MSF.MergeSort(X, 0, X.Length - 1);77 //控制台打印输出78 foreach (int item in X)79 {80 Console.WriteLine(item);81 }82 }83 }84 }
其结果与插入排序结果相同。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。