排序与查找算法

• 本文将介绍10种常见的排序算法以及一些常见的查找算法

1.比较类排序

Part1：插入排序

1.1：插入排序【InsertionSort】

思路

• 将序列中的数组分为两个部分，一个为有序序列，另一个为未排序的无序序列。每次排序时，取未排序序列的第一个元素，从后向前扫描有序序列，找到目标位置并插入。插入排序是通过逐步扩大有序序列，缩短无序序列，最终使整个序列都有序的过程。这就像我们整理扑克牌时将牌逐个逐个放入指定的位置一样
• 步骤：
  1. 从第2个元素(即从i = 1)开始遍历，一共遍历arr.size() - 1次
  2. 在每个循环中，用有个临时变量tmp储存arr[i]的数据
  3. 令j = i，当j > 0时进入扫描循环，每次都进行比较：若tmp比arr[j - 1]小，那么arr[j - 1]的数据后移,--j，否则就直接跳出扫描循环，保证第j位置上是"空位"
  4. 将arr[j]赋值为tmp【即将数据插入】，重复这个过程直到步骤1的遍历完毕

代码⚙️

void OneRound_Insert(vector<int>& arr, int pos);

// 插入排序
void InsertSort(vector<int>& arr) 
{
    int size = arr.size();
    for (int i = 1; i < size; ++i)
    {
        OneRound_Insert(arr, i);
    }
}

/// <summary>
/// 一趟插入
/// </summary>
/// <param name="arr">要排序的数组</param>
/// <param name="pos">无序序列第一个元素的下标</param>
void OneRound_Insert(vector<int>& arr, int pos)
{
    int tmp = arr[pos];
    while (pos > 0 && tmp < arr[pos - 1])
    {
        arr[pos] = arr[pos - 1];
        --pos; // 保证pos指向的位置是空位
    }
    // TODO:出来再插入对应位置,若pos到了0位置时是不执行else代码块内容的
    arr[pos] = tmp;
}

1.2：希尔排序【ShellSort】

思路

• 希尔排序是一种优化后的插入排序，它通过分步骤预处理，提高了插入排序的效率。希尔排序需要设置有个步长gap变量用来确定相邻gap位置才进行比较与排序，之后不断减小gap的大小，来多次预处理数组序列，直至最后一次比较，数组序列就接近有序了，这提高了插入排序的效率
• 步骤：
  1. 设置一个初始步长gap = arr.size() / 3 + 1，之后每次迭代时gap = gap / 3 + 1
  2. 当gap满足gap > 1的条件时进入预处理循环【gap > 1是为了确保gap为1时是最后一次插入排序】
  3. 设置循环，让数据从gap位置开始与前gap个数据比较，直至将数据都比较完毕
  4. 令j = i，当j > 0时进入扫描循环，每次都进行比较：若tmp比arr[j - gap]小，那么arr[j - gap]的数据往后移gap位,j -= gap，否则就直接跳出扫描循环，保证第j位置上是"空位"
  5. 将arr[j]赋值为tmp【即将数据插入】，重复这个过程直到步骤1的遍历完毕

代码⚙️

