十大排序算法

排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。

冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法，它通过重复地遍历待排序的列表，比较相邻的元素并交换它们的位置来实现排序。

比较相邻元素：从列表的第一个元素开始，比较相邻的两个元素。
交换位置：如果前一个元素比后一个元素大，则交换它们的位置。
重复遍历：对列表中的每一对相邻元素重复上述步骤，直到列表的末尾。这样，最大的元素会被"冒泡"到列表的最后。
缩小范围：忽略已经排序好的最后一个元素，重复上述步骤，直到整个列表排序完成。

template<typename T>  
void bubble_sort(T *arr, int n) {  
    for (int i = 0; i < n; i++) {  
        bool flag = false;  
        for (int j = 0; j < n - i - 1; j++) {  
            if (arr[j] > arr[j + 1]) {  
                flag = true;  
                std::swap(arr[j], arr[j + 1]);  
            }  
        }  
        //没有交换则说明有序了退出  
        if (!flag) break;  
    }  
}

选择排序

选择排序（Selection Sort）是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
选择排序基本思想是每次从待排序的数据中选择最小（或最大）的元素，放到已排序序列的末尾，直到全部数据排序完成。

初始化：将列表分为已排序部分和未排序部分。初始时，已排序部分为空，未排序部分为整个列表。
查找最小值：在未排序部分中查找最小的元素。
交换位置：将找到的最小元素与未排序部分的第一个元素交换位置。
更新范围：将未排序部分的起始位置向后移动一位，扩大已排序部分的范围。
重复步骤：重复上述步骤，直到未排序部分为空，列表完全有序。

template<typename T>  
void selection_sort(T *arr, int n) {  
    for (int i = 0; i < n; i++) {  
        int min = i;  
        //每次循环中记录最小值的下标  
        for (int j = i + 1; j < n; j++) {  
            if (arr[j] < arr[min]) {  
                min = j;  
            }  
        }  
        std::swap(arr[i], arr[min]);  
    }  
}

插入排序

插入排序通过构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。
插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

初始化：将列表分为已排序部分和未排序部分。初始时，已排序部分只包含第一个元素，未排序部分包含剩余元素。
选择元素：从未排序部分中取出第一个元素。
插入到已排序部分：将该元素与已排序部分的元素从后向前依次比较，找到合适的位置插入。
重复步骤：重复上述步骤，直到未排序部分为空，列表完全有序。

template<typename T>  
void insertion_sort(T *arr, int n) {  
    // 第一个值默认有序  
    //每轮循环中[0，j]都是有序的  
    for (int i = 1; i < n; i++) {  
        int key = arr[i], j = i - 1;  
        //向前寻找大于key的数，全部后移  
        while (j >= 0 && arr[j] > key) {  
            arr[j + 1] = arr[j];  
            j--;  
        }  
        arr[j + 1] = key;  
    }  
}

希尔排序

希尔排序（Shell Sort）是插入排序的一种改进版本，也称为缩小增量排序。它通过将待排序的列表分成若干子列表，对每个子列表进行插入排序，逐步缩小子列表的间隔，最终完成整个排序。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

以下是算法步骤：

选择增量序列：选择一个增量序列（gap sequence），用于将列表分成若干子列表。常见的增量序列有希尔增量（n/2, n/4, ..., 1）等。
分组插入排序：按照增量序列将列表分成若干子列表，对每个子列表进行插入排序。
缩小增量：逐步缩小增量，重复上述分组和排序过程，直到增量为 1。
最终排序：当增量为 1 时，对整个列表进行一次插入排序，完成排序。

template<typename T>  
void shell_sort(T *arr, int n) {  
    int gap = n / 2;  
    while (gap > 0) {  
        for (int i = gap; i < n; i++) {  
            T key = arr[i];  
            int j = i - gap;  
            while (j >= 0 && arr[j] > key) {  
                arr[j + gap] = arr[j];  
                j = j - gap;  
            }  
            arr[j + gap] = key;  
        }  
        gap = gap / 2;  
    }  
}

归并排序

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

自上而下的递归；
自下而上的迭代；

