快速排序法是由C.A.R.Hoare提出来的。快速排序法又称分割交换排序法,是目前公认的最佳排序法,也是使用分而治之(Divide and Conquer)的方式,会先在数据中找到一个虚拟的中间值,并按此中间值将所有打算排序的数据分为两部分。其中小于中间值的数据放在左边,而大于中间值的数据放在右边,再以同样的方式分别处理左右两边的数据,直到排序完为止。操作与分割步骤如下:
假设有n项记录,其键值为。
- #include
- using namespace std;
-
- void Print(int tempData[], int tempSize) {
- for (int i = 0; i < tempSize; i++) {
- cout << tempData[i] << " ";
- }
- cout << endl;
- }
-
- void Quick(int tempData[], int tempLeft, int tempRight) {
- int temp;
- int leftIndex;
- int rightIndex;
- int t;
- if (tempLeft < tempRight) {
- leftIndex = tempLeft + 1;
- rightIndex = tempRight;
- while (true) {
- for (int i = tempLeft + 1; i < tempRight; i++) {
- if (tempData[i] >= tempData[tempLeft]) {
- leftIndex = i;
- break;
- }
- leftIndex++;
- }
- for (int j = tempRight; j > tempLeft + 1; j--) {
- if (tempData[j] <= tempData[tempLeft]) {
- rightIndex = j;
- break;
- }
- rightIndex--;
- }
- if (leftIndex < rightIndex) {
- temp = tempData[leftIndex];
- tempData[leftIndex] = tempData[rightIndex];
- tempData[rightIndex] = temp;
- }
- else {
- break;
- }
- }
- if (leftIndex >= rightIndex) {
- temp = tempData[tempLeft];
- tempData[tempLeft] = tempData[rightIndex];
- tempData[rightIndex] = temp;
-
- Quick(tempData, tempLeft, rightIndex - 1);
- Quick(tempData, rightIndex + 1, tempRight);
- }
- }
- }
-
- int main() {
- const int size = 10;
- int data[100] = { 32,5,24,55,40,81,17,48,25,71 };
- //32 5 24 55 40 81 17 48 25 71
- //32 5 24 25 40 81 17 48 55 71
- //32 5 24 25 17 81 40 48 55 71
- //17 5 24 25 32 81 40 48 55 71
- //5 17 24 25 32 81 40 48 55 71
- //5 17 25 24 32 81 40 48 55 71
- //5 17 25 24 32 71 40 48 55 81
- //5 17 25 24 32 55 40 48 71 81
- //5 17 25 24 32 48 40 55 71 81
- //5 17 25 24 32 40 48 55 71 81
- Print(data, size);
- Quick(data, 0, size - 1);
- Print(data, size);
- return 0;
- }
输出结果