// 希尔排序
void ShellSort(vector<int>& arr)
{
    int size = arr.size() - 1;
    int gap = size;
    // 确保gap为1时是最后一次插入排序
    while(gap > 1)
    {
        gap = gap / 3 + 1; // 以除3的速度缩小gap

        // 从gap位置开始与前gap个数据比较,直到将所有数据都比较完毕
        for (int i = gap; i < size; ++i)
        {
            int tmp = arr[i];
            int j = i;
            while (j > 0 && tmp < arr[j - gap])
            {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = tmp;
        }
    }
}

Part2：选择排序

2.1：直接/简单选择排序【SelectionSort】

思路

• 类似插入排序，选择排序也要区分已排序的有序序列与未排序的无序序列，不过选择排序的有序序列初始长度为0。每轮循环中从未排序序列中取出一个最大（或最小）的元素，将其交换到已排序序列的开头（或末尾）。通过不断选择，交换，最终使数组序列有序化。【当然也可以一次同时选出最大和最小元素，提高效率（双端有序）】
• 步骤：
  1. 设置两个起始变量begin和end表示无序序列的始端和尾端
  2. 当满足begin < end（即无序队列存在且还有多个元素），进入一趟选择排序
  3. 设置两个最值索引用来获取最大值与最小值
  4. 将两个对应的最值分别交换到无序序列的始端和尾端（注意调整特殊情况），然后--end，++begin来缩短无序序列，并重复步骤2的循环

代码⚙️

// 简单选择排序
void SelectionSort(vector<int>& arr)
{
    // TODO:设置begin和end变量表示无序序列的始端和尾端
    int begin = 0;
    int end = arr.size() - 1;
    while (begin < end)
    {
        // 步骤1:获取两个最值索引位置
        int minI = begin, maxI = end;
        for (int i = begin; i <= end; ++i)
        {
            if (arr[i] > arr[maxI])
            {
                maxI = i;
            }

            if (arr[i] < arr[minI])
            {
                minI = i;
            }
        }

        // 2.选择后交换
        if (end != maxI)
        {
            swap(arr[end], arr[maxI]);
            // 一个最值先交换时,若另一个最值在无序序列端点处,就需要修改一下另一个最值的索位引置
            if (minI  end)
            {
                minI = maxI;
            }
        }

        if (begin != minI)
        {
            swap(arr, arr[minI]);
        }

        // 无序序列收缩
        --end;
        ++begin;
    }
}

2.2：堆排序【HeapSort】

思路

• 堆排序是一种特殊的选择排序，利用了堆的特性（即最大元素或最小元素在堆顶）来进行排序。我们要先跟据二叉树中父节点与左右孩子节点的下标关系将数组序列中的元素映射成一棵二叉树，然后通过调整算法将数组序列构建成一个大根堆（或小根堆），之后再次通过调整算法，将堆顶元素交换到最后一个位置。之后不断地调整，交换使得数组序列变得有序
• 步骤：
  1. 设置一个循环，将除叶子节点外的节点进行第一次的向下调整
  2. 设置一个变量end = size - 1用于记录无序序列的尾部位置
  3. 再建立一个循环，不断交换堆顶元素和无序序列最后一个元素，然后对基址元素重新调整堆，并--end，直至end为0时循环结束

代码⚙️

void AdjustDown(vector<int>& arr, int root, int unoLen);

// 堆排序
void HeapSort(vector<int>& arr)
{
    int size = arr.size();

    // 第一次调整从非叶子节点开始调整(左右节点都可以用((size - 1) - 1) / 2来表示父节点)
    for (int root = ((size - 1) - 1) / 2; root >= 0; --root)
    {
        AdjustDown(arr, root, size);
    }

    int end = size - 1;
    // 第二次调整
    while (end > 0)
    {
        swap(arr[end], arr[0]);
        AdjustDown(arr, 0, end);
        --end;
    }
}

/// <summary>
/// 堆下沉调整算法(构建大根堆)
/// </summary>
/// <param name="arr">要调整的数组</param>
/// <param name="root">第一个调整的(根)节点</param>
/// <param name="unoLen">第二次调整时无序序列的长度(第一次调整长度规定为数组长)</param>
void AdjustDown(vector<int>& arr, int root, int unoLen)
{
    // TODO:下沉算法要求该根节点的左右子节点是大根堆(小根堆)
    int parent = root;
    int maxChild = parent * 2 + 1; // 先让左节点占位为左右节点中的较大者
    while (maxChild < unoLen)
    {
        // 找到较大孩子节点
        if (maxChild + 1 < unoLen && arr[maxChild] < arr[maxChild + 1])
        {
            maxChild += 1;
        }

        if (arr[maxChild] > arr[parent])
        {
            swap(arr[maxChild], arr[parent]);

            // 下沉
            parent = maxChild;
            maxChild = parent * 2 + 1;
        }
        // 不下沉,调整结束
        else
        {
            break;
        }
    }
}

Part3：交换排序

3.1：冒泡排序【BubbleSort】

思路

• 冒泡排序是通过模拟"气泡上浮"的过程而实现的一种排序方式，从无序序列第一个元素开始，不断比较相邻两个元素，将较大者向后移动，最后能达到将无序序列的最大值移动到无序序列的末尾的目的，归入有序序列，之后不断重复此过程直至数组序列有序

• 步骤：

  1. 建立双层循环，保证每次循环都能访问数组序列中的无序序列部分
  2. 在循环中，若是前面位置的值比后面位置的值大，那么就将前后元素互换，反复此过程直至内外两层循环都结束

代码⚙️

// 冒泡排序
void BubbleSort(vector<int>& arr)
{
    int size = arr.size();
    for (int i = size - 1; i > 0; --i)
    {
        // 小优化
        bool isSwapped = 0;
        for (int j = 0; j < i; ++j)
        {
            if (arr[j] > arr[j + 1])
            {
                swap(arr[j], arr[j + 1]);
                isSwapped = 1;
            }
        }

        if (!isSwapped)
            break;
    }
}

3.2：快速排序【QuickSort】

思想

• 快速排序是一种采用分治思维的排序算法(即大事化小)，每次都通过单趟排序选择一个基准元素，将数组序列分成两个部分，左边要小于基准元素，右边要大于基准元素，之后通过递归调用自身不断重复上述过程，直至最后有序
• 步骤：
  1. 判断递归基础情况，即low >= high时，不满足继续递归的条件，返回
  2. 通过单趟快排获取该轮次的基准元素
  3. 通过基准元素将此次递归中要快排的数组序列分为两部分，并进入下一次递归，直至每次递归满足基础情况并返回时，数组序列有序

单趟快排

• 作用及目的：
  • 选择一个基准元素
  • 通过单趟分区，将这个基准元素放到序列中通过函数给它分配的位置
• 分类：
  1. 挖坑法：
     • 设置一个低位指针(左端)和一个高位指针(右端)，选择序列第一个元素作为基准元素(即pivot)，并作为第一个"坑"，然后进入一次循环，每次循环中，我们先用高位指针从右往左找比pivot小的元素，把这个元素放到上一次挖的''坑''中(称为填坑)，并在该元素原来的位置处挖一个新"坑"(称为挖坑)，再用低位指针从左往右找比pivot大的元素，填上一次的坑，并挖新坑，然后循环重复上述过程直至两个指针相遇，然后将pivot放在相遇位置的"坑"上
  2. 左右指针法：
     • 设置一个左指针和一个右指针，选择序列第一个元素为基准元素(即pivot)，两个指针分别向内查找【由于基准元素在左端，所以需要先从右往左查找】，直到右指针指向的元素比基准值小，且左指针的元素比基准值大，那么就交换着两个指针指向元素，最后left right时，就将该位置的值跟pivot交换
  3. 前后指针法：
     • 选择序列第一个元素作为基准元素(即pivot)，设置两个指针，一前一后，前指针指向第一个元素，后指针指向前指针的下一个元素。让后指针往后走，如果记录到比基准值小的值，就将前后指针指向的值交换，当后指针将最后一个位置都走完后，最后再将前指针指向的值和pivot交换

快排优化

1. 三数取中：选择首、中、尾三个元素的中位数作为基准元素
2. 尾递归优化：减少递归深度，在数组元素较少时使用其他的排序方式(如插入排序等等)

代码⚙️

int ExcavationPartition(vector<int>& arr, int low, int high);
int TwoPointerPartition(vector<int>& arr, int left, int right);
int SidesPointerPartition(vector<int>& arr, int low, int high);
int GetMidIndex(const vector<int>& arr, int left, int right);

// 快速排序(递归)
void QuickSort(vector<int>& arr, int low = 0, int high = -1)
{
    high = high  -1 ? arr.size() - 1 : high;
    // 如果子序列为空,返回
    if (low >= high)
        return;

    int pivot = GetMidIndex(arr, low, high);
    swap(arr[pivot], arr[low]);

    // 进行单趟的排序,并将基准元素返回(基准元素:满足arr[基准左] <= arr[基准] <= arr[基准右])
    // int KeyIndex = ExcavationPartition(arr, low, high); // 法一
    // int KeyIndex = TwoPointerPartition(arr, low, high); // 法二
    int KeyIndex = SidesPointerPartition(arr, low, high); // 法三

    int leftSize = KeyIndex - low;
    int rightSize = high - KeyIndex;
    // 非尾三层使用快排递归,尾三层使用插入排序,减少尾递归的层数,降低递归消耗
    if (leftSize > 10)
    {
        QuickSort(arr, low, KeyIndex - 1);
    }
    else
    {
        InsertionSort(arr, low, leftSize);
    }

    if (rightSize > 10)
    {
        QuickSort(arr, KeyIndex + 1, high);
    }
    else
    {
        InsertionSort(arr, KeyIndex + 1, rightSize);
    }
}

/// <summary>
/// 1.快排单趟----挖坑法:将序列中的第一个元素作为pivot(基准元素),然后不断地在左端和右端挖坑,将大于基准值的值放到右边的坑位,小于基准值的值放到左边的坑位,并将基准元素放到最后一个坑中
/// </summary>
/// <param name="arr">(子)数组序列</param>
/// <param name="low">该序列的开始位置(低位)</param>
/// <param name="high">该序列的结束位置(高位)</param>
/// <returns>基准元素的位置</returns>
int ExcavationPartition(vector<int>& arr, int low, int high)
{
    // 基准元素pivot
    int pivot = arr[low];

    while (low < high)
    {
        // 从后往前找,找比pivot小的元素并挖坑
        while (low < high && arr[high] >= pivot)
            --high;

        if (high < 0)
            return low;
        // 将较小值放到左边坑位上
        arr[low] = arr[high]; 

        // 从前往后找,找比pivot大的元素并挖坑
        while (low < high && arr[low] <= pivot)
            ++low;
        // 将较大值放到右边坑位上
        arr[high] = arr[low];
    }
    arr[low] = pivot;
    // 返回基准元素的位置
    return low;
}
/// <summary>
/// 2.快排单趟----左右指针法:设置左指针和右指针,分别向内查找,若右指针指向的元素比基准值小,且左指针的元素比基准值大,那么就交换着两个指针指向位置的值,最后left  right时,就将这个位置的值跟基准位置交换
/// /// </summary>
/// <param name="arr">(子)数组序列</param>
/// <param name="left">该序列的左指针位置</param>
/// <param name="right">该序列的右指针位置</param>
/// <returns>基准元素的位置</returns>
int TwoPointerPartition(vector<int>& arr, int left, int right)
{
    // 由于基准值在数组序列左边,所以需要先从右往左走,再从左往右走,这样可以防止交换位置的值比基准值大从而破坏了结构的有序
    int pivotI = left;
    while (left < right)
    {
        // 从右往左找比基准值小的值
        while (left < right && arr[right] >= arr[pivotI])
            right -= 1;
        // 从左往右找比基准值大的值
        while (left < right && arr[left] <= arr[pivotI])
            left += 1;
        swap(arr[left], arr[right]);
    }
    swap(arr[pivotI], arr[right]);
    return right;
}
/// <summary>
/// 3.快排单趟----前后指针法:设置两个指针,一前一后,后指针往后走,如果记录到比基准值小的值,就将前后指针指向的值交换,最后再将前指针指向的值和基准值交换
/// </summary>
/// <param name="arr">(子)数组序列</param>
/// <param name="low">该序列的开始位置(低位)</param>
/// <param name="high">该序列的结束位置(高位)</param>
/// <returns>基准元素的位置</returns>
int SidesPointerPartition(vector<int>& arr, int low, int high)
{
    int pivotI = low;
    int prev = low;
    int cur = low + 1;

    while (cur <= high)
    {
        if (arr[cur] < arr[pivotI] && ++prev != cur)
        {
            // 自增prev,然后和cur位置的值交换
            swap(arr[cur], arr[prev]);
        }
        ++cur;
    }
    swap(arr[pivotI], arr[prev]);
    return prev;
}

// 快排优化----三数取中:获取中值,然后把他放在数组的第0个位置,因为我们的函数使用第0个位置的元素作为基准元素
int GetMidIndex(const vector<int>& arr, int left, int right)
{
    int mid = (left + right) >> 1;
    if (arr[left] < arr[mid])
    {
        if (arr[left] > arr[right])
            return left;
        else if (arr[mid] < arr[right])
            return mid;
        else
            return right;
    }
    // arr[left] >= arr[mid]
    else
    {
        if (arr[right] > arr[left])
            return left;
        else if (arr[mid] > arr[right])
            return mid;
        else
            return right;
    }
}

Part4：归并排序

4.1：归并排序【MergeSort】

思想

• 和快速排序类似，归并排序也采用了分治思想。归并排序需要将数组序列不断地递归对半分割，最终将大数组序列化为化为若干个不可再分割的单元素数组，然后将这些小序列逐个比较，然后合并，最后使数组序列变得有序
• 步骤：
  1. 建立一个tmp数组，用来暂时保存每次合并时arr数组对应位置的值
  2. 进入递归，不断拆分数组序列，当数组序列被分为单元素子序列时，就开始合并
  3. 将合并的结果暂存到tmp数组中
  4. 将tmp的结果拷贝回arr数组中

代码⚙️

void _MergeSort(vector<int>& arr, vector<int>& tmp, int left, int right);

// 归并排序(递归)
void MergeSort(vector<int>& arr)
{
    vector<int> tmp(arr.size());
    _MergeSort(arr, tmp, 0, arr.size() - 1);
}

/// <summary>
/// 归并子函数
/// </summary>
/// <param name="arr">(子)数组序列</param>
/// <param name="tmp">暂存数组</param>
/// <param name="left">该次递归的左端位置</param>
/// <param name="right">该次递归的右端位置</param>
void _MergeSort(vector<int>& arr, vector<int>& tmp, int left, int right)
{
    // 如果单元素子序列,返回
    if (left >= right)
    {
        return ;
    }
    // 将数组序列拆分为单元素子序列
    int mid = (left + right) >> 1;
    _MergeSort(arr, tmp, left, mid);
    _MergeSort(arr, tmp, mid + 1, right);

    // 开始合并
    int begin1 = left, begin2 = mid + 1;
    int end1 = mid, end2 = right;
    int cur = left;
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (arr[begin1] <= arr[begin2])
        {
            tmp[cur] = arr[begin1];
            ++begin1;
        }
        else
        {
            tmp[cur] = arr[begin2];
            ++begin2;
        }
        ++cur;
    }

    // 如果遍历后还有剩余
    while (begin1 <= end1)
    {
        tmp[cur++] = arr[begin1++];
    }
    while (begin2 <= end2)
    {
        tmp[cur++] = arr[begin2++];
    }

    // 将数据移动映射回原数组中
    for (int i = left; i <= right; ++i)
    {
        arr[i] = tmp[i];
    }
}