归并排序的核心思想是将一个大问题分解成若干个小问题，分别解决这些小问题，然后将结果合并起来，最终得到整个问题的解。具体到排序问题，归并排序的步骤如下：

分解（Divide）：将待排序的数组分成两个子数组，每个子数组包含大约一半的元素。
解决（Conquer）：递归地对每个子数组进行排序。
合并（Combine）：将两个已排序的子数组合并成一个有序的数组。

通过不断地分解和合并，最终整个数组将被排序。

以下是算法步骤：

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
设定两个指针，最初位置分别为两个已经排序序列的起始位置；
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
重复步骤 3 直到某一指针达到序列尾；
将另一序列剩下的所有元素直接复制到合并序列尾。

递归实现

template<typename T>  
void merge(T *arr, int l, int m, int r) {  
    //创建临时数组用于存放排序后的数据  
    T tmp[r - l + 1];  
    int i = l, j = m + 1, k = 0;  
    while (i <= m && j <= r) {  
        if (arr[i] <= arr[j]) {  
            tmp[k++] = arr[i++];  
        } else {  
            tmp[k++] = arr[j++];  
        }  
    }  
    //可能有部分没排序完  
    while (i <= m) tmp[k++] = arr[i++];  
    while (j <= r) tmp[k++] = arr[j++];  
    //复制数组  
    for (int i = l; i <= r; i++)  
        arr[i] = tmp[i - l];  
}  
  
template<typename T>  
void merge_sort_recursion(T *arr, int p, int q) {  
    if (arr == nullptr || p >= q) return;  
    int mid = p + ((q - p) >> 1);  
    // 递归排序做左边  
    merge_sort_recursion(arr, p, mid);  
    // 递归排序做右边  
    merge_sort_recursion(arr, mid + 1, q);  
    // 归并  
    merge(arr, p, mid, q);  
}

迭代实现

template<typename T>  
void merge(T *arr, int l, int m, int r) {  
    //创建临时数组用于存放排序后的数据  
    T tmp[r - l + 1];  
    int i = l, j = m + 1, k = 0;  
    while (i <= m && j <= r) {  
        if (arr[i] <= arr[j]) {  
            tmp[k++] = arr[i++];  
        } else {  
            tmp[k++] = arr[j++];  
        }  
    }  
    //可能有部分没排序完  
    while (i <= m) tmp[k++] = arr[i++];  
    while (j <= r) tmp[k++] = arr[j++];  
    //复制数组  
    for (int i = l; i <= r; i++)  
        arr[i] = tmp[i - l];  
}
template<typename T>  
void merge_sort_iterative(T *arr, int p, int q) {  
    if (arr == nullptr || p >= q) return;  
    int len = q - p + 1;  
    for (int step = 1; step < len; step *= 2) {  
        for (int l = p; l <= q; l += step * 2) {  
            int mid = std::min(l + step - 1, q);  
            int r = std::min(l + step * 2 - 1, q);  
            if (mid < r)  
                merge(arr, l, mid, r);  
        }  
    }  
}

快速排序

快速排序（Quick Sort）是一种高效的排序算法，基于分治法（Divide and Conquer）的思想。它的核心是通过选择一个基准元素（pivot），将列表分为两部分：一部分小于基准元素，另一部分大于基准元素，然后递归地对这两部分进行排序。

实现步骤如下：

选择基准元素：从列表中选择一个元素作为基准（pivot）。选择方式可以是第一个元素、最后一个元素、中间元素或随机元素。
分区：将列表重新排列，使得所有小于基准元素的元素都在基准的左侧，所有大于基准元素的元素都在基准的右侧。基准元素的位置在分区完成后确定。
递归排序：对基准元素左侧和右侧的子列表分别递归地进行快速排序。
合并：由于分区操作是原地进行的，递归结束后整个列表已经有序。

以下动图以最后一个元素为基准：

假设有一个待排序的列表 [3, 6, 8, 10, 1, 2, 1]，选择最后一个元素作为基准（pivot），排序过程如下：

