基于树的算法的堆排序是广泛使用的原地数组排序。但快速排序的性能甚至超过了堆排序。这是已知最快的排序方法。

　　快速排序使用分割法对表进行排序，将数组内元素分割成若干部分。

　　【算法原理】快速排序的独创之处在于两个索引在扫描表期间的交互作用。scanUp往表的高端(右)移动，寻找比中心值大的元素，一旦找到扫描终止，准备将元素重新放置到高端子表中，而scanDown则往表的低端(左)移动，寻找蔽中心值小的元素，这样两个子表中各有一个错位元素，因而可以将其进行交换swap(a[scanUp],A[scanDown])。scanUp和scanDown擦肩而过时，我们找到2个表之间的分割点并求出中心值的最后位置swap(a[0],A[scanDown])。

　　



　　QuickSort算法：

　　pivot=A[mid]; //mid=(high+low)/2

　　scanUp=low+1 指向表头,scanDown=high 指向表尾

　　//scanUp<=scanDown 且所指向的元素A[scanUp]<=pivot.

　　while(scanUp<=scanDown && A[scanUp]<= pivot)

　　{ scanUp++; //往表尾移动

　　}

　　//pivot

　　while(pivot

　　{scanDown--; //往表头移动

　　}

　　if(scanUp

　　{ Swap(A[scanUp],A[scanDown]); //交换错位元素

　　}else

　　{ return;}

　　QuickSort使用递归处理子表。分割后：[low,mid-1][mid][mid+1,high]，终止条件：子表元素个数<2

　　(单元素表或空表必然有序)

　　void QuickSort(T A[],int low, int high)

　　{ T pivot; //中心值

　　int scanUp,scanDown; //上游标、下游标

　　int mid;//中心索引

　　if(high-low<=0) //如果表元素个数小于2个，则返回

　　{return;}

　　else

　　{ if(high-low ==1) //如果子表有2个元素，对其进行比较，并在必要时进行交换

　　{ if(A[high]

　　{Swap(A[low],A[high]); }

　　return;

　　}

　　mid=(low+high)/2; //定义中心索引

　　pivot=A[mid]; //中心值赋值给pivot

　　Swap(A[mid],A[low]); //交换pivot及低端元素的值

　　//初始化扫描索引scanUp,scanDown

　　scanUp=low+1;

　　scanDown=high;

　　//定位错位元素;当scanDown

　　do

　　{ while(scanUp<=scanDown && A[scanUp]<=pivot)

　　scanUp++;

　　while(piovat

　　scanDown--;

　　if(scanUp < scanDown)

　　{ Swap(A[scanUp],A[scanDown]); //交换错位元素

　　}

　　}while(scanUp>scanDown);

　　//将pivot拷贝到scanDown位置，分开两个子表

　　A[low]=A[scanDown];

　　A[scanDown]=pivot;

　　//若低端子表(low,scanDown-1)有2个或更多个元素，则进行递归调用

　　if(low < scanDown-1)

　　QuickSort(A,low,scanDown-1);

　　//若高端子表(scanDown+1,high)有2个或更多个元素，则进行递归调用

　　if(scanDown+1

　　QuickSort(A,scanDown+1,high);

　　}

　　}

　　最好情况：已升序排列的数组

　　其次：已降序排列的数组

　　最坏情况：中心值总是子表中的最小元素。此种情况下性能不比选择排序或插入排序更好，但现实中不太可能发生。

　　



　　



　　各种排序算法性能比较：

　　(1)O(n的2次方)量级排序算法比较：

　　快速排序(QuickSort) > 插入排序(InsertionSort) > 选择排序(SelectionSort) > 交换排序(ExchangeSort) > 冒泡排序(BubbleSort)

　　(2)O(nlog2n)量级排序算法比较：

　　快速排序(QuickSort) > 堆排序(HeapSort) > 竞赛排序(TournamentSort) > 树排序(TreeSort)

　　3.哈希法(Hashing)

　　键值对提供对数据的访问，但大多数并不作为数组记录的索引。在多数应用中，键用来提供对数据的间接引用。用一个函数将键映射到一定的整数范围内，然后用整数值来访问数据，被称为"哈希函数(hash function)"，映射到某个与哈希函数相关联的表，其索引范围是0~n-1，此表被称为"哈希表(hash table)",它存放数据或数据的引用。
编辑澳门娱乐城:http://www.