2.非比较类排序

5.1：计数排序【CountingSort】

思路

• 计数排序是一种非比较排序，它根据数组中数据的范围创建一个计数数组来记录每个元素出现的次数，之后通过这个数组来对原来的数组序列进行排序，适合对数据范围较小的整型数据进行排序
• 步骤：
  1. 设置两个整型变量max和min，用于记录数组序列arr中的最大值和最小值
  2. 创建变量range = max - min，然后创建一个长度为range，元素均为0的数组count，用于记录对应位置元素的个数
  3. 如果找到对应元素，就在count[对应元素大小 - min]的位置上处++
  4. 最后根据索引值i和count[i]的大小，将i + min数据逐个放在数组序列arr中

代码⚙️

// 计数排序
void CountingSort(vector<int>& arr)
{
    int max = arr[0];
    int min = arr[0];
    for (auto e : arr)
    {
        if (e > max)
            max = e;
        if (e < min)
            min = e;
    }
    // range为计数数组的长度
    int range = max - min + 1;
    vector<int> count(range, 0);
    int size = arr.size();

    // 找到对应元素就使对应位置的值+1
    for (int i = 0; i < size; ++i)
    {
        ++count[arr[i] - min];
    }

    int j = 0;
    for (int i = 0; i < range; ++i)
    {
        while (count[i] != 0)
        {
            arr[j] = i + min;
            ++j, --count[i];
        }
    }
}

