|
根據(jù)《算法設(shè)計(jì)與分析基礎(chǔ)》中對(duì)歸并排序的描述，寫(xiě)了一分C#代碼實(shí)現(xiàn)。 1
 using System;2 using System.Collections.Generic;3 using System.Text;4 5 namespace MergeSort6    {7  class Program8   {9 static void Main(string[] args)10 {11 Program p = new Program();12 13 int[] a = new int[] { 4, 2, 1, 6, 3, 6, 0, -5, 1, 1 };14 15 p.Sort(a);16 17 for (int i = 0; i < a.Length; i++)18 {19 System.Console.WriteLine(a[i]);20 }21 }22 23 /**//// <summary>24 /// 利用歸并排序按由下到大的順序排序25 /// </summary>26 /// <param name="toBeSort"></param>27 /// <returns></returns>28 public int[] Sort(int[] toBeSort)29 {30 if (toBeSort.Length == 0)31 {32 throw new Exception("Sort array Error!");33 }34 35 if (toBeSort.Length > 1)36 {37 int[] part1 = Sort(get1Part(toBeSort));38 int[] part2 = Sort(get2Part(toBeSort));39 40 merger(part1, part2, toBeSort);41 }42 43 return toBeSort;44 }45 46 /**//// <summary>47 /// 將part1和part2按照由小到大的順序歸并到數(shù)組toBeSort中48 /// </summary>49 /// <param name="part1"></param>50 /// <param name="part2"></param>51 /// <param name="toBeSort"></param>52 private void merger(int[] part1, int[] part2, int[] toBeSort)53 {54 int index = 0;55 int i1 = 0;56 int i2 = 0;57 58 while (i1 < part1.Length && i2 < part2.Length)59 {60 if (part1[i1] < part2[i2])61 {62 toBeSort[index] = part1[i1];63 i1++;64 }65 else66 {67 toBeSort[index] = part2[i2];68 i2++;69 }70 71 index++;72 }73 74 while (i1 < part1.Length)75 {76 toBeSort[index] = part1[i1];77 index++;78 i1++;79 }80 81 while (i2 < part2.Length)82 {83 toBeSort[index] = part2[i2];84 index++;85 i2++;86 }87 }88 89 /**//// <summary>90 /// Get the second part of the array.91 /// </summary>92 /// <param name="toBeSort">The array to be sort.</param>93 /// <returns>The second part of the array.</returns>94 private int[] get2Part(int[] toBeSort)95 {96 int len = toBeSort.Length - toBeSort.Length / 2;97 int[] part2 = new int[len];98 99 Array.Copy(toBeSort, toBeSort.Length / 2, part2, 0, len);100 101 return part2;102 }103 104 /**//// <summary>105 /// Get the first part of the array.106 /// </summary>107 /// <param name="toBeSort">The array to be sort.</param>108 /// <returns>The first part of the array.</returns>109 private int[] get1Part(int[] toBeSort)110 {111 int len = toBeSort.Length / 2;112 int[] part1 = new int[len];113 114 Array.Copy(toBeSort, part1, len);115 116 return part1;117 }118 }119 }120 對(duì)于分治法的效率分析，有一個(gè)通用的公示可以使用：通用分治遞推公式。 |
|
|
