C++语言程序设计

程序：
根据上面的算法分析，我们可以写出快速排序的递归函数quick_sort，它有三个参数：存放待排序的整数数组list，数组的的最小下标left和最大下标right。通过left和right可以算出数组元素的个数，这是一个通用的整数数组的排序函数，它并没有限制数组元素的个数。
我们再增加两个辅助函数：
swap：交换两个整型数。
display：显示一个整型数组的每一个元素。
另外，增加一个main函数，用于输入、排序和显示给定的数组，得到下面一个完整的程序：

| 例7-20

#include <iostream.h>
const int MAX = 11;
void quick_sort(int list[MAX], int left, int right);
void swap(int& first, int& second);
void display(int a[], int length);

void main()
{
int list[MAX];
int count;
for (count = 0 ; count < MAX ; count++)
{
cout << "Enter value of element " << count << ": ";
cin >> list[count];
}
cout << "\n\nBefore Quick Sort:\n\n";
display(list,MAX);
quick_sort(list, 0, MAX -1);
cout << "\nAfter Quick Sort:\n\n";
display(list,MAX);
}
void quick_sort(int list[], int left, int right)
{
int pivot, left_arrow, right_arrow;
left_arrow = left;
right_arrow = right;
pivot = list[(left + right)/2];
do
{
while (list[right_arrow] > pivot)
right_arrow--;
while (list[left_arrow] < pivot)
left_arrow++;
if (left_arrow <= right_arrow)
{
swap(list[left_arrow], list[right_arrow]);
left_arrow++;
right_arrow--;
}
}
while (right_arrow >= left_arrow);
if (left < right_arrow)
quick_sort(list, left, right_arrow);
if (left_arrow < right)
quick_sort(list, left_arrow, right);
}
void swap(int& first, int& second)
{
int temp = first;
first = second;
second = temp;
}

void display(int a[], int length)
{
for (int count = 0 ; count < length ; count++)
cout << a[count] << " ";
cout << "\n\n";
}

编译、运行该程序，并输入待排序的数组的个数组元素：
Enter value of element 0：49↙
Enter value of element 1：38↙
Enter value of element 2：65↙
Enter value of element 3：97↙
Enter value of element 4：76↙
Enter value of element 5：13↙
Enter value of element 6：27↙
Enter value of element 7：45↙
Enter value of element 8：22↙
Enter value of element 9：54↙
Enter value of element 10：6↙
得到下面的输出结果：
Before Quick Sort:
49 38 65 97 76 13 27 45 22 54 6
After Quick Sort:
6 13 22 27 38 45 49 54 65 76 97