快速排序(QuickSort)
基于树的算法的堆排序是广泛使用的原地数组排序。但快速排序的性能甚至超过了堆排序。这是已知最快的排序方法。快速排序使用分割法对表进行排序，将数组内元素分割成若干部分。
【算法原理】快速排序的独创之处在于两个索引在扫描表期间的交互作用。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.
