快速排序（快排）

大家好，欢迎来到IT知识分享网。

快速排序

1. 什么是快排 ？

快速排序，简称快排，利用了“分治”的思想。比较次数较小，速度较快。

2. 快排的原理是什么？

快排的基本思想是：在待排序的 n 个数据中任取一个数据为分区标准，把所有小于该排序码的数据移到左边，把所有大于该排序码的数据移到右边，中间放所选记录，称之为一趟排序；然后，对前后两个子序列重复上述过程。继续下去，直到所有记录都排好序。

通俗点说，大致过程是对于一个无序序列，找到一个”哨兵数”，将序列中所有比哨兵数小的数字都移在哨兵数的左边，所有比哨兵数大的数字都移在哨兵数的右边；然后分别对哨兵数左边和右边再使用同样的方法找到新的哨兵数，并再次进行分类，直到集合不可分割为止。

3. 如何实现快排？

3.1 代码实现：

void quick_sort(int a[], int l, int r) // 引入数组的地址 { 
    int i = l, j = r, flag = a[(l+r)/2], tmp; do { 
    while(a[i] < flag) i++; // 出左找比哨兵大的数 while(a[j] > flag) j--; // 出右找比哨兵小的数 if(i <= j) { 
    // 进行交换 swap(a[i], a[j]); i++; j--; } } while(i <= j) { 
    if(l < j) quick_sort(a, l, j); if(i < r) quick_sort(a, i, r); } } 

3.2 详细图解：

4. 快排的时间复杂度为多少？

5. 注意事项

1. 快排适应性差，平均时间复杂度为O(nlog2n)。
2. 建议使用 (l+r)/2 作为分界点，避免出现 O(n^2) 的时间复杂度造成超时。