5.2：基数排序【RadixSort】

思路

• 基数排序也是一种非比较型的排序算法，通过将数据一共有的位数来进行逐位排序【一般是从低位到高位】来使数组序列逐步有序，到最后就会变有序。基数排序使用计数排序作为子排序算法，来进行逐位排序。基数排序适用于排序整型或者特定格式的字符串，适合对数据范围较大的整型进行排序

• 步骤：

  1. 取得数组序列中的最大值max，满足特定条件时进入循环，循环进入基数排序的逐位排序子函数
  2. 创建两个数组count和tmp，count数组用来计数，tmp数组用来暂存数据
  3. 记录数据，存在count数组中，然后让count函数累加前面的值，使count数组表示第一个值为i的元素要放在tmp数组的第几个位置上
  4. 将元素放在tmp数组中，元素放置完毕后，将值拷贝回原数组序列

代码⚙️

void _RadxiSort_Counting(vector<int>& arr, int divisor);

// 基数排序
void RadixSort(vector<int>& arr)
{
    int max = arr[0];
    for (auto e : arr)
    {
        if (e > max)
            max = e;
    }

    for (int divisor = 1; max / divisor > 0; divisor *= 10)
    {
        _RadxiSort_Counting(arr, divisor);
    }
}

/// <summary>
/// 基数排序的逐位排序
/// </summary>
/// <param name="arr">待排序的数组序列</param>
/// <param name="divisor">除数(即表示要计数的是第几位)</param>
void _RadxiSort_Counting(vector<int>& arr, int divisor)
{
    int size = arr.size();
    // count:计数数组;tmp:暂存数组
    vector<int> count(10);
    vector<int> tmp(size);

    // 找到对应元素就使对应位置的值+1
    for (int i = 0; i < size; ++i)
    {
        ++count[(arr[i] / divisor) % 10];
    }

    // TODO:用count数组记录第一个值为i的元素要放在tmp数组的第几个位置上
    for (int i = 1; i < 10; ++i)
    {
        count[i] += count[i - 1];
    }

    // TODO:将元素放进tmp数组中(因为count记录时是从左到右读取记录的,所以如果有重复的值,那么前面的值是无法直接获取的,因为这个值被后面的覆盖掉了,所以这就需要从后往前读取元素才行)
    for (int i = size - 1; i >= 0; --i)
    {
        // count[val] - 1表示arr[i]被记录的位置
        int val = (arr[i] / divisor) % 10;
        tmp[count[val] - 1] = arr[i];
        --count[val];
    }

    // 在值拷贝回arr
    arr = tmp;
}

