桶排序和基数排序

非比较排序是一种不依赖于元素比较大小的排序算法。

在排序过程中，非比较排序不需要通过比较元素的大小来确定它们的相对顺序，而是利用其他的技巧和数据结构来实现排序。

非比较排序算法通常具有较高的时间效率，并且在某些特定情况下甚至可以达到线性时间复杂度。

本文将介绍几种常见的非比较排序算法，包括计数排序、桶排序和基数排序，并对它们的原理和应用进行详细解释。

1. 计数排序计数排序是一种适用于特定范围内整数排序的线性时间复杂度的非比较排序算法。

其基本思想是统计每个元素出现的次数，然后根据元素的值和出现次数重新排列元素。

计数排序包括以下几个步骤：- 统计每个元素出现的次数，得到一个统计数组。

- 将统计数组转换为前缀和数组，表示每个元素在排序后的数组中的位置。

- 根据前缀和数组将元素重新排列到正确的位置上，完成排序过程。

计数排序适用于待排序元素范围不大的情况，时间复杂度为O(n+k)，其中n为待排序元素个数，k为元素范围大小。

2. 桶排序桶排序是一种对元素分布较为均匀的情况下效率较高的非比较排序算法。

桶排序将元素划分到若干个有序的桶中，然后对每个桶中的元素进行排序，最后按照桶的顺序将各个桶中的元素合并成有序序列。

桶排序的基本思想包括以下几个步骤：- 划分若干个桶，并确定元素划分规则。

- 将待排序元素分别放入对应的桶中。

- 对每个桶中的元素进行排序。

- 按照桶的顺序将各个桶中的元素合并成有序序列。

桶排序适用于元素分布较为均匀的情况，时间复杂度为O(n)，其中n为待排序元素个数。

3. 基数排序基数排序是一种多关键字排序算法，适用于对整数或字符串等具有多位数字符的序列进行排序。

基数排序的基本思想是从低位到高位依次对元素进行排序，最终得到有序序列。

基数排序包括以下几个步骤：- 从低位到高位依次对元素进行排序。

- 对每一位使用稳定的排序算法，如计数排序或桶排序。

- 重复上述步骤直到所有位都被排序完毕。

基数排序适用于多关键字排序的场景，时间复杂度为O(d(n+k))，其中d为关键字位数，n为待排序元素个数，k为关键字基数大小。

线性时间的排序算法前⾯已经介绍了⼏种排序算法，像插⼊排序（直接插⼊排序，折半插⼊排序，希尔排序）、交换排序（冒泡排序，快速排序）、选择排序（简单选择排序，堆排序）、2-路归并排序（见我的另⼀篇⽂章：）等，这些排序算法都有⼀个共同的特点，就是基于⽐较。

本⽂将介绍三种⾮⽐较的排序算法：计数排序，基数排序，桶排序。

它们将突破⽐较排序的Ω(nlgn)下界，以线性时间运⾏。

⼀、⽐较排序算法的时间下界所谓的⽐较排序是指通过⽐较来决定元素间的相对次序。

“定理：对于含n个元素的⼀个输⼊序列，任何⽐较排序算法在最坏情况下，都需要做Ω(nlgn)次⽐较。

”也就是说，⽐较排序算法的运⾏速度不会快于nlgn，这就是基于⽐较的排序算法的时间下界。

通过决策树（Decision-Tree）可以证明这个定理，关于决策树的定义以及证明过程在这⾥就不赘述了。

你可以⾃⼰去查找资料，推荐观看《》。

根据上⾯的定理，我们知道任何⽐较排序算法的运⾏时间不会快于nlgn。

那么我们是否可以突破这个限制呢？当然可以，接下来我们将介绍三种线性时间的排序算法，它们都不是通过⽐较来排序的，因此，下界Ω(nlgn)对它们不适⽤。

