普通快速排序的缺陷

普通快速排序源代码

template<typename T>
void quickSort(T* arr, int size) { 
    if (size == 0)return;
    int front = 0, rear = size - 1;
    T pivot = arr[0];
    while (front < rear) { 
        while (front < rear && arr[rear] >= pivot) {  --rear; }
        arr[front] = arr[rear];
        while (front < rear && arr[front] <= pivot) {  ++front; }
        arr[rear] = arr[front];
    }
    arr[front] = pivot;
    quickSort(arr, front);
    quickSort(arr + front + 1, size - 1 - front);
}

我们输入一个完全倒序的数组,测试一下

int main() { 
    constexpr int size = 10000;
    int* nums = new int[size]{ 0};
    // 完全倒序的一个数组
    for (int i = 0; i < size; ++i) { 
        nums[i] = size - i;
    }
    quickSort(nums, size);
    delete[] nums;
    return 0;
}

对 10000 个完全倒序的数进行排序并计一下时,可以发现快速排序是非常慢的!因为此时快速排序已经退化成了冒泡排序!

同时如果输入的数组中的数据完全相同,那么普通的快速排序会产生不必要的划分和递归,既浪费时间又浪费空间

快速排序的优化

优化 pivot 的选取

1.随机选取中轴

template<typename T>
void quickSort(T* arr, int size) { 
    if (size == 0)return;
    int front = 0, rear = size - 1;
    // 在arr中随机选一个数,然后和arr[0]交换一下
    swap(arr[0], arr[rand() % size]);
    T pivot = arr[0];
    while (front < rear) { 
        while (front < rear && arr[rear] >= pivot) {  --rear; }
        arr[front] = arr[rear];
        while (front < rear && arr[front] <= pivot) {  ++front; }
        arr[rear] = arr[front];
    }
    arr[front] = pivot;
    quickSort(arr, front);
    quickSort(arr + front + 1, size - 1 - front);
}

重新对 10000 完全倒序的数进行排序,可以发现速度大幅度提升

2.三数取中

template<typename T>
void quickSort(T* arr, int size) { 
    if (size == 0)return;
    int front = 0, rear = size - 1, mid = rear / 2;
    // 把arr[0],arr[mid],arr[rear]的中位数与arr[0]调换位置
    if (arr[mid] > arr[rear]) { 
        swap(arr[mid], arr[rear]);
    }
    if (arr[front] > arr[rear]) { 
        swap(arr[front], arr[rear]);
    }
    if (arr[mid] > arr[front]) { 
        swap(arr[mid], arr[front]);
    }
    T pivot = arr[0];
    while (front < rear) { 
        while (front < rear && arr[rear] >= pivot) {  --rear; }
        arr[front] = arr[rear];
        while (front < rear && arr[front] <= pivot) {  ++front; }
        arr[rear] = arr[front];
    }
    arr[front] = pivot;
    quickSort(arr, front);
    quickSort(arr + front + 1, size - 1 - front);
}

对算法的优化

1. 在数据量小的时候使用插入排序

我们只需要把

if (size == 0) return;

改为

if (size <= 10) { 
    // do insertSort ...
    return;
}

即可!

2. 把与 pivot 相同的数据尽可能的聚集到中轴附近

先来看一组数,这是经过一次划分之后的数组,其中粗体的 5 是这个数组的中轴,左边的数全部<=5,右边的数全部>=5
1 5 3 2 4 5 6 5 7 5 9
此时我们需要对 1 5 3 2 4 和 6 5 7 5 9 进行快速排序
如果我们把数组中所有的 5 全部向中轴聚集,我们会得到这样一个数组
1 4 3 2 5 5 5 5 7 6 9
这样我们只需对 1 4 3 2 和 7 6 9 进行快速排序就可以了,效率得到提高

template<typename T>
void quickSort(T* arr, int size) { 
    if (size == 0)return;
    int front = 0, rear = size - 1;
    T pivot = arr[0];
    while (front < rear) { 
        while (front < rear && arr[rear] >= pivot) {  --rear; }
        arr[front] = arr[rear];
        while (front < rear && arr[front] <= pivot) {  ++front; }
        arr[rear] = arr[front];
    }
    arr[front] = pivot;
    // 向中间聚集
    int left = front - 1, right = front + 1;
    for (int i = left; i >= 0; i--) { 
        if (arr[i] == pivot) { 
            swap(arr[i], arr[left]);
            --left;
        }
    }
    for (int i = right; i < size; i++) { 
        if (arr[i] == pivot) { 
            swap(arr[i], arr[right]);
            ++right;
        }
    }
    quickSort(arr, left + 1);
    quickSort(arr + right, size - right);
}

最终版本

template<typename T>
void quickSort(T* const arr, const size_t size) { 
    if (size <= 10) { 
    	// lambda实现直接插入排序
        ([arr, size]() -> void { 
            int i, j;
            T temp;
            for (i = 1; i < size; ++i) { 
                temp = arr[i];
                for (j = i - 1; j >= 0 && arr[j] > temp; --j) { 
                    arr[j + 1] = arr[j];
                }
                arr[j + 1] = temp;
            }
        })();
        return;
    }
    int front = 0, rear = size - 1, mid = rear / 2;
    if (arr[mid] > arr[rear]) { 
        swap(arr[mid], arr[rear]);
    }
    if (arr[front] > arr[rear]) { 
        swap(arr[front], arr[rear]);
    }
    if (arr[mid] > arr[front]) { 
        swap(arr[mid], arr[front]);
    }
    T pivot = arr[0];
    while (front < rear) { 
        while (front < rear && arr[rear] >= pivot) { 
            --rear;
        }
        arr[front] = arr[rear];
        while (front < rear && arr[front] <= pivot) { 
            ++front;
        }
        arr[rear] = arr[front];
    }
    arr[front] = pivot;
    int left = front - 1, right = front + 1;
    for (int i = left; i >= 0; i--) { 
        if (arr[i] == pivot) { 
            swap(arr[i], arr[left]);
            --left;
        }
    }
    for (int i = right; i < size; i++) { 
        if (arr[i] == pivot) { 
            swap(arr[i], arr[right]);
            ++right;
        }
    }
    quickSort(arr, left + 1);
    quickSort(arr + right, size - right);
}

对 n 个随机数排序耗时如下:

普通快速排序耗时

优化后的快速排序耗时

其他

单轴快速排序还可以继续优化,例如可以把尾递归改为循环实现,使用多线程加快排序速度