初始状态：
- 列表：[3, 6, 8, 10, 1, 2, 1]。
- 基准元素：1（最后一个元素）。
第一轮分区：
- 将小于基准的元素放在左侧，大于基准的元素放在右侧。
- 分区后列表：[1, 1, 2, 10, 6, 8, 3]。
- 基准元素 1 的位置确定。
递归排序：
- 对左侧子列表 [1] 和右侧子列表 [2, 10, 6, 8, 3] 分别进行快速排序。
- 左侧子列表已经有序。
- 对右侧子列表 [2, 10, 6, 8, 3] 选择基准元素 3（最后一个元素）：
  - 分区后列表：[2, 3, 6, 8, 10]。
  - 基准元素 3 的位置确定。
- 继续递归排序右侧子列表 [6, 8, 10]：
  - 选择基准元素 10（最后一个元素）：
    - 分区后列表：[6, 8, 10]。
    - 基准元素 10 的位置确定。
  - 继续递归排序左侧子列表 [6, 8]：
    - 选择基准元素 8（最后一个元素）：
      - 分区后列表：[6, 8]。
      - 基准元素 8 的位置确定。
    - 继续递归排序左侧子列表 [6]，已经有序。
最终结果：
- 列表完全有序：[1, 1, 2, 3, 6, 8, 10]。

递归实现

template<typename T>  
void quick_sort_recursion(T *arr, int p, int q) {  
    if (arr == nullptr || p >= q) return;  
    //以中间元素为基准  
    int pivot_pos = p + ((q - p) >> 1);  
    T pivot = arr[pivot_pos];  
    int l = p, r = q;  
    while (l <= r) {  
        //找到左边大于基准的值  
        while (arr[l] < pivot) l++;  
        //找到右边小于基准的值  
        while (arr[r] > pivot) r--;  
        if (l <= r)  
            std::swap(arr[l++], arr[r--]);  
    }  
    quick_sort_recursion(arr, p, r); //[p,r]所有小于基准值的数  
    quick_sort_recursion(arr, l, q); //[l,q]所有大于基准值的数  
}

迭代实现

template<typename T>  
void quick_sort_iterative(T *arr, int p, int q) {  
    if (arr == nullptr || p >= q) return;  
  
    std::stack<std::pair<int, int> > stack;  
    stack.push(std::make_pair(p, q));  
  
    while (!stack.empty()) {  
        int start = stack.top().first;  
        int end = stack.top().second;  
        stack.pop();  
  
        if (start >= end) continue;  
  
        // 与原递归版本相同的划分逻辑  
        int pivot_pos = start + ((end - start) >> 1);  
        T pivot = arr[pivot_pos];  
        int l = start, r = end;  
        while (l <= r) {  
            while (arr[l] < pivot) l++;  
            while (arr[r] > pivot) r--;  
            if (l <= r) {  
                std::swap(arr[l++], arr[r--]);  
            }  
        }  
  
        // 根据划分结果压栈，先压右侧区间（后处理），再压左侧区间（先处理）  
        if (start < r) {  
            stack.push(std::make_pair(start, r));  
        }  
        if (l < end) {  
            stack.push(std::make_pair(l, end));  
        }  
    }  
}

计数排序

计数排序（Counting Sort）是一种非比较型的排序算法，适用于对整数或有限范围内的数据进行排序。它的核心思想是通过统计每个元素的出现次数，然后根据统计结果将元素放回正确的位置。计数排序的时间复杂度为 O(n + k)，其中 n 是待排序元素的数量，k 是数据的范围大小。

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是 有确定范围的整数 。

算法的步骤如下：

统计频率：遍历待排序的列表，统计每个元素出现的次数，存储在一个计数数组中。
累加频率：将计数数组中的值累加，得到每个元素在排序后列表中的最后一个位置。
构建有序列表：遍历待排序的列表，根据计数数组中的位置信息，将元素放到正确的位置。
输出结果：将排序后的列表输出。

