快速排序的算法思想: 選定一個樞紐元素,對待排序序列進行分割,分割之后的序列一個部分小于樞紐元素,一個部分大于樞紐元素,再對這兩個分割好的子序列進行上述的過程.
//?對一個給定范圍的子序列選定一個樞紐元素,執(zhí)行完函數(shù)之后返回分割元素所在的位置,
//?在分割元素之前的元素都小于樞紐元素,在它后面的元素都大于這個元素
int?Partition(int?array[],?int?low,?int?high)
{
????//?采用子序列的第一個元素為樞紐元素
????int?pivot?=?array[low];
????while?(low?<?high)
????{
????????//?從后往前在后半部分中尋找第一個小于樞紐元素的元素
????????while?(low?<?high?&&?array[high]?>=?pivot)
????????{
????????????--high;
????????}
????????//?將這個比樞紐元素小的元素交換到前半部分
????????Swap(&array[low],?&array[high]);
????????//?從前往后在前半部分中尋找第一個大于樞紐元素的元素
????????while?(low?<?high?&&?array[low]?<=?pivot)
????????{
????????????++low;
????????}
????????//?將這個比樞紐元素大的元素交換到后半部分
????????Swap(&array[low],?&array[high]);
????}
????//?返回樞紐元素所在的位置
????return?low;
}
//?快速排序
void?QuickSort(int?array[],?int?low,?int?high)
{
????if?(low?<?high)
????{
????????int?n?=?Partition(array,?low,?high);
????????QuickSort(array,?low,?n);
????????QuickSort(array,?n?+?1,?high);
????}
}