5.3：桶排序【BucketSort】

思路

• 桶排序是一种使用分布策略的排序算法，通过将数组序列中的数据分配到多个区间不同的桶中，然后对每个桶进行排序，最后将这些桶合并，使得数组序列变得有序。桶排序通过将数据拆分，从而避免数据量过大时性能消耗过高的情况，之后由在桶中根据桶中元素的个数来采用不同的排序策略，从而提高排序的效率。
• 步骤：
  1. 获取数组序列的最小值min和最大值max，并求出范围range = max - min
  2. 判断数据的数量然后生成对应数量的桶【或者生成数据个数个桶也行】
  3. 将数据序列中的元素映射到对应的桶上(元素按桶的位置有序排列)
  4. 设置一个暂存数组，将每个桶中的元素进行合并并放在暂存数组中，然后将值交换回原数组中

代码⚙️

// 桶排序
void BucketSort(vector<int>& arr)
{
    int size = arr.size();
    // 数据量小用内置排序
    if (size <= 50)
        sort(arr.begin(), arr.end());

    // 1.获取数据范围
    int min = arr[0];
    int max = arr[0];
    for (auto e : arr)
    {
        if (e > max)
            max = e;
        if (e < min)
            min = e;
    }
    int range = max - min;

    // 2.智能选择桶数量并创建桶
    int bucketCount = 0;
    if (size <= 50)
        bucketCount = 4;
    else if (size <= 100)
        bucketCount = 10;
    else if (size <= 1000)
        bucketCount = 20;
    else
        bucketCount = std::min(50, (int)sqrt(size));

    vector<vector<int>> buckets(bucketCount);

    // 3.将元素分配到桶中
    for (auto val : arr)
    {
        // 归一化(将元素的大小映射为在(0, 1)之间的位置)
        double normalized = (val - min) / (double)range;
        // 获取元素在buckets中的桶位置
        int bktIndex = normalized * (bucketCount - 1);
        buckets[bktIndex].push_back(val);
    }

    // 4.将桶中的元素排序
    vector<int> tmp; // 创建一个数组用于暂存数据
    for (int i = 0; i < bucketCount; ++i)
    {
        int length = buckets[i].size();
        if (length  0)
        {
            continue;
        }
        else if (length <= 10)
        {
            InsertionSort(buckets[i]);
            tmp.insert(tmp.end(), buckets[i].begin(), buckets[i].end());
        }
        else if (length <= 50)
        {
            sort(buckets[i].begin(), buckets[i].end());
            tmp.insert(tmp.end(), buckets[i].begin(), buckets[i].end());
        }
        // 桶中数据过多,进行再次递归调用桶排序
        else
        {
            BucketSort(buckets[i]);
            tmp.insert(tmp.end(), buckets[i].begin(), buckets[i].end());
        }
    }
    // 交换
    swap(arr, tmp);
}