void counting_sort(int *arr, int n) {  
    if (arr == nullptr || n <= 0) return;  
    int max_val = *std::max_element(arr, arr + n);  
    int min_val = *std::min_element(arr, arr + n);  
    // 最大值和最小值的差值+1（0）为计数数组的长度  
    int len = max_val - min_val + 1;  
    int count[len] = {0};  
    //计数  
    for (int i = 0; i < n; i++)  
        ++count[arr[i] - min_val];  
    //填充原数组  
    int x = 0;  
    for (int i = 0; i < len; i++) {  
        for (int j = 0; j < count[i]; j++) {  
            arr[x++] = i; //下标i是数据  count[i]是数量  
        }  
    }  
}

桶排序

桶排序（Bucket Sort）是一种分布式排序算法，它将待排序的元素分配到若干个桶（Bucket）中，然后对每个桶中的元素进行排序，最后将所有桶中的元素按顺序合并。桶排序的核心思想是将数据分到有限数量的桶中，每个桶再分别排序（可以使用其他排序算法或递归地使用桶排序）。

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

在额外空间充足的情况下，尽量增大桶的数量
使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

算法步骤：

初始化桶：根据数据的范围和分布，创建若干个桶。
分配元素：遍历待排序的列表，将每个元素分配到对应的桶中。
排序每个桶：对每个桶中的元素进行排序（可以使用插入排序、快速排序等）。
合并桶：将所有桶中的元素按顺序合并，得到最终排序结果。

template<typename T>  
void bucket_sort(T *arr, int n) {  
    if (arr == nullptr || n <= 0) return;  
    //设置桶数量  
    const int bucket_size = 10;  
    T max_val = *std::max_element(arr, arr + n);  
    T min_val = *std::min_element(arr, arr + n);  
    // 将每个数放到指定的桶里面  
    int bucket_range = (max_val - min_val + 1) / bucket_size;  
    std::vector<std::vector<T> > buckets(bucket_size, std::vector<T>());  
    for (int i = 0; i < n; i++) {  
        buckets[(arr[i] - min_val) / bucket_range].push_back(arr[i]);  
    }  
    //对每个桶进行排序  
    for (int i = 0; i < bucket_size; i++) {  
        std::sort(buckets[i].begin(), buckets[i].end());  
    }  
}

基数排序

基数排序（Radix Sort）是一种非比较型的排序算法，它通过逐位比较元素的每一位（从最低位到最高位）来实现排序。基数排序的核心思想是将整数按位数切割成不同的数字，然后按每个位数分别进行排序。基数排序的时间复杂度为 O(n * k)，其中 n 是列表长度，k 是最大数字的位数。

算法步骤：

确定最大位数：找到列表中最大数字的位数，确定需要排序的轮数。
按位排序：从最低位开始，依次对每一位进行排序（通常使用计数排序或桶排序作为子排序算法）。
合并结果：每一轮排序后，更新列表的顺序，直到所有位数排序完成。

基数排序：根据键值的每位数字来分配桶；
计数排序：每个桶只存储单一键值；
桶排序：每个桶存储一定范围的数值；

void radix_sort(int *arr, int n) {  
    if (n <= 0) return;  
  
    // 找到最大绝对值，确定最大位数  
    int max_val = *std::max_element(arr, arr + n);  
    int min_val = *std::min_element(arr, arr + n);  
    int max_abs = std::max(std::abs(max_val), std::abs(min_val));  
  
    // 从最低位到最高位进行排序  
    for (int exp = 1; exp <= max_abs; exp *= 10) {  
        std::vector<std::vector<int> > buckets(19); // -9到+9共19个桶  
  
        // 分配到桶中（包含负数）  
        for (int i = 0; i < n; i++) {  
            int digit = (arr[i] / exp) % 10;  
            buckets[digit + 9].push_back(arr[i]); // +9映射负数  
        }  
  
        // 收集桶中数据  
        int pos = 0;  
        for (auto &bucket: buckets) {  
            for (int val: bucket) {  
                arr[pos++] = val;  
            }  
        }  
    }  
}

堆排序

堆是具有以下性质的完全二叉树 ：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

如下图：

同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

大顶堆 ：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆 ：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

接下来看一下堆排序的基本思想和步骤：

