首页 / 算法 / 插入排序与归并排序的C#实现
插入排序与归并排序的C#实现
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了插入排序与归并排序的C#实现,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2443字,纯文字阅读大概需要4分钟。
内容图文
算法导论在介绍算法时列举了插入排序与并归排序,以此来说明什么事算法,算法效率以及提出了算法设计中重要的思想--分治,也就是将问题划分为规模较小的子问题。这种思想在大规模运算时具有显著的时间开销优势,例如插入排序和并归排序,其时间开销大致分别等于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 InsertionSortFun 11 { 12 public void InsertionSort(int[] A) 13 { 14int n = A.Length; 15for (int j = 1; j < n; j++) 16 { 17//所要插入的新值18int key = A[j]; 19int i = j - 1; 20//将新值与原有序列比较21while ((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 } 3233staticvoid Main(string[] args) 34 { 35//待排序数组36int[] 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//控制台打印输出41foreach (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 MergeSortFun 11 { 12 // 合并函数--用于将两个已排序的数组合并 13 private void Merge(int[] num, int start, int middle, int end) 14 { 15int n1 = middle - start + 1; 16int n2 = end - middle; 1718//声明两个数组用来容纳左右两个数组19int[] L = newint[n1 + 1]; 20int[] R = newint[n2 + 1]; 2122//为新建的数组赋值23for (int i = 0; i < n1; i++) 24 { 25 L[i] = num[start + i]; 26 } 27for (int i = 0; i < n2; i++) 28 { 29 R[i] = num[middle + i + 1]; 30 } 31//设置哨兵元素32 L[n1] = 1000000; 33 R[n2] = 1000000; 3435int p = 0; 36int q = 0; 37//进行合并38for (int k = start; k <= end; k++) 39 { 40if (L[p] <= R[q]) 41 { 42 num[k] = L[p]; 43 p++; 44 } 45else46 { 47 num[k] = R[q]; 48 q++; 49 } 50 } 51 } 5253//递归函数54publicvoid MergeSort(int[] num, int start, int end) 55 { 56int middle; 57if (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 } 70staticvoid Main(string[] args) 71 { 72//待排序数组73int[] 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//控制台打印输出78foreach (int item in X) 79 { 80 Console.WriteLine(item); 81 } 82 } 83 } 84 }
其结果与插入排序结果相同。
原文:http://www.cnblogs.com/LiuYujie/p/3854513.html
内容总结
以上是互联网集市为您收集整理的插入排序与归并排序的C#实现全部内容,希望文章能够帮你解决插入排序与归并排序的C#实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。