这是最快的排序算法!

该算法还可以进一步优化。

快速排序算法平均情况下的时间复杂度为O(nlog2底n)，最坏情况下的时间复杂度为O(n的平方)。

最坏情况的发生与轴值的选择有关。为了避免最坏情况的发生，对轴值的选择可以采用随机确定法（从待排序子序列中随机选择一个元素作为轴值）和三者取中法（选取待排序子序列中第一、中间和最后，三个元素中值在中间的作为轴值）。

当待排序子序列的长度小于一定值时，对其递归调用快速排序，执行速度并不快。一个可行的优化措施是，当子序列的长度小于9时，不对子序列执行任何操作，这样调用快速排序算法后得到的是一个近似有序的序列，最后对该序列执行一次直接插入排序（对近似有序序列执行直接插入算法，速度很快）。

上面两种优化措施，不能改变快速排序算法在平均情况下的时间复杂度，只是比没有优化的程序执行稍快一些。

比较排序算法的时间复杂度的下限是O(nlog2底n)，非比较排序算法的时间复杂度可以达到O(n)。

快速排序算法不能称为最快的排序算法，某些情况下使用非比较排序算法更快，但非比较排序算法的应用有一些限制条件，所以称快速排序算法为最实用的排序算法还是比较妥当的。

[此贴子已经被作者于2006-7-6 10:57:46编辑过]

楼上的能否弄个代码上来啊!

你避免了最遭情况，也同时失去了最好情况，在说了，频繁使用随即函数要消耗大量CPU资源，你这叫出里不掏好
有本事你弄个代码上来呀
你这套理论是你的导师交的吧导师，导师，误导人的老师

快速排序並不是真的最快的排序算法

只是在平均意義上的 不同的有不同的特殊算法針對

希尔排序
using System；
namespace ShellSorter
{
public class ShellSorter
{
public void Sort（int [] list）
{
int inc；
for（inc=1；inc＜=list.Length/9；inc=3*inc+1）；
for（；inc＞0；inc/=3）
{
for（int i=inc+1；i＜=list.Length；i+=inc）
{
int t=list[i-1]；
int j=i；
while（（j＞inc）&&（list[j-inc-1]＞t））
{
list[j-1]=list[j-inc-1]；
j-=inc；
}
list[j-1]=t；
}
}
}
}
public class MainClass
{
public static void Main（）
{
int[] iArrary=new int[]{1,5,13,6,10,55,99,2,87,12,34,75,33,47}；
ShellSorter sh=new ShellSorter（）；
sh.Sort（iArrary）；
for（int m=0；m＜iArrary.Length；m++）
Console.Write（"{0} ",iArrary[m]）；
Console.WriteLine（）；
}
}
}

插入排序

using System；
namespace InsertionSorter
{
public class InsertionSorter
{
public void Sort（int [] list）
{
for（int i=1；i＜list.Length；i++）
{
int t=list[i]；
int j=i；
while（（j＞0）&&（list[j-1]＞t））
{
list[j]=list[j-1]；
--j；
}
list[j]=t；
}

}
}
public class MainClass
{
public static void Main（）
{
int[] iArrary=new int[]{1,13,3,6,10,55,98,2,87,12,34,75,33,47}；
InsertionSorter ii=new InsertionSorter（）；
ii.Sort（iArrary）；
for（int m=0；m＜iArrary.Length；m++）
Console.Write（"{0}",iArrary[m]）；
Console.WriteLine（）；
}
}
}

选择排序

using System；

namespace SelectionSorter
{
public class SelectionSorter
{
private int min；
public void Sort（int [] list）
{
for（int i=0；i＜list.Length-1；i++）
{
min=i；
for（int j=i+1；j＜list.Length；j++）
{
if（list[j]＜list[min]）
min=j；
}
int t=list[min]；
list[min]=list[i]；
list[i]=t；
}

}
}
public class MainClass
{
public static void Main（）
{
int[] iArrary=new int[]{1,5,3,6,10,55,9,2,87,12,34,75,33,47}；
SelectionSorter ss=new SelectionSorter（）；
ss.Sort（iArrary）；
for（int m=0；m＜iArrary.Length；m++）
Console.Write（"{0} ",iArrary[m]）；
Console.WriteLine（）；

}
}
}

冒泡排序
using System；

namespace BubbleSorter
{
public class BubbleSorter
{
public void Sort（int [] list）
{
int i,j,temp；
bool done=false；
j=1；
while（（j＜list.Length）&&（!done））
{
done=true；
for（i=0；i＜list.Length-j；i++）
{
if（list[i]＞list[i+1]）
{
done=false；
temp=list[i]；
list[i]=list[i+1]；
list[i+1]=temp；
}
}
j++；
}

}
}
public class MainClass
{
public static void Main（）
{
int[] iArrary=new int[]{1,5,13,6,10,55,99,2,87,12,34,75,33,47}；
BubbleSorter sh=new BubbleSorter（）；
sh.Sort（iArrary）；
for（int m=0；m＜iArrary.Length；m++）
Console.Write（"{0} ",iArrary[m]）；
Console.WriteLine（）；
}
}
}

來點比較冷門的排序