十大排序算法的效率分析

排序算法	时间复杂度	空间复杂度	稳定性	关键特点
插入排序	最好：O(n) 一般：O(n²) 最坏：O(n²)	O(1)	稳定	对几乎有序数据效率高，实际常用
希尔排序	最好：O(n log n) 一般：O(n^1.3) 最坏：O(n²)	O(1)	不稳定	插入排序的改进，分组插入
选择排序	最好：O(n²) 一般：O(n²) 最坏：O(n²)	O(1)	不稳定	交换次数少(O(n))，但不稳定
堆排序	最好：O(n log n) 一般：O(n log n) 最坏：O(n log n)	O(1)	不稳定	最坏情况也有保证，不稳定
冒泡排序	最好：O(n) 一般：O(n²) 最坏：O(n²)	O(1)	稳定	简单易懂，效率低，检测有序时提前结束
快速排序	最好：O(n log n) 一般：O(n log n) 最坏：O(n²)	O(log n)	不稳定	平均性能最优，实际应用最广
归并排序	最好：O(n log n) 一般：O(n log n) 最坏：O(n log n)	O(n)	稳定	稳定且性能保证，但需要额外空间
计数排序	最好：O(n + k) 一般：O(n + k) 最坏：O(n + k)	O(n + k)	稳定	非比较排序，k为值域范围
基数排序	最好：O(d × (n + k)) 一般：O(d × (n + k)) 最坏：O(d × (n + k))	O(n + k)	稳定	按位排序，d为最大位数
桶排序	最好：O(n + k) 一般：O(n + k) 最坏：O(n²)	O(n + k)	稳定	数据分布均匀时效率高

• 稳定性分析

  1. 稳定排序（保持相等元素相对顺序）：

     • 冒泡排序、插入排序、归并排序、计数排序、桶排序、基数排序

  2. 不稳定排序：

     • 选择排序、希尔排序、快速排序、堆排序

适用场景

1. 插入排序：
   • 适合对数据规模小的数组进行排序
   • 适合作为其他排序算法的小数组排序优化算法
2. 希尔排序
   • 是插入排序的改进版，适合排序数据规模中等的数组序列
3. 选择排序
   • 适合在内存写入受限的环境下使用
4. 堆排序
   • 适合在内存受限的环境下使用
   • 适合作为需要保证最坏情况下任然能保持性能的排序算法
5. 冒泡排序
   • 适合作为演示与教学排序的基础算法
6. 快速排序
   • 作为通用的排序算法(各种语言的标准库排序算法)
7. 归并排序
   • 适合做数据量大的外排序算法
   • 适合作为需要保证最坏情况下任然能保持性能的排序算法
   • 可以对链表进行排序
8. 计数排序
   • 对整数排序且值域范围小
   • 适合统计频率分布
9. 基数排序
   • 适合对整数排序（尤其是位数非常多的整数）
   • 适合对字符串排序（字典排序）
   • 适合多关键字排序
10. 桶排序
    • 适合排序均匀分布的数据以及浮点数
    • 适合作为外排序的预处理排序

3.基于比较的查找

3.1：顺序查找【SequentialSearch】

思路

• 顺序查找是最简单的查找方式，也被称为线性查找。线性查找从第一个元素开始，逐个往后扫描，直到找到要查找的值后，就返回对应的索引位置

代码⚙️

// 顺序查找
template<class V>
int SequentialSearch(const vector<V>& arr, const V& value)
{
    for (int i = 0; i < arr.size(); ++i)
    {
        if (value  arr[i])
            return i;
    }
    // 不存在元素
    return -1;
}

3.2：二分查找【BinarySearch】

思路

• 二分查找也叫做折半查找，是一种有序查找算法，它要求数组序列是有序的。查找时设置左指针left，右指针right和中间下标mid = (right - left) / 2，然后对比要查找的值和arr[mid]的大小关系，如果arr[mid]较大，就将mid - 1设置为新的right，反之设将mid + 1为新的left，然后反复上述过程，直到要找的值 arr[mid]，就表示找到了值，下标为mid；若是left > right，表示数组中不存在这个值

• 步骤：

  1. 设置一个左指针left和右指针right和中间指针mid
  2. 当满足条件left <= right时进入循环，比较arr[mid]和value的值，若相等，直接返回索引值mid；若arr[mid] > value（value在左半区），则使right = mid - 1；若arr[mid] < value（value在右半区），则使left = mid + 1
  3. 如果循环结束还没有返回mid，则说明不存在value这个元素并返回-1

代码⚙️

// 二分查找
template<class V>
int BinarySearch(const vector<V>& arr, const V& value)
{
    int size = arr.size();
    int left = 0;
    int right = size - 1;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (arr[mid]  value)
            return mid;
        else if (arr[mid] > value) // 如果值比value大
            right = mid - 1;
        else // 如果值比value小
            left = mid + 1;
    }
    // 不存在元素
    return -1;
}

3.3：分块查找【BlockSearch】

思想