⼆、计数排序（Counting Sort）计数排序的基本思想就是对每⼀个输⼊元素x，确定⼩于x的元素的个数，这样就可以把x直接放在它在最终输出数组的位置上，例如：算法的步骤⼤致如下：找出待排序的数组中最⼤和最⼩的元素统计数组中每个值为i的元素出现的次数，存⼊数组C的第i项对所有的计数累加（从C中的第⼀个元素开始，每⼀项和前⼀项相加）反向填充⽬标数组：将每个元素i放在新数组的第C(i)项，每放⼀个元素就将C(i)减去1C++代码：/*************************************************************************> File Name: CountingSort.cpp> Author: SongLee> E-mail: lisong.shine@> Created Time: 2014年06⽉11⽇星期三 00时08分55秒> Personal Blog: http://songlee24.github.io************************************************************************/#include<iostream>using namespace std;/**计数排序：A和B为待排和⽬标数组，k为数组中最⼤值,len为数组长度*/void CountingSort(int A[], int B[], int k, int len){int C[k+1];for(int i=0; i<k+1; ++i)C[i] = 0;for(int i=0; i<len; ++i)C[A[i]] += 1;for(int i=1; i<k+1; ++i)C[i] = C[i] + C[i-1];for(int i=len-1; i>=0; --i){B[C[A[i]]-1] = A[i];C[A[i]] -= 1;}}/* 输出数组 */void print(int arr[], int len){for(int i=0; i<len; ++i)cout << arr[i] << " ";cout << endl;}/* 测试 */int main(){int origin[8] = {4,5,3,0,2,1,15,6};int result[8];print(origin, 8);CountingSort(origin, result, 15, 8);print(result, 8);return 0;}当输⼊的元素是0到k之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)。

所有排序的原理排序是将一组数据按照某种特定顺序进行排列的过程。

在计算机科学中，排序是一种基本的算法问题，涉及到许多常见的排序算法。

排序算法根据其基本原理和实现方式的不同，可以分为多种类型，如比较排序、非比较排序、稳定排序和非稳定排序等。

下面将详细介绍排序的原理和各种排序算法。

一、比较排序的原理比较排序是指通过比较数据之间的大小关系来确定数据的相对顺序。

所有常见的比较排序算法都基于这种原理，包括冒泡排序、插入排序、选择排序、归并排序、快速排序、堆排序等。

比较排序算法的时间复杂度一般为O(n^2)或O(nlogn)，其中n是待排序元素的数量。

1. 冒泡排序原理冒泡排序是一种简单的比较排序算法，其基本思想是从待排序的元素中两两比较相邻元素的大小，并依次将较大的元素往后移，最终将最大的元素冒泡到序列的尾部。

重复这个过程，直到所有元素都有序。

2. 插入排序原理插入排序是一种简单直观的比较排序算法，其基本思想是将待排序序列分成已排序和未排序两部分，初始状态下已排序部分只包含第一个元素。

然后，依次将未排序部分的元素插入到已排序部分的正确位置，直到所有元素都有序。

3. 选择排序原理选择排序是一种简单直观的比较排序算法，其基本思想是每次从待排序的元素中选择最小（或最大）的元素，将其放到已排序部分的末尾。

重复这个过程，直到所有元素都有序。

4. 归并排序原理归并排序是一种典型的分治策略下的比较排序算法，其基本思想是将待排序的元素不断地二分，直到每个子序列只包含一个元素，然后将相邻的子序列两两归并，直到所有元素都有序。

5. 快速排序原理快速排序是一种常用的比较排序算法，其基本思想是通过一趟排序将待排序的元素分割成两部分，其中一部分的元素均比另一部分的元素小。

然后，对这两部分元素分别进行快速排序，最终将整个序列排序完成。

6. 堆排序原理堆排序是一种常用的比较排序算法，其基本思想是利用堆这种数据结构对待排序的元素进行排序。

基数排序和桶排序的区别1.桶排序(bucket sort)基本思路是：将待排序元素划分到不同的痛。

先扫描一遍序列求出最大值maxv 和最小值 minv ，设桶的个数为 k ，则把区间 [minv, maxv] 均匀划分成 k 个区间，每个区间就是一个桶。

将序列中的元素分配到各自的桶。

对每个桶内的元素进行排序。

可以选择任意一种排序算法。

将每个桶中的元素组合成一个大的有序序列。

假设数据是均匀分布的，则每个桶的元素平均个数为 n/k 。

