本帖最后由 Mayi 于 2012-12-12 23:09 编辑
合并排序是对分治法的一个完美展现,若对一个数组进行合并排序,其思路是将该数组一分为二,然后递归排序,再把两个排好序的数组合二为一,达到排序的目的;
例如对一个数组{8,3,4,6}进行排序,其过程如下:- { 5 3 4 6 } //将数组一拆为二
- { 5 3 } { 4 6 } //再次拆
- { 5 } { 3 } { 4 } { 6 } //数组1和2比较,8 > 3 所以3先落位,然后是8,合并数组1和2为一个数组,数组3、4做同样的操作
- { 3 5 } { 4 6 } //数组1和2比较,1中的第一个元素小于2中的第一,第二,所以3先落位,5大于数组2中第一个,所以接下来是数组2中的4落位,然后比较
- //数组1中的5和数组2中的6,5 < 6 所以5先落位,然后剩下的6落位,得到排序好的数组
- {3 4 6 8 }
复制代码 以下是实现代码,欢迎指正:
- static void MergeSort(ref int[] A)
- {
- if (A.Length > 1)
- {
- //分
- int[] left = new int[A.Length / 2 + A.Length % 2];
- int[] right = new int[A.Length / 2];
- for (int n = 0; n < (A.Length / 2 + A.Length % 2); n++)
- {
- left[n] = A[n];
- }
- for (int n = 0; n < (A.Length / 2); n++)
- {
- right[n] = A[(A.Length / 2) + (A.Length % 2) + n];
- }
- //递归
- MergeSort(ref left);
- MergeSort(ref right);
- //合并,排序
- Merge(left, right, ref A);
- }
- }
- static void Merge(int[] left, int[] right, ref int[] A)
- {
-
- int i = 0, j = 0, k = 0;
- while (i < left.Length && j < right.Length)
- {
- if (left[i] <= right[j])
- {
- A[k] = left[i];
- i++;
- }
- else
- {
- A[k] = right[j];
- j++;
- }
- k++;
- if (i == left.Length)
- {
- for (; j < right.Length; j++)
- {
- A[k] = right[j];
- k++;
- }
- }
- if(j == right.Length)
- {
- for (; i < left.Length; i++)
- {
- A[k] = left[i];
- k++;
- }
- }
- }
- }
复制代码 多的不说了,有不对之处还请指出,
PS:觉得有些冗余,找机会在优化一下,如果有不同的看法希望不吝赐教,其他算法请看这里
|