• 分块查找是一种改进的顺序查找方式，通过将数组序列分成多个块，并保证每个块中的最大值小于它下一个块的最小值。创建一个索引表用于储存每个块中的最大值，之后在索引表中要查找的val，将val锁定在特定块中，然后使用其他查找算法查找val，如果找到，就返回对应索引值，否则返回-1
• 步骤：
  1. 创建一个结构体Block，用来表示每个数组块的左索引，右索引以及最大元素信息
  2. 设置每个数组块的大小，然后分块
  3. 之后构建索引表，查找value在索引表上对应的位置，找到value对应的数组块位置【一个获取块索引的过程】
  4. 在步骤3找到对应的数组块后，在对应的数组块中查找【其实是通过索引关系在原数组序列arr上查找，不真正存在储存"数组块"的数组】

代码⚙️

struct Block;
vector<Block> SortedBlockCreat(vector<int>& arr, int blockSize);

// 分块查找
template<class V>
int BlockSearch(vector<V>& arr, const V& value)
{
    int size = arr.size();
    // 每个块的大小
    int blockSize;
    if (size <= 20)
        blockSize = (size + 3) / 4;
    else if (size <= 100)
        blockSize = (size + 7) / 8;
    else
        blockSize = (size + 19) / 20;
    // 1.将arr排序,然后分块
    vector<Block> blocks = SortedBlockCreat(arr, blockSize);
    int left = 0, right = blocks.size();
    int blockIndex = -1;
    // 2.查找value在索引表上的位置
    while (left <= right)
    {
        // 二分查找
        int mid = (left + right) / 2; 
        // 如果mid位置最大值比value大,那么就将blockIndex暂时赋值为mid
        if (blocks[mid].maxVal > value)
        {
            blockIndex = mid;
            right = mid - 1;
        }
        else if (blocks[mid].maxVal < value)
        {
            left = mid + 1;
        }
        // 相等
        else
        {
            blockIndex = mid;
            break;
        }
    }

    // 如果blockIndex的值不为-1(value太大了),就在对应的位置的blocks上查找
    if (blockIndex  -1)
        return -1;

    // 3.在对应块内查找
    for (int i = blocks[blockIndex].begin; i <= blocks[blockIndex].end; ++i)
    {
        if (arr[i]  value)
        {
            return i;
        }
    }
    return -1;
}

struct Block
{
    int maxVal;
    int begin;
    int end;
};

// 分块操作(先排序再分块)
vector<Block> SortedBlockCreat(vector<int>& arr, int blockSize)
{
    int size = arr.size();
    int blockCount = (arr.size() + blockSize - 1) / blockSize;
    sort(arr.begin(), arr.end());
    vector<Block> blocks(blockCount);

    for (int i = 0; i < blockCount; i++) {
        blocks[i].begin = i * blockSize;
        blocks[i].end = std::min((i + 1) * blockSize - 1, size - 1); // size - 1保证不会越界
        blocks[i].maxVal = arr[blocks[i].end]; // 每块的最大值就是最后一个元素
    }
    return blocks;
}

3.4：插值查找【InterpolationSearch】

思想

• 插值查找是一种改进的二分查找算法，更适用于数据分布均匀有序的数组序列。它先通过一个公式【就是通过比例来估计】计算出要查找的值value最可能在的位置pos，之后就和二分查找一样了，也是比较arr[pos]和value的关系来不断更新left和right指针直到找到对应的值。【点位置估计公式：pos = low + ((value - arr[low]) * (right - left)/ (arr[high] - arr[low])) ，先把两个数乘了是为了防止精度丢失】
• 步骤：
  1. 设置左指针left和右指针right，当满足left < right时进入循环
  2. 在循环中，先要处理除零错误，即arr[left] arr[right]的情况要单独处理一下
  3. 通过估计公式计算出最有可能的位置pos
  4. 对比value与arr[pos]，情况分析和二分查找一样，只不过mid变成了pos

代码⚙️

// 插值查找
template<class V>
int InterpolationSearch(const vector<V>& arr, const V& value)
{
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right)
    {
        // TODO:1.有序数组的left端和right端的值相同,要提前单独处理除零错误
        if (arr[left]  arr[right])
        {
            if (arr[left]  value)
                return left; // 返回第一个索引值
            else
                return -1;
        }

        // 2.通过估计公式获取最可能的位置
        int pos = left + (value - arr[left]) * (right - left) / (arr[right] - arr[left]);

        // 由于value的不可知性,所以要处理所以可能的情况,在有问题时提前退出
        if (pos < left || pos > right)
            return -1;

        // 3.查找值
        if (arr[pos]  value)
        {
            return pos;
        }
        else if (arr[pos] > value)
        {
            right = pos - 1;
        }
        else
        {
            left = pos + 1;
        }
    }

    // 处理未预期的行为
    return -1; 
}

3.5：斐波那契查找【FibonacciSearch】

思路

