一、快速排序 Quick Sort
1. 前提条件

快排是最经典的：分治思想

和归并一样：先拆再解决

但和归并最大的区别：

归并：先递归，后合并

快排：先分区，后递归

2. 核心概念

核心操作：Partition（划分）

例如：

[5,2,8,1,7]

选：5

作为基准值（pivot）。

目标：

小于5的放左边

大于5的放右边

变成：

[2,1,5,8,7]

注意：5已经到最终位置

以后不用管它了。

然后递归：

[2,1]

[8,7]

继续快排。

3. 核心思想

每次递归：确定一个元素最终位置

归并：每层合并有序数组

快排：每层确定一个 pivot

4. Partition（双指针）


数组：[5,2,8,1,7]

选：pivot=5

定义：

i 左边找大于5

j 右边找小于5

找到：

8
1

交换：

[5,2,1,8,7]

最后：

pivot归位

得到：

[1,2,5,8,7]

5. 固定模板
partition
int partition(int arr[], int left, int right)
{
    int pivot = arr[left];

    int i = left;
    int j = right;

    while(i < j)
    {
        while(i < j && arr[j] >= pivot)
        {
            j--;
        }
     //相当于从左往右遍历直到直到跳过小于pivot的位置
        while(i < j && arr[i] <= pivot)
        {
            i++;
        }
     //这里相当于从右往左跳过比pivot大的位置，直到找到最终pivot应该在的位置
        if(i < j)
        {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        //这里就是左右指针没碰到，就交换两个位置，然后继续移动指针直到left=right
    }
//然后把left位置选中的pivot和i位置的数交换，之后相当于排好了pivot的位置，之后return 
    arr[left] = arr[i];
    arr[i] = pivot;

    return i;
}

quickSort
void quickSort(int arr[],
               int left,
               int right)
{
    if(left >= right)
    {
        return;
    }
//这里是直接分到最小就直接返回
//然后递归排mid左边和mid右边 
    int mid = partition(arr,left,right);

    quickSort(arr,left,mid-1);

    quickSort(arr,mid+1,right);
}

6. 例子

数组：[5,2,8,1,7]

第一次：pivot=5

分区后：[1,2,5,8,7]

继续：

[1,2]

[8,7]

左边：[1,2]

已经有序。

右边：[8,7]

变：[7,8]

最终：[1,2,5,7,8]

7. 复杂度

平均：O(nlogn)

最坏：O(n²)

例如：[1,2,3,4,5]

总拿最左边当 pivot。

空间：O(logn)

递归栈。

稳定性：不稳定

8. 易错点

partition返回的是pivot最终位置

pivot已经排好

递归不要再包含pivot

应该：

left ~ mid-1

mid+1 ~ right

二、桶排序 Bucket Sort
1. 前提条件

桶排序不是比较排序。

思想：先分类，再排序

例如成绩：

72
91
85
60

可以放进：

60桶

70桶

80桶

90桶

然后桶内排序。

2. 核心思想

步骤：

1. 建桶
2. 放桶
3. 桶内排序
4. 收集

3. 最简单情况

如果数据范围：0~100

其实就是计数排序。就是拿空间换时间的方式

数组：[5,2,8,5,3]

建立桶：

cnt[101]

统计：

cnt[2]++

cnt[3]++

cnt[5]+=2

cnt[8]++

得到：

2:1

3:1

5:2

8:1

输出：

2

3

5

5

8

4. 固定模板（计数排序）
void bucketSort(int arr[],
                int n)
{
    int cnt[101]={0};

    for(int i=0;i<n;i++)
    {
        cnt[arr[i]]++;
    }

    int k=0;

    for(int i=0;i<=100;i++)
    {
        while(cnt[i]--)
        {
            arr[k++] = i;
        }
    }
}

5. 为什么快

因为：不比较直接统计

例如：100万个成绩

范围0~100

只需要：统计101个桶

即可。

6. 复杂度
O(n+k)

其中：
n=元素个数

k=桶个数

7. 局限性

如果：

1

1000000000

只有两个数。

开桶：cnt[1000000001]会炸。
所以：桶排序要求数据范围较小

三、总结

快速排序

核心：
    partition

思想：
    小的放左边
    大的放右边

每次确定一个pivot最终位置

递归：
    左边快排
    右边快排

平均：
    O(nlogn)

最坏：
    O(n²)

不稳定

--------------------------------

桶排序

核心：
    分类统计

步骤：
    建桶
    放桶
    桶内排序
    收集

复杂度：
    O(n+k)

要求：
    数据范围较小

典型：
    成绩统计
    年龄统计
    计数排序