黑马程序员技术交流社区
标题:
三大排序--归并和快速排序
[打印本页]
作者:
sunrise2
时间:
2014-7-23 23:26
标题:
三大排序--归并和快速排序
本帖最后由 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;
}
}
复制代码
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2