• 斐波那契查找是一种结合了二分查找和斐波那契数列特性的查找算法，或者说是一种基于黄金分割原理的高效查找算法。然后要找一个最小斐波那契数，并保证这个斐波那契数大于或等于数组长度【若是大于，一般还要扩展数组到制定的长度】，然后通过F(K) = F(K - 1) + F(K - 2)和mid = left + F(K - 1) - 1将数组序列分为两个长度分别为F(K - 1)和F(K - 2)的两个区间【其实是F(K - 1) - 1和 F(K - 2)，因为mid的位置是F(K - 1)的前一个，防止重复比较】，然后重复此过程不断分割查找最终找到对应的元素
• 步骤：
  1. 先获取斐波那契数列fib和斐波那契索引k
  2. 然后扩展数组序列成一个临时数组extendArr，以确保之后的分割位置指针能正常递归获取
  3. 设置左指针left和右指针right，当满足left < right时进入循环【注意right指针仍然是原数组序列的尾位置】
  4. 设置分割位置指针mid = left + fib(k - 1) - 1
  5. 对比value与arr[mid]，情况分析和二分查找一样

代码⚙️

// 斐波那契查找
template<class V>
int FibonacciSearch(const vector<V>& arr, const V& value)
{
    // 1.获取斐波那契数列和斐波那契索引
    int size = arr.size();
    vector<int> fib = GenerateFibonacci(size);
    // 斐波那契索引k
    int k = fib.size() - 1; 

    // 2.将数组扩展
    vector<V> extendArr(arr);
    V lastElem = arr.back();
    while (extendArr.size() < fib(k))
        extendArr.push_back(lastElem);

    // 3.查找
    int left = 0, right = size - 1;
    while (left < right)
    {
        // 分割点位置(最后-1是因为我们把left当成了开始索引位置)
        int mid = left + fib(k - 1) - 1; 
        if (extendArr[mid] == value)
        {
            return std::min(mid, right);
        }
        else if (extendArr[mid] > value)
        {
            // TODO:在左半区(让K = K - 1,左半区的实际元素个数比F(K - 1)少一个,但是递归下去不会有影响,所以可以这么做)
            right = mid - 1;
            k = k - 1;
        }
        else
        {
            left = mid + 1;
            k = k - 2;
        }
    }
}

4.树形查找

4.1：树形查找

• 即利用搜索二叉树，AVL树，红黑树，B树等树形数据结构来进行查找的算法，详情可以看我的另一篇文章：
  • [数据结构(DataStructure)

5.哈希查找

4.2：哈希查找

• 和树型查找类似，也是利用哈希表这种通过键值对实现的数据结构来实现的算法，详情可以看我的另一篇文章：
  • [数据结构(DataStructure)

七种查找算法的效率分析

查找算法	时间复杂度	空间复杂度	适用数据结构	关键特点
顺序查找	最好：O(1) 一般：O(n) 最坏：O(n)	O(1)	数组、链表等	实现简单，对数据无要求，但效率较低
二分查找	最好：O(1) 一般：O(log n) 最坏：O(log n)	O(1)	有序的数组结构	查找效率高，但要求数据有序，且支持随机访问
分块查找	最好：O(1) 一般：O(√n) 最坏：O(√n)	O(1)	分块有序结构	数据分块管理，块内无序、块间有序，适合大数据集
插值查找	最好：O(1) 一般：O(log log n) 最坏：O(n)	O(1)	有序且均匀分布的数组结构	二分查找改进版，数据分布均匀时效率优于二分查找
斐波那契查找	最好：O(1) 一般：O(log n) 最坏：O(log n)	O(1)	有序的数组结构	仅使用加减运算，适合硬件资源受限的嵌入式系统
树形查找	最好：O(log n) 一般：O(log n) 最坏：O(n)	O(n)	二叉搜索树，B-树结构	支持动态插入删除，但可能退化为链表影响效率
哈希查找	最好：O(1) 一般：O(1) 最坏：O(n)	O(n)	哈希表结构	平均查找效率最高，但需要额外空间，可能产生冲突

适用场景

1. 顺序查找：
   • 适合数据量小或查找频率低的场景
   • 适合对无序数据进行查找
   • 适合作为其他查找算法的后备方案
2. 二分查找：
   • 适合静态有序数据集的查找
   • 适合查找频率高且数据不常变动的场景
   • 适合作为标准库的基础查找算法
3. 分块查找：
   • 适合数据量很大且难以整体排序的场景
   • 适合数据库索引的构建
   • 适合文件系统的数据管理
   • 适合外部存储的数据查找
4. 插值查找：
   • 适合数据分布均匀且关键字分布均匀的有序表
   • 适合数据量极大且分布均匀的场景
5. 斐波那契查找：
   • 适合硬件资源受限的嵌入式系统
   • 适合需要避免乘除法运算的场景
6. 树形查找：
   • 适合动态数据集，需要频繁插入删除操作
   • 适合内存数据库的索引结构
   • 平衡二叉树变种（AVL树、红黑树）保证最坏情况下O(log n)性能
7. 哈希查找：
   • 适合查找性能要求极高的场景
   • 适合数据规模大且内存充足的环境
   • 适合键值对类型的数据存储和查找

• 性能对比与选择建议:

  • 小规模无序数据：顺序查找（实现简单）

  • 静态有序数据：二分查找（效率稳定）

  • 均匀分布数据：插值查找（效率更高）

  • 动态数据集：平衡二叉查找树（性能保证）

  • 极致性能要求：哈希查找（平均O(1)）

  • 资源受限环境：斐波那契查找（运算简单）

  • 超大规模数据：分块查找（可扩展性好）