堆排序的基本思想 ：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

步骤一构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。

假设给定无序序列结构如下；
此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。
找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。
这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。

此时，我们就将一个无需序列构造成了一个大顶堆。

步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

将堆顶元素9和末尾元素4进行交换
重新调整结构，使其继续满足堆定义
再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.
后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

// 调整以 i 为根的子树为最大堆 下标从0开始  
template<typename T>  
void heapify(T *arr, int n, int i) {  
    int largest = i; // 初始化最大元素为根节点  
    int left = 2 * i + 1; // 左子节点索引  
    int right = 2 * i + 2; // 右子节点索引  
  
    // 找到根节点和两个子节点中的最大值  
    if (left < n && arr[left] > arr[largest])  
        largest = left;  
    if (right < n && arr[right] > arr[largest])  
        largest = right;  
  
    // 如果最大值不是根节点，则交换并递归调整  
    if (largest != i) {  
        std::swap(arr[i], arr[largest]);  
        heapify(arr, n, largest);  
    }  
}  
  
template<typename T>  
void heap_sort(T *arr, int n) {  
    // 构建大顶堆堆（从最后一个非叶子节点开始）  
    // 排序后数组从小到大  
    for (int i = n / 2 - 1; i >= 0; i--)  
        heapify(arr, n, i);  
  
    // 依次提取最大元素并调整堆  
    for (int i = n - 1; i > 0; i--) {  
        std::swap(arr[0], arr[i]); // 将当前最大值移到数组末尾  
        heapify(arr, i, 0); // 对剩余元素重新堆化  
    }  
}

附录

#include <algorithm>  
#include <iostream>  
#include <stack>  
#include <algorithm>  
#include <cmath>  
#include  <vector>  
  
template<typename T>  
void bubble_sort(T *arr, int n) {  
    for (int i = 0; i < n; i++) {  
        bool flag = false;  
        for (int j = 0; j < n - i - 1; j++) {  
            if (arr[j] > arr[j + 1]) {  
                flag = true;  
                std::swap(arr[j], arr[j + 1]);  
            }  
        }  
        //没有交换则说明有序了退出  
        if (!flag) break;  
    }  
}  
  
template<typename T>  
void selection_sort(T *arr, int n) {  
    for (int i = 0; i < n; i++) {  
        int min = i;  
        //每次循环中记录最小值的下标  
        for (int j = i + 1; j < n; j++) {  
            if (arr[j] < arr[min]) {  
                min = j;  
            }  
        }  
        std::swap(arr[i], arr[min]);  
    }  
}  
  
template<typename T>  
void insertion_sort(T *arr, int n) {  
    // 第一个值默认有序  
    //每轮循环中[0，j]都是有序的  
    for (int i = 1; i < n; i++) {  
        int key = arr[i], j = i - 1;  
        //向前寻找大于key的数，全部后移  
        while (j >= 0 && arr[j] > key) {  
            arr[j + 1] = arr[j];  
            j--;  
        }  
        arr[j + 1] = key;  
    }  
}  
  
template<typename T>  
void shell_sort(T *arr, int n) {  
    int gap = n / 2;  
    while (gap > 0) {  
        for (int i = gap; i < n; i++) {  
            T key = arr[i];  
            int j = i - gap;  
            while (j >= 0 && arr[j] > key) {  
                arr[j + gap] = arr[j];  
                j = j - gap;  
            }  
            arr[j + gap] = key;  
        }  
        gap = gap / 2;  
    }  
}  
  
template<typename T>  
void merge(T *arr, int l, int m, int r) {  
    //创建临时数组用于存放排序后的数据  
    T tmp[r - l + 1];  
    int i = l, j = m + 1, k = 0;  
    while (i <= m && j <= r) {  
        if (arr[i] <= arr[j]) {  
            tmp[k++] = arr[i++];  
        } else {  
            tmp[k++] = arr[j++];  
        }  
    }  
    //可能有部分没排序完  
    while (i <= m) tmp[k++] = arr[i++];  
    while (j <= r) tmp[k++] = arr[j++];  
    //复制数组  
    for (int i = l; i <= r; i++)  
        arr[i] = tmp[i - l];  
}  
  
