-- 作者：admin
-- 发布时间：11/9/2004 2:25:00 AM
-- 快速排序算法的C#实现
发信人: Jobs (温少), 信区: DotNET
标 题: 快速排序算法的C#实现
发信站: BBS 水木清华站 (Sun Jan 5 02:48:33 2003)
/**
*
*
@author <a href="wen">mailto:szuJobs@hotmail.com">wenshaojin</a>
@created January 5, 2003
@version 1
*
**/
using System;
using System.Collections;
namespace Matrix.Common.Utils
{
/// <summary>
/// Summary description for SortUtils.
/// </summary>
public class SortUtils
{
#region 用于IList的快速排序
/// <summary>
/// 快速排序
/// </summary>
/// <param name="array"></param>
public static void QuickSort(IList list)
{
QuickSort(list, 0, list.Count-1, new CompareMethod(Comparer.Defaul
t.Compare));
}
public static void QuickSort(IList list, CompareMethod compare)
{
QuickSort(list, 0, list.Count-1, compare);
}
private static void QuickSort(IList list, int low, int high, CompareMe
thod compare)
{
if(low >= high)
{
return;
}
int i = low; //从左到右的游标
int j = high + 1; //从右到左的游标
object pivot = list[low];
//把左侧>=pivot的元素与右侧<=pivot的元素进行交换
while(true)
{
do //从左侧寻找>=pivot的元素
{
i++;
}
while(compare(list[i], pivot)<0);
do //从右侧寻找<=pivot的元素
{
j--;
}
while(compare(list[j], pivot)>0);
if(i >= j) //未发现交换对象
{
break;
}
//Swap
object temp = list[i];
list[i] = list[j];
list[j] = temp;
}
//设置pivot
list[low] = list[j];
list[j] = pivot;
QuickSort(list, low, j-1, compare); //对左段排序
QuickSort(list, j+1, high, compare); //对右段排序
}
#endregion
//用于值类型的快速排序，有更好的性能
#region 用于值类型数组的快速排序
/// <summary>
/// 快速排序
/// </summary>
/// <param name="array"></param>
public static void QuickSort(int[] array)
{
QuickSort(array, 0, array.Length-1);
}
/// <summary>
/// 快速排序
/// </summary>
/// <param name="array"></param>
public static void QuickSort(long[] array)
{
QuickSort(array, 0, array.Length-1);
}
/// <summary>
/// 快速排序
/// </summary>
/// <param name="array"></param>
public static void QuickSort(float[] array)
{
QuickSort(array, 0, array.Length-1);
}
/// <summary>
/// 快速排序
/// </summary>
/// <param name="array"></param>
public static void QuickSort(double[] array)
{
QuickSort(array, 0, array.Length-1);
}
/// <summary>
/// 快速排序
/// </summary>
/// <param name="array"></param>
public static void QuickSort(decimal[] array)
{
QuickSort(array, 0, array.Length-1);
}
/// <summary>
/// 快速排序
/// </summary>
/// <param name="array"></param>
public static void QuickSort(DateTime[] array)
{
QuickSort(array, 0, array.Length-1);
}
private static void QuickSort(int[] array, int low, int high)
{
if(low >= high)
{
return;
}
int i = low; //从左到右的游标
int j = high + 1; //从右到左的游标
int pivot = array[low];
//把左侧>=pivot的元素与右侧<=pivot的元素进行交换
while(true)
{
do //从左侧寻找>=pivot的元素
{
i++;
}
while(array[i] < pivot);
do //从右侧寻找<=pivot的元素
{
j--;
}
while(array[j] > pivot);
if(i >= j) //未发现交换对象
{
break;
}
Swap(ref array[i], ref array[j]);
}
//设置pivot
array[low] = array[j];
array[j] = pivot;
QuickSort(array, low, j-1); //对左段排序
QuickSort(array, j+1, high); //对右段排序
}
private static void QuickSort(long[] array, int low, int high)
{
if(low >= high)
{
return;
}
int i = low; //从左到右的游标
int j = high + 1; //从右到左的游标
long pivot = array[low];
//把左侧>=pivot的元素与右侧<=pivot的元素进行交换
while(true)
{
do //从左侧寻找>=pivot的元素
{
i++;
}
while(array[i] < pivot);
do //从右侧寻找<=pivot的元素
{
j--;
}
while(array[j] > pivot);
if(i >= j) //未发现交换对象
{
break;
}
Swap(ref array[i], ref array[j]);
}
//设置pivot
array[low] = array[j];
array[j] = pivot;
QuickSort(array, low, j-1); //对左段排序
QuickSort(array, j+1, high); //对右段排序
}
private static void QuickSort(float[] array, int low, int high)
{
if(low >= high)
{
return;
}
int i = low; //从左到右的游标
int j = high + 1; //从右到左的游标
float pivot = array[low];
//把左侧>=pivot的元素与右侧<=pivot的元素进行交换
while(true)
{
do //从左侧寻找>=pivot的元素
{
i++;
}
while(array[i] < pivot);
do //从右侧寻找<=pivot的元素
{
j--;
}
while(array[j] > pivot);
if(i >= j) //未发现交换对象
{
break;
}
Swap(ref array[i], ref array[j]);
}
//设置pivot
array[low] = array[j];
array[j] = pivot;
QuickSort(array, low, j-1); //对左段排序
QuickSort(array, j+1, high); //对右段排序
}
private static void QuickSort(double[] array, int low, int high)
{
if(low >= high)
{
return;
}
int i = low; //从左到右的游标
int j = high + 1; //从右到左的游标
double pivot = array[low];
//把左侧>=pivot的元素与右侧<=pivot的元素进行交换
while(true)
{
do //从左侧寻找>=pivot的元素
{
i++;
}
while(array[i] < pivot);
do //从右侧寻找<=pivot的元素
{
j--;
}
while(array[j] > pivot);
if(i >= j) //未发现交换对象
{
break;
}
Swap(ref array[i], ref array[j]);
}
//设置pivot
array[low] = array[j];
array[j] = pivot;
QuickSort(array, low, j-1); //对左段排序
QuickSort(array, j+1, high); //对右段排序
}
private static void QuickSort(decimal[] array, int low, int high)
{
if(low >= high)
{
return;
}
int i = low; //从左到右的游标
int j = high + 1; //从右到左的游标
decimal pivot = array[low];
//把左侧>=pivot的元素与右侧<=pivot的元素进行交换
while(true)
{
do //从左侧寻找>=pivot的元素
{
i++;
}
while(array[i] < pivot);
do //从右侧寻找<=pivot的元素
{
j--;
}
while(array[j] > pivot);
if(i >= j) //未发现交换对象
{
break;
}
Swap(ref array[i], ref array[j]);
}
//设置pivot
array[low] = array[j];
array[j] = pivot;
QuickSort(array, low, j-1); //对左段排序
QuickSort(array, j+1, high); //对右段排序
}
private static void QuickSort(DateTime[] array, int low, int high)
{
if(low >= high)
{
return;
}
int i = low; //从左到右的游标
int j = high + 1; //从右到左的游标
DateTime pivot = array[low];
//把左侧>=pivot的元素与右侧<=pivot的元素进行交换
while(true)
{
do //从左侧寻找>=pivot的元素
{
i++;
}
while(array[i] < pivot);
do //从右侧寻找<=pivot的元素
{
j--;
}
while(array[j] > pivot);
if(i >= j) //未发现交换对象
{
break;
}
Swap(ref array[i], ref array[j]);
}
//设置pivot
array[low] = array[j];
array[j] = pivot;
QuickSort(array, low, j-1); //对左段排序
QuickSort(array, j+1, high); //对右段排序
}
private static void Swap(ref int a, ref int b)
{
int temp = a;
a = b;
b = temp;
}
private static void Swap(ref long a, ref long b)
{
long temp = a;
a = b;
b = temp;
}
private static void Swap(ref float a, ref float b)
{
float temp = a;
a = b;
b = temp;
}
private static void Swap(ref double a, ref double b)
{
double temp = a;
a = b;
b = temp;
}
private static void Swap(ref decimal a, ref decimal b)
{
decimal temp = a;
a = b;
b = temp;
}
private static void Swap(ref DateTime a, ref DateTime b)
{
DateTime temp = a;
a = b;
b = temp;
}
#endregion
/// <summary>
/// 如果a小于b，返回小于0的数字。
/// 如果a等于b，返回等于0的数字。
/// 如果a大于b，返回大于0的数字。
/// </summary>
public delegate int CompareMethod(object a, object b);
}
}
--
※ 来源:·BBS 水木清华站 smth.org·[FROM: 218.17.71.167]
上一篇
返回上一页
回到目录
回到页首
下一篇
|