假设选择用快速排序对每个桶内的元素进行排序，那么每次排序的时间复杂度为 o(n/klog(n/k)) 。

总的时间复杂度为 o(n)+o(m)o(n/klog(n/k)) =o(n+nlog(n/k)) = o(n+nlogn-nlogk 。

当 k 接近于 n 时，桶排序的时间复杂度就可以金斯认为是o(n) 的。

即桶越多，时间效率就越高，而桶越多，空间就越大。

2.计数排序(counting sort)是一种o(n)的排序算法，其思路是开一个长度为 maxvalue-minvalue+1 的数组，然后分配。

扫描一遍原始数组，以当前值- minvalue 作为下标，将该下标的计数器增1。

收藏。

扫描一次计数器数组，并按顺序收集值。

举个例子， nums=[2, 1, 3, 1, 5] , 首先扫描一遍获取最小值和最大值，maxvalue=5 , minvalue=1 ，于是开一个长度为5的计数器数组 counter ，1. 分配。

统计每个元素出现的频率，得到 counter=[2, 1, 1, 0, 1] ，例如 counter[0] 表示值 0+minvalue=1 出现了2次。

2. 收集。

counter[0]=2 表示 1 出现了两次，那就向原始数组写入两个1，3. counter[1]=1 表示 2 出现了1次，那就向原始数组写入一个2，依次类推，最终原始数组变为 [1,1,2,3,5] ，排序好了。

排序有哪几种方法排序是计算机科学中非常重要的概念之一，它指的是将一组元素按照某种规则进行重新排列的过程。

排序算法可以分为多种类型，包括插入排序、交换排序、选择排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序等。

下面我将详细介绍每种排序方法的原理、特点和应用场景。

1. 插入排序（Insertion Sort）插入排序是一种简单且直观的排序算法。

它的原理是将一个未排序的元素逐个地插入到已排序的部分中，最终形成一个完全有序的序列。

具体操作是从第二个元素开始，将其与前面已排序的元素逐个比较并插入到正确的位置。

插入排序的时间复杂度为O(n^2)，适用于小规模或部分有序的序列。

2. 交换排序（Exchange Sort）交换排序包括冒泡排序和快速排序。

冒泡排序（Bubble Sort）的原理是从头到尾依次比较相邻的两个元素，如果顺序不对则交换位置，一轮下来可以将最大的元素移动到末尾。

快速排序（Quick Sort）使用了分治的思想，通过选择一个基准元素将序列分成左右两部分，左边的元素都小于该基准值，右边的元素都大于该基准值，然后递归地对左右两部分进行快速排序。

交换排序的平均时间复杂度为O(nlogn)，适合用于排序大规模随机数据。

3. 选择排序（Selection Sort）选择排序的原理很简单：每一次从未排序的部分中选择最小（或最大）的元素，放到已排序部分的末尾。

具体操作是通过不断找到最小元素的索引，然后将其与第一个未排序元素交换，如此循环直到所有元素都被排序。

选择排序的时间复杂度为O(n^2)，适用于简单的排序需求。

4. 归并排序（Merge Sort）归并排序采用了分治的思想，将一个序列递归地分成两个子序列，直到每个子序列只有一个元素，然后将两个有序的子序列合并成一个有序的序列。

具体操作是比较两个子序列的第一个元素，将较小的元素放入结果序列，然后再比较较小元素所在子序列的下一个元素与另一个子序列的第一个元素，直到所有元素都被放入结果序列。

常用的选择类排序方法一、冒泡排序法冒泡排序法是一种简单直观的排序方法，它重复地遍历要排序的列表，比较相邻的元素并按照大小交换位置，直到整个列表排序完成。

该方法的时间复杂度为O(n^2)，在大规模数据排序时效率较低。

冒泡排序的优点是实现简单，代码易于理解和实现。

二、插入排序法插入排序法是一种稳定的排序方法，它通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序法的时间复杂度为O(n^2)，但是在小规模数据排序时效率较高。

插入排序的优点是实现简单，对于部分有序的数据集合，排序效率较高。

三、选择排序法选择排序法是一种简单直观的排序方法，它将待排序的列表分为有序和无序两部分，每次从无序部分选择最小（或最大）的元素放到有序部分的末尾，直到整个列表排序完成。

选择排序法的时间复杂度为O(n^2)，在大规模数据排序时效率较低。

选择排序的优点是实现简单，对于大规模数据排序时空间复杂度较低。

四、快速排序法快速排序法是一种常用的排序方法，它基于分治的思想，通过递归地将列表分成较小和较大的两个子序列，然后对子序列进行排序，最后将排序好的子序列合并成有序的列表。

快速排序法的时间复杂度为O(nlogn)，在大规模数据排序时效率较高。

快速排序的优点是实现简单，排序速度快。

五、归并排序法归并排序法是一种稳定的排序方法，它通过将列表递归地分成较小的子序列，对子序列进行排序，然后将排序好的子序列合并成有序的列表。

归并排序法的时间复杂度为O(nlogn)，在大规模数据排序时效率较高。

归并排序的优点是稳定性好，适用于大规模数据排序。

六、堆排序法堆排序法是一种常用的排序方法，它利用堆这种数据结构进行排序。

堆是一棵完全二叉树，可以通过数组来表示。

堆排序法通过构建最大堆或最小堆，将堆的根节点与最后一个叶子节点交换，然后重新调整堆，直到整个列表排序完成。

堆排序法的时间复杂度为O(nlogn)，在大规模数据排序时效率较高。

排序算法十大经典方法
排序算法是计算机科学中的经典问题之一，它们用于将一组元素按照一定规则排序。

以下是十大经典排序算法：
1. 冒泡排序：比较相邻元素并交换，每一轮将最大的元素移动到最后。

2. 选择排序：每一轮选出未排序部分中最小的元素，并将其放在已排序部分的末尾。

3. 插入排序：将未排序部分的第一个元素插入到已排序部分的合适位置。

4. 希尔排序：改进的插入排序，将数据分组排序，最终合并排序。

5. 归并排序：将序列拆分成子序列，分别排序后合并，递归完成。

6. 快速排序：选定一个基准值，将小于基准值的元素放在左边，大于基准值的元素放在右边，递归排序。

7. 堆排序：将序列构建成一个堆，然后一次将堆顶元素取出并调整堆。

8. 计数排序：统计每个元素出现的次数，再按照元素大小输出。

9. 桶排序：将数据分到一个或多个桶中，对每个桶进行排序，最后输出。

10. 基数排序：按照元素的位数从低到高进行排序，每次排序只考虑一位。

以上是十大经典排序算法，每个算法都有其优缺点和适用场景，选择合适的算法可以提高排序效率。

「⼲货」编程语⾔⼗⼤经典算法，你知道⼏个？算法与数据结构是计算机学习路上的内功⼼法，也是学好编程语⾔的重要基础。

今天给⼤家介绍⼀下⼗⼤经典算法。

⼗⼤经典算法分别是：冒泡排序，插⼊排序，选择排序，希尔排序，快速排序，归并排序，桶排序，堆排序，计数排序，基数排序。

预备知识：算法稳定性如果a==b，排序前a在b的前⾯，排序后a在b的后⾯，只要会出现这种现象，我们则说这个算法不稳定（即使两个相等的数，在排序的过程中不断交换，有可能将后⾯的b交换到a的前⾯去）。

⼀、冒泡排序冒泡排序（Bubble Sort）是基于交换的排序，它重复⾛过需要排序的元素，依次⽐较相邻的两个元素的⼤⼩，保证最后⼀个数字⼀定是最⼤的，即它的顺序已经排好，下⼀轮只需要保证前⾯n-1个元素的顺序即可。

之所以称为冒泡，是因为最⼤/最⼩的数，每⼀次都往后⾯冒，就像是⽔⾥⾯的⽓泡⼀样。

排序的步骤如下：1. 从头开始，⽐较相邻的两个数，如果第⼀个数⽐第⼆个数⼤，那么就交换它们位置。

2. 从开始到最后⼀对⽐较完成，⼀轮结束后，最后⼀个元素的位置已经确定。

3. 除了最后⼀个元素以外，前⾯的所有未排好序的元素重复前⾯两个步骤。

4. 重复前⾯ 1 ～ 3 步骤，直到都已经排好序。

例如，我们需要对数组[98，90，34，56，21]进⾏从⼩到⼤排序，每⼀次都需要将数组最⼤的移动到数组尾部。

那么排序的过程如下动图所⽰：⼆、选择排序前⾯说的冒泡排序是每⼀轮⽐较确定最后⼀个元素，中间过程不断地交换。

⽽选择排序就是每次选择剩下的元素中最⼩的那个元素，直到选择完成。

排序的步骤如下：从第⼀个元素开始，遍历其后⾯的元素，找出其后⾯⽐它更⼩的元素，若有，则两者交换，保证第⼀个元素最⼩。

对第⼆个元素⼀样，遍历其后⾯的元素，找出其后⾯⽐它更⼩的元素，若存在，则两者交换，保证第⼆个元素在未排序的数中（除了第⼀个元素）最⼩。

依次类推，直到最后⼀个元素，那么数组就已经排好序了。

【十大经典排序算法（动图演示）】必学十大经典排序算法0.1 算法分类十种常见排序算法可以分为两大类：比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。

非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

0.2 算法复杂度0.3 相关概念稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。

不稳定：如果a原本在b的前面，而a=b，排序之后a 可能会出现在b 的后面。

时间复杂度：对排序数据的总的操作次数。

反映当n变化时，操作次数呈现什么规律。

空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

1、冒泡排序（Bubble Sort）冒泡排序是一种简单的排序算法。

它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。

走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

1.1 算法描述比较相邻的元素。

如果第一个比第二个大，就交换它们两个；对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；针对所有的元素重复以上的步骤，除了最后一个；重复步骤1~3，直到排序完成。

1.2 动图演示1.3 代码实现1.unction bubbleSort(arr) {2. varlen = arr.length;3. for(vari = 0; i arr[j+1]) {// 相邻元素两两对比6. vartemp = arr[j+1];// 元素交换7. arr[j+1] = arr[j];8. arr[j] = temp;9. }10. }11. }12. returnarr;13.}2、选择排序（Selection Sort）选择排序(Selection-sort)是一种简单直观的排序算法。

python实现⼗⼤经典算法排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进⾏排序，⽽外部排序是因排序的数据很⼤，⼀次不能容纳全部的排序记录，在排序过程中需要访问外存。

常见的内部排序算法有：插⼊排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。

⽤⼀张图概括：关于时间复杂度：1. 平⽅阶 (O(n2)) 排序各类简单排序：直接插⼊、直接选择和冒泡排序。

2. 线性对数阶 (O(nlog2n)) 排序快速排序、堆排序和归并排序。

3. O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。

希尔排序。

4. 线性阶 (O(n)) 排序基数排序，此外还有桶、箱排序。

关于稳定性：稳定的排序算法：冒泡排序、插⼊排序、归并排序和基数排序。

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

名词解释：n：数据规模k：“桶”的个数In-place：占⽤常数内存，不占⽤额外内存Out-place：占⽤额外内存稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同冒泡排序冒泡排序（Bubble Sort）也是⼀种简单直观的排序算法。

它重复地⾛访过要排序的数列，⼀次⽐较两个元素，如果他们的顺序错误就把他们交换过来。

⾛访数列的⼯作是重复地进⾏直到没有再需要交换，也就是说该数列已经排序完成。

这个算法的名字由来是因为越⼩的元素会经由交换慢慢“浮”到数列的顶端。

作为最简单的排序算法之⼀，冒泡排序给我的感觉就像 Abandon 在单词书⾥出现的感觉⼀样，每次都在第⼀页第⼀位，所以最熟悉。

冒泡排序还有⼀种优化算法，就是⽴⼀个 flag，当在⼀趟序列遍历中元素没有发⽣交换，则证明该序列已经有序。

但这种改进对于提升性能来说并没有什么太⼤作⽤。

1. 算法步骤1. ⽐较相邻的元素。

如果第⼀个⽐第⼆个⼤，就交换他们两个。

2. 对每⼀对相邻元素作同样的⼯作，从开始第⼀对到结尾的最后⼀对。