本帖最后由 sunrise2 于 2014-7-23 23:31 编辑
1、归并排序
归并排序先分解要排序的序列,从1分成2,2分成4,依次分解,
当分解到只有1个一组的时候,就可以排序这些分组,
然后依次合并回原来的序列中,这样就可以排序所有数据。
合并排序比堆排序稍微快一点,但是需要比堆排序多一倍的内存空间,
因为它需要一个额外的数组。
- /// <summary>
- /// 归并排序
- /// </summary>
- public class MergeSort : ISort
- {
- public int[] Sort(int[] array)
- {
- if (array != null)
- {
- int[] temp = new int[array.Length];
- SortLeftAndRight(array, 0, array.Length - 1, temp);
- }
- return array;
- }
- /// <summary>
- /// 对array[first]-array[middle]和array[middle+1]-array[last]进行并归
- /// </summary>
- /// <param name="array"></param>
- /// <param name="first"></param>
- /// <param name="middle"></param>
- /// <param name="last"></param>
- /// <param name="temp"></param>
- private void Merge(int[] array, int first, int middle, int last, int[] temp)
- {
- int i = first;
- int n = middle;
- int j = middle + 1;
- int m = last;
- int k = 0;
- while (i <= n && j <= m)
- {
- if (array[i] <= array[j])
- {
- temp[k++] = array[i++];
- }
- else
- {
- temp[k++] = array[j++];
- }
- }
- while (i <= n)
- {
- temp[k++] = array[i++];
- }
- while (j <= m)
- {
- temp[k++] = array[j++];
- }
- for (i = 0; i < k; i++)
- {
- array[first + i] = temp[i];
- }
- }
- /// <summary>
- /// 递归分治
- /// </summary>
- /// <param name="array"></param>
- /// <param name="first"></param>
- /// <param name="last"></param>
- /// <param name="temp"></param>
- private void SortLeftAndRight(int[] array, int first, int last, int[] temp)
- {
- if (first < last)
- {
- int middle = (first + last) / 2;
- SortLeftAndRight(array, first, middle, temp);
- SortLeftAndRight(array, middle + 1, last, temp);
- Merge(array, first, middle, last, temp);
- }
- }
- }
复制代码 2、快速排序 快速排序是一个就地排序,分而治之,大规模递归的算法。从本质上来说,它是归并排序的就地版本。快速排序可以由下面四步组成。
(1) 如果不多于1个数据,直接返回。
(2) 一般选择序列最左边的值作为支点数据。
(3) 将序列分成2部分,一部分都大于支点数据,另外一部分都小于支点数据。
(4) 对两边利用递归排序数列。快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法,但是就通常情况而言,没有比它更快的了。快速排序是递归的,对于内存非常有限的机器来说,它不是一个好的选择。- /// <summary>
- /// 快速排序
- /// </summary>
- public class QuickSort : ISort
- {
- public int[] Sort(int[] array)
- {
- if (array != null)
- {
- int[] temp = new int[array.Length];
- QuickSorting(array, 0, array.Length - 1);
- }
- return array;
- }
- private static void QuickSorting(int[] array, int l, int r)
- {
- if (l < r)
- {
- int i = l;
- int j = r;
- int temp = array[i];
- while (i < j)
- {
- while (i < j && array[j] >= temp)
- {
- j--;
- }
- if (i < j)
- {
- array[i++] = array[j];
- }
- while (i < j && array[i] < temp)
- {
- i++;
- }
- if (i < j)
- {
- array[j--] = array[i];
- }
- }
- array[i] = temp;
- QuickSorting(array, l, i - 1);
- QuickSorting(array, i + 1, r);
- }
- }
- }
复制代码 测试代码:- class Program
- {
- public static Random re = new Random();
- static void Main(string[] args)
- {
- Stopwatch stw4 = new Stopwatch();
- Stopwatch stw5 = new Stopwatch();
- Stopwatch stw6 = new Stopwatch();
- int[] intArray4 = GetArray(int.MaxValue / 100000);
- int[] intArray5 = GetArray(int.MaxValue / 100000);
- int[] intArray6 = GetArray(int.MaxValue / 100000);
- ISort sort4 = new HeapSort();//堆排序
- stw4.Start();
- int[] result4 = sort4.Sort(intArray4);
- stw4.Stop();
- Console.WriteLine("输出排序的结果(堆排序)");
- Console.WriteLine("程序共运行时间:" + stw4.Elapsed.ToString());
- ISort sort5 = new MergeSort();//归并排序
- stw5.Start();
- int[] result5 = sort5.Sort(intArray5);
- stw5.Stop();
- Console.WriteLine("输出排序的结果(归并排序)");
- Console.WriteLine("程序共运行时间:" + stw5.Elapsed.ToString());
- ISort sort6 = new QuickSort();//快速排序
- stw6.Start();
- int[] result6 = sort6.Sort(intArray6);
- stw6.Stop();
- Console.WriteLine("输出排序的结果(快速排序)");
- Console.WriteLine("程序共运行时间:" + stw6.Elapsed.ToString());
- Console.ReadKey();
- }
- private static int[] GetArray(long _arrayLength)
- {
- long arrayLength = _arrayLength;
- //初始化数组
- int[] intArray = new int[arrayLength];
- for (int i = 0; i < arrayLength; i++)
- {
- intArray[i] = re.Next();
- }
- return intArray;
- }
- }
复制代码
|
|