template<typename T>  
void merge_sort_recursion(T *arr, int p, int q) {  
    if (arr == nullptr || p >= q) return;  
    int mid = p + ((q - p) >> 1);  
    // 递归排序做左边  
    merge_sort_recursion(arr, p, mid);  
    // 递归排序做右边  
    merge_sort_recursion(arr, mid + 1, q);  
    // 归并  
    merge(arr, p, mid, q);  
}  
  
template<typename T>  
void merge_sort_iterative(T *arr, int p, int q) {  
    if (arr == nullptr || p >= q) return;  
    int len = q - p + 1;  
    for (int step = 1; step < len; step *= 2) {  
        for (int l = p; l <= q; l += step * 2) {  
            int mid = std::min(l + step - 1, q);  
            int r = std::min(l + step * 2 - 1, q);  
            if (mid < r)  
                merge(arr, l, mid, r);  
        }  
    }  
}  
  
template<typename T>  
void quick_sort_recursion(T *arr, int p, int q) {  
    if (arr == nullptr || p >= q) return;  
    //以中间元素为基准  
    int pivot_pos = p + ((q - p) >> 1);  
    T pivot = arr[pivot_pos];  
    int l = p, r = q;  
    while (l <= r) {  
        //找到左边大于基准的值  
        while (arr[l] < pivot) l++;  
        //找到右边小于基准的值  
        while (arr[r] > pivot) r--;  
        if (l <= r)  
            std::swap(arr[l++], arr[r--]);  
    }  
    quick_sort_recursion(arr, p, r); //[p,r]所有小于基准值的数  
    quick_sort_recursion(arr, l, q); //[l,q]所有大于基准值的数  
}  
  
template<typename T>  
void quick_sort_iterative(T *arr, int p, int q) {  
    if (arr == nullptr || p >= q) return;  
  
    std::stack<std::pair<int, int> > stack;  
    stack.push(std::make_pair(p, q));  
  
    while (!stack.empty()) {  
        int start = stack.top().first;  
        int end = stack.top().second;  
        stack.pop();  
  
        if (start >= end) continue;  
  
        // 与原递归版本相同的划分逻辑  
        int pivot_pos = start + ((end - start) >> 1);  
        T pivot = arr[pivot_pos];  
        int l = start, r = end;  
        while (l <= r) {  
            while (arr[l] < pivot) l++;  
            while (arr[r] > pivot) r--;  
            if (l <= r) {  
                std::swap(arr[l++], arr[r--]);  
            }  
        }  
  
        // 根据划分结果压栈，先压右侧区间（后处理），再压左侧区间（先处理）  
        if (start < r) {  
            stack.push(std::make_pair(start, r));  
        }  
        if (l < end) {  
            stack.push(std::make_pair(l, end));  
        }  
    }  
}  
  
void counting_sort(int *arr, int n) {  
    if (arr == nullptr || n <= 0) return;  
    int max_val = *std::max_element(arr, arr + n);  
    int min_val = *std::min_element(arr, arr + n);  
    // 最大值和最小值的差值+1（0）为计数数组的长度  
    int len = max_val - min_val + 1;  
    int count[len] = {0};  
    //计数  
    for (int i = 0; i < n; i++)  
        ++count[arr[i] - min_val];  
    //填充原数组  
    int x = 0;  
    for (int i = 0; i < len; i++) {  
        for (int j = 0; j < count[i]; j++) {  
            arr[x++] = i; //下标i是数据  count[i]是数量  
        }  
    }  
}  
  
template<typename T>  
void bucket_sort(T *arr, int n) {  
    if (arr == nullptr || n <= 0) return;  
    //设置桶数量  
    const int bucket_size = 10;  
    T max_val = *std::max_element(arr, arr + n);  
    T min_val = *std::min_element(arr, arr + n);  
    // 将每个数放到指定的桶里面  
    int bucket_range = (max_val - min_val + 1) / bucket_size;  
    std::vector<std::vector<T> > buckets(bucket_size, std::vector<T>());  
    for (int i = 0; i < n; i++) {  
        buckets[(arr[i] - min_val) / bucket_range].push_back(arr[i]);  
    }  
    //对每个桶进行排序  
    for (int i = 0; i < bucket_size; i++) {  
        std::sort(buckets[i].begin(), buckets[i].end());  
    }  
}  
  
void radix_sort(int *arr, int n) {  
    if (n <= 0) return;  
  
    // 找到最大绝对值，确定最大位数  
    int max_val = *std::max_element(arr, arr + n);  
    int min_val = *std::min_element(arr, arr + n);  
    int max_abs = std::max(std::abs(max_val), std::abs(min_val));  
  
    // 从最低位到最高位进行排序  
    for (int exp = 1; exp <= max_abs; exp *= 10) {  
        std::vector<std::vector<int> > buckets(19); // -9到+9共19个桶  
  
        // 分配到桶中（包含负数）  
        for (int i = 0; i < n; i++) {  
            int digit = (arr[i] / exp) % 10;  
            buckets[digit + 9].push_back(arr[i]); // +9映射负数  
        }  
  
        // 收集桶中数据  
        int pos = 0;  
        for (auto &bucket: buckets) {  
            for (int val: bucket) {  
                arr[pos++] = val;  
            }  
        }  
    }  
}  
  
// 调整以 i 为根的子树为最大堆 下标从0开始  
template<typename T>  
void heapify(T *arr, int n, int i) {  
    int largest = i; // 初始化最大元素为根节点  
    int left = 2 * i + 1; // 左子节点索引  
    int right = 2 * i + 2; // 右子节点索引  
  
    // 找到根节点和两个子节点中的最大值  
    if (left < n && arr[left] > arr[largest])  
        largest = left;  
    if (right < n && arr[right] > arr[largest])  
        largest = right;  
  
    // 如果最大值不是根节点，则交换并递归调整  
    if (largest != i) {  
        std::swap(arr[i], arr[largest]);  
        heapify(arr, n, largest);  
    }  
}  
  
template<typename T>  
void heap_sort(T *arr, int n) {  
    // 构建大顶堆堆（从最后一个非叶子节点开始）  
    // 排序后数组从小到大  
    for (int i = n / 2 - 1; i >= 0; i--)  
        heapify(arr, n, i);  
  
    // 依次提取最大元素并调整堆  
    for (int i = n - 1; i > 0; i--) {  
        std::swap(arr[0], arr[i]); // 将当前最大值移到数组末尾  
        heapify(arr, i, 0); // 对剩余元素重新堆化  
    }  
}  
  
  
int main() {  
    int arr[] = {-100, -53, 1, 4, 100, 111, 138, 191, 244, 2, 4, 5, 109, 209, 3, 9, 0, 4};  
    const int n = std::size(arr);  
    // bubble_sort(arr, n);  
    // selection_sort(arr, n);    
    // insertion_sort(arr, n);   
    // shell_sort(arr, n);    
    // merge_sort_recursion(arr, 0, n - 1);    
    // merge_sort_iterative(arr, 0, n - 1);    
    // quick_sort_recursion(arr, 0, n - 1);    
    // quick_sort_iterative(arr, 0, n - 1);    
    // bubble_sort(arr, n);    
    // counting_sort(arr, n);    
    // radix_sort(arr, n);    
    heap_sort(arr, n);  
    for (const int i: arr) {  
        std::cout << i << " ";  
    }  
}

阅读选项

冒泡排序

选择排序

插入排序

希尔排序

归并排序

递归实现

迭代实现

快速排序

递归实现

迭代实现

计数排序

桶排序

基数排序

堆排序

附录

冒泡排序

选择排序

插入排序

希尔排序

归并排序

递归实现

迭代实现

快速排序

递归实现

迭代实现

计数排序

桶排序

基数排序

堆排序

附录

微信分享二维码

猜您想看

二叉树的遍历

二分查找

零零碎碎的算法题

评论区(暂无评论)

我要评论

这里空空如也，快来评论吧~

支持作者