快速排序是应用最广泛的排序算法,也是目前认为最好的一种内部排序方法(就平均时间而言)。它采用分治(divide-and-conquer)的策略,通过一趟排序将待排记录分割成独立的两个部分,使其中的一部分记录关键字均比另一部分记录关键字小(大),然后分别对两个部分继续进行排序,以达到整个序列有序。
快速排序的C/C++代码实现:
int partition(int sort_array[], int low, int high)
{
int pivotkey = sort_array[low];
while (low < high) {
while (low < high && pivotkey <= sort_array[high]) --high;
sort_array[low] = sort_array[high];
while (low < high && pivotkey >= sort_array[low]) ++low;
sort_array[high] = sort_array[low];
}
sort_array[low] = pivotkey;
return low;
}
void quick_sort(int sort_array[], int low, int high)
{
if (low < high) {
int i = partition(sort_array, low, high);
quick_sort(sort_array, low, i - 1);
quick_sort(sort_array, i + 1, high);
}
}