快速排序详解

在编程中，排序是非常一个实用的算法。通常我们用来将一组数据升序或降序排列。但是排序也有不同的方法，他们的平均排序效率也不同。对于排序的数据较大时，我们通常使用快速排序(Quick Sort)。因为他的效率就与他的名字一样非常快，其平均复杂度为 O(nlogn)。下面我们来看看他的使用方法。

Part 1

先写下快速排序的函数框架。

1
2
3

void quicksort(int *arr, int left, int right) {

}//end quicksort

先创建一个void类型的函数, 函数中需要3个参数

arr 表示数组名
left 表示左边界
right 表示右边界

Part 2

创建变量。

void quicksort(int *arr, int left, int right) {
    int i = left;
    int j = right;
    int temp;
    int pivot = arr[(left + right) / 2];
}//end quicksort

这些变量将会被用来遍历数组和交换数值。一共需要四个变量：

i 表示遍历的左边界
j 表示遍历的右边界
temp 用于后面的交换2个元素
pivot 作为中间点和其他元素比较，方便排序

Part 3

写个while循环开始排序


void quicksort(int *arr, int left, int right) {
    int i = left;
    int j = right;
    int temp;
    int pivot = arr[(left + right) / 2];

    while (i <= j) {

    }//end while

}//end quicksort

}//end quicksort

当 i <= j 时才遍历数组。

Part 4

开始遍历两侧元素。


void quicksort(int *arr, int left, int right) {
    int i = left;
    int j = right;
    int temp;
    int pivot = arr[(left + right) / 2];

    while (i <= j) {

        while (arr[i] < pivot)
            i++;
        while (arr[j] > pivot)
            j--;

    }//end while

}//end quicksort

}//end quicksort

第一个 while 用于检测左侧的元素是否都小于 pivot, 如果是，则使 i ++。
这可以用来判断是否需要对数组左侧执行排序。
第二个 while 用于检测右侧的元素是否都大于 pivot, 如果是，则使 j —。
这可以用来判断是否需要对数组右侧执行排序。

Part 5

如果 i <= j 则交换两个元素的值。

void quicksort(int *arr, int left, int right) {
    int i = left;
    int j = right;
    int temp;
    int pivot = arr[(left + right) / 2];

    while (i <= j) {

        while (arr[i] < pivot)
            i++;
        while (arr[j] > pivot)
            j--;

        // Begins the swap
        if (i <= j) {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        } //end if

    }//end while

}//end quicksort

这样交换会使数组升序排列，如果交换这里没有 temp 作为临时变量的话，其中一个元素的值就会丢失。为了防止丢失，需要以下的过程：

将 arr[ i ] 的值复制给 temp
将 arr[ j ] 的值赋值给 arr[ i ]
将 temp 的值赋值给 arr[ j ]
i++
j—

Part 6

判断两边的数组是否已排好序


void quicksort(int *arr, int left, int right) {
    int i = left;
    int j = right;
    int temp;
    int pivot = arr[(left + right) / 2];

    while (i <= j) {

        while (arr[i] < pivot)
            i++;
        while (arr[j] > pivot)
            j--;

        // Begins the swap
        if (i <= j) {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        } //end if

    }//end while

    // Check if we need to sort the left side
    if (left < j)
        quicksort(arr, left, j);

    // Check if we need to sort the right side
    if (i < right)
        quicksort(arr, i, right);

}//end quicksort

通过两个递归调用，对左侧数组排序，当排完左侧时，再排右侧数组。

Part 7

测试函数

#include <bits/stdc++.h>
using namespace std;
void quicksort(int* arr, int left, int right)
{
    int i = left;
    int j = right;
    int temp;
    int pivot = arr[(left + right) / 2];

    while (i <= j) {

        while (arr[i] < pivot)
            i++;
        while (arr[j] > pivot)
            j--;

        // Begins the swap
        if (i <= j) {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        } //end if

    } //end while

    // Check if we need to sort the left side
    if (left < j)
        quicksort(arr, left, j);

    // Check if we need to sort the right side
    if (i < right)
        quicksort(arr, i, right);

} //end quicksort
int main()
{
    const int n = 10;
    int arr[n] = { 7, 1, 34, 16, 12, 44, 19, 99, 0, 4 };
    quicksort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) {
        cout << arr[i] << ' ';
    }
    return 0;
}

经过调试，运行结果为
0 1 4 7 12 16 19 34 44 99
与预期相同。快速排序大功告成。

Part 1

Part 2

Part 3

Part 4

Part 5

Part 6

Part 7