【算法导论】 内部排序算法总结
| 排序名称 | 时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|
| 直接插入排序 | O(n^2) | O(1) | 稳定 |
| 折半插入排序 | O(n^2) | O(1) | 稳定 |
| 希尔排序 | O(n^2) | O(1) | 不稳定 |
| 冒泡排序 | O(n^2) | O(1) | 稳定 |
| 快速排序 | O(n*logn) | O(1) | 不稳定 |
| 简单选择排序 | O(n^2) | O(1) | 不稳定 |
| 堆排序 | O(n*logn) | O(1) | 不稳定 |
| 归并排序 | O(n*logn) | O(n) | 稳定 |
| 计数排序 | O(k+n) | O(k+n) | 稳定 |
| 基数排序 | O( d(k+n) ) | O(k+n) | 稳定 |
| 桶排序 | O(n) | O(n+m) | 稳定 |
比较排序的下界
比较排序通过元素之间的比较确定元素的位置。例如给定两个元素a、b，共有a≥b，a>b，a=b，a＜b，a≤b五种比较方式，假设排序中给定的元素都是互异的，则不存在a=b这种比较方式。剩下的≥、＞、＜、≤四中比较方式是等价的，因为通过它们得到的a、b的相对次序信息都是相同的。
假设采用≤这种比较方式（下同），若a≤b为真，将a调整到b的位置前，若a≤b为假，将a调整到b之后，a、b有序。
决策树模型：比较排序可以抽象为一棵决策树（决策树是完全二叉树），决策树的所有内部结点以 i : j 表示(1≤ i，j≤n)，表示对a[ i ]、a[ j ] 进行比较，若i≤j为真，进入其的左子树，若i≤j为假，进入其右子树。直至一系列比较后，到达叶子节点。叶子节点存储一个序列<π1、π2 . . . πn>（1≤ k，πk≤n），表示<a_π1 、a_π2 . . . a_πn>已经有序。以数组a中有3个元素为例，见下图：
对于数列a1、a2、a3，比较a1≤a2是否为真，若为真继续比较a2≤a3，若a2≤a3为真那么数列的顺序为：a1、a2、a3. 若为假则在右子树继续进行判断。假设现有数组a = { 5, 7, 3} 进行排序，首先比较a1≤a2，为真，继续比较a2≤a3，为假，继续比较a1≤a3，为假，此时到达叶节点<3,1,2>，则可得出排序后的结果：a3、a1、a2，即3、5、7。
对于任意n个元素的排序，都可以构建这样一颗决策树，且叶子节点的数目至少为n!个（对于每种不同的情况都能在叶子节点上找到对应的输出，例如上述决策树共有6个叶子结点，包含1、2、3的所有可能组合）。
那么一个比较排序算法在最坏情况下的比较次数为h（h为决策树的高度），且 h ≥ log(n!) = Ω( n logn )；
结论： 最坏情况下，任何比较排序算法都需要做Ω( n logn )次比较。
堆排序和归并排序的运行时间都为O( n logn)，因此两者都是渐进最优的比较排序算法。
Ps：O --渐进上界 Ω --渐进下界 Θ--渐进紧确界
插入排序----直接插入排序 （Straight Insertion Sort）
对于数组a[1...n]，对于k（k从1开始，到n结束），依次调整a[k]的位置，使得a[1...k]为有序数组。
当k = n时，则完成排序，a[1...n] 成为有序数组。
直接插入排序写起来比较简单，适用于数据量较少、对时间要求不高的场景。
/**
* 直接插入排序
* zhanw15 @2018/4/9
*/
#include<stdio.h>
#define N 11
void insort( int *a, int n)
{
int i, j, temp; //临时保存a[i]
for( i=0; i<n; i++) {
temp = a[i];
for( j=i-1; j>=0 && a[j]>temp; j--) {
a[j+1] = a[j];
} //向前移动大于temp的元素
a[j+1] = temp;
}
}
int main()
{
int i=0;
int a[N] = { 13, 24, 35, 15, 27, 39, 30, 4, 23, 21, 6};
for( i=0; i<N; i++) printf( "%d ", a[i]);
printf( "\n");
insort( a, N);
for( i=0; i<N; i++) printf( "%d ", a[i]);
printf( "\n");
return 0;
}
//output:
// 13 24 35 15 27 39 30 4 23 21 6
// 4 6 13 15 21 23 24 27 30 35 39插入排序----折半插入排序 （Binary Insertion Sort）
折半插入是对直接插入排序的一种改进，即选择插入位置的时候利用折半法进行查找。
折半插入的时间复杂度仍为O(n^2)，因为在这里衡量时间复杂度的基本操作为元素的移动。
/**
* 折半插入排序
* zhanw15 @2018/4/9
*/
#include<stdio.h>
#define N 11
int binsearch( int *a, int num, int begin, int end)
{
int left=begin, right=end, mid;
/* 折半查找第一个比num大的元素的位置 */
while( left<=right) {
mid = (left+right)/2;
if( a[mid]<=num) left=mid+1;
else right=mid-1;
}
return left;
}
void binsort( int *a, int n)
{
int i, j, t, temp; //临时保存a[i]
for( i=0; i<n; i++) {
temp = a[i];
t = binsearch( a, a[i], 0, i-1);
for( j=i-1; j>=t; j--) {
a[j+1] = a[j];
} //向前移动大于temp的元素
a[t] = temp;
}
}
int main()
{
int i=0;
int a[N] = { 13, 24, 35, 15, 27, 39, 30, 4, 23, 21, 6};
for( i=0; i<N; i++) printf( "%d ", a[i]);
printf( "\n");
binsort( a, N);
for( i=0; i<N; i++) printf( "%d ", a[i]);
printf( "\n");
return 0;
}
//output:
// 13 24 35 15 27 39 30 4 23 21 6
// 4 6 13 15 21 23 24 27 30 35 39 插入排序----希尔排序（Shell's Sort）
希尔排序采用分组插入的方法对直接插入排序进行改进。若要排序的数组为n，首先选取d1<n作为增量，对于所有k%d （0≤k<n）相同的元素a[ k ] 划分为一组，在组内进行直接插入排序( 共d 个组)。然后选取第二个增量 d2<d1重复上述分组排序过程，直到最后取 dk = 1，排序结束。
不同的增量选取方式会影响到希尔排序的性能，下面以希尔增量的方式进行演示。希尔排序适用于中等输入规模的情况。
Ps：希尔增量是希尔给出的增量方式，第一个增量为n/2，之后的每个增量是前一个的1/2，最后一个增量为1。
/**
* 希尔排序 ( 希尔增量 )
* zhanw15 @2018/4/9
*/
#include<stdio.h>
#define N 11
void shell( int *a, int n)
{
int d, i, j, temp; // d为增量
/* 增量从 n/2 开始, 到 1 结束 */
for ( d=n/2; d>0; d/=2) {
/* d组同时进行直接插入排序 */
for ( i=0; i<n; i++) {
temp = a[i];
for ( j=i-d; j>=0 && a[j]>temp; j-=d) {
a[j+d]=a[j];
} // 大于要插入值的元素依次向后移
a[j+d]=temp; // 插入元素
}
}
}
int main()
{
int i=0;
int a[N] = { 13, 24, 35, 15, 27, 39, 30, 4, 23, 21, 6};
for( i=0; i<N; i++) printf( "%d ", a[i]);
printf( "\n");
shell( a, N);
for( i=0; i<N; i++) printf( "%d ", a[i]);
printf( "\n");
return 0;
}
//output:
// 13 24 35 15 27 39 30 4 23 21 6
// 4 6 13 15 21 23 24 27 30 35 39 选择排序----简单选择排序 （Straight Select Sort）
对于数组a[1...n]，对于k（k从1开始，到n结束），找出a[k...n]中最小元素min，与 a[ k ] 交换位置；
当k = n-1时，则完成排序，a[1...n] 成为有序数组。
与时间复杂度相同的冒泡和直接插入比较，移动元素数量较少，而且是已知的（n-1次交换）；但需要较多次的元素比较。
/**
* 简单选择排序
* zhanw15 @2018/4/9
*/
#include<stdio.h>
#define N 11
void swap( int* a, int i, int j)
{
int temp=a[j];
a[j]=a[i];
a[i]=temp;
}
void selsort( int *a, int n)
{
for( int i=0; i<n-1; i++) {
int min = i; // a[j...n]最小元素位置
for( int j=i; j<n; j++) {
min = a[min]<a[j]?min:j;
}
swap( a, i, min);
}
}
int main()
{
int i=0;
int a[N] = { 13, 24, 35, 15, 27, 39, 30, 4, 23, 21, 6};
for( i=0; i<N; i++) printf( "%d ", a[i]);
printf( "\n");
selsort( a, N);
for( i=0; i<N; i++) printf( "%d ", a[i]);
printf( "\n");
return 0;
}
//output:
// 13 24 35 15 27 39 30 4 23 21 6
// 4 6 13 15 21 23 24 27 30 35 39
选择排序----堆排序 （Heap Sort）
堆（heap）的定义：
对于由n个元素的序列{k1, k2, ki, …, kn}当且仅当满足下关系时，称之为堆：
( ki <= k2i, ki <= k2i+1)或者( ki >= k2i, ki >= k2i+1), i = 1,2,3,4...n/2
通过定义可以看出堆就是一个队列，但是它的元素有相互之间的约束。我们可以把这个队列“装进”一颗完全二叉树中，并从根节点依次编号来理解堆。
堆的几个重要性质：
2) 堆的左右子树也都是堆。
对于堆中某节点的值总是不小于其子节点的值的堆我们称为大根堆；反之则称为小根堆。
当把堆放在数组中，我们将将堆从0开始编号，则有：
1) 对于编号为k的节点，有2*k+1和2*k+2为其子节点（2*k+2<=n）
2) 对于编号为k的节点，有k/2-1为其父节点（k/2-1>=0）
怎么进行堆排序？
1) 将输入进来的元素构建成一个堆；
2) 取出堆顶（即最大值或最小值），并将堆最末尾元素放到堆顶位置；
3) 将剩余节点重新调整为一个堆；
4) 重复2、3两个步骤到堆空为止。
怎么进行建堆？
首先将数据存入到一个数组中，将其看作一个完全二叉树，则其所有的叶子节点肯定是一个堆。然后在调整叶子节点的父节点使其成为一个堆，依次向上，直到堆构建完成（从下到上的一个过程）。
怎么去除堆顶并将剩余结点调整为一个堆？
通过将堆的根节点和末尾结点交换，然后将堆的长度减一，将剩下的节点作为一个堆进行调整。从堆顶开始，比较其和左右子节点的大小，将更小（或更大）的节点调整到父节点的位置，然后继续调整根节点改变的左子树（或右子树），只到形成一个堆（从上到下的一个过程）。
优点：对数据有序性不敏感，最差时间复杂度仍为O(n*logn)，建堆过程比较费时间，因此适用于数据量比较大的排序。
缺点：相对于快排速度较慢。
/**
* 堆排序（大根堆）
* zhanw15 @2018/4/7
*/
#include<stdio.h>
#define N 11
void swap( int* a, int i, int j)
{
int temp=a[j];
a[j]=a[i];
a[i]=temp;
}
/* 调整begin元素位置，使其重新成为一个堆 */
void adjust( int* a, int begin, int end)
{
int son = begin*2+1;
/* 将根节点向下沉，直至完全构成一个堆 */
while( son<=end) {
if( son!=end && a[son+1]>a[son]) ++son;
if( a[son]<=a[begin]) break;
else swap( a, son ,begin);
begin = son;
son = begin*2+1;
}
}
void heapsort( int* a, int n)
{
int last=n-1, i;
/* 建堆(大根堆）*/
for( i=last/2-1; i>=0; i--) {
adjust( a, i, last);
}
/* 取堆顶元素，调整堆 */
while( last!=0) {
swap( a, last, 0);
adjust( a, 0, --last);
}
}
int main()
{
int i=0;
int a[N] = { 13, 24, 35, 15, 27, 39, 30, 4, 23, 21, 6};
for( i=0; i<N; i++) printf( "%d ", a[i]);
printf( "\n");
heapsort( a, N);
for( i=0; i<N; i++) printf( "%d ", a[i]);
printf( "\n");
return 0;
}
//output:
// 13 24 35 15 27 39 30 4 23 21 6
// 4 6 13 15 21 23 24 27 30 35 39交换排序----冒泡排序 （Bubble Sort）
对于数组a[1...n]，对于k（k从1开始，到n结束），从n开始、到k结束，依次交换两相邻元素的位置，使较小的元素在前，较大的元素在后。每趟交换后，a[ k ] 总是 a[k...n]中最小的元素；
当k = n时，则完成排序，a[1...n] 成为有序数组。
冒泡排序是一种稳定排序算法，且当数组有序时，冒泡排序不需要交换任何元素就能完成排序。
缺点：当数组无需或逆序时，需要较多的元素移动才能完成排序。
/**
* 冒泡排序
* zhanw15 @2018/4/9
*/
#include<stdio.h>
#define N 11
void swap( int* a, int i, int j)
{
int temp=a[j];
a[j]=a[i];
a[i]=temp;
}
void busort( int *a, int n)
{
for( int i=0; i<n-1; i++) {
for( int j=n-1; j>i; j--) {
if( a[j]<a[j-1]) swap( a, j, j-1);
}
}
}
int main()
{
int i=0;
int a[N] = { 13, 24, 35, 15, 27, 39, 30, 4, 23, 21, 6};
for( i=0; i<N; i++) printf( "%d ", a[i]);
printf( "\n");
busort( a, N);
for( i=0; i<N; i++) printf( "%d ", a[i]);
printf( "\n");
return 0;
}
//output:
// 13 24 35 15 27 39 30 4 23 21 6
// 4 6 13 15 21 23 24 27 30 35 39
交换排序----快速排序 （Quick Sort）
快排的平均时间复杂度约为O(1.39nlogn)，相比于堆排序和合并排序效率要高很多。但是最差情况下可能会出现 O(n^2)；
快速排序中一趟排序的几种常用方法（皆以最后一个元素为基准）：
1） 选定最后一个元素s为基准，两个指针i、j分别指向第一个和最后一个元素；
1、向前移动 i 直到出现 a[ i ]≤s，然后交换 a[ i ] 和 s的位置；
2、向后移动 j 直到出现 a[ j ]>s，然后交换 a[ j ] 和 s的位置；
重复上述两个步骤直到直到 i > j 为止，此时一趟排序完成。
2）选定最后一个元素s为基准，两个指针i、j分别指向第一个和最后一个元素；
向后移动 j 直到出现 a[ j ]>s，向前移动 i 直到出现 a[ i ]≤s，然后交换a[ i ] 和 a[ j ] 的位置；
重复上步骤直到 i > j 为止，取消最后一次交换，并交换 a[ i ] 和 s 的位置，一趟排序完成。
3）选定最后一个元素s为基准，两个指针 i、j同时指向第一个元素；
向前移动 j 直到出现 a[ j ]≤s，交换 a[ j ] 和 a[ i ] 的位置，并使 i++；
重复上步骤直到 j = n为止，一趟排序完成。
2 、3 两种方法都是先将数组分为 小于基准元素 和 大于基准元素 的两部分后，再将 基准元素 移动到中间位置的，避免了频繁的移动基准元素，因此相对 1 来说更省时。
下面的代码采用第三种方式进行快速排序。
/**
* 快速排序
* zhanw15 @2018/4/9
*/
#include<stdio.h>
#define N 11
void swap( int* a, int i, int j)
{
int temp=a[j];
a[j]=a[i];
a[i]=temp;
}
int partition( int* a, int p, int r)
{
int i=p-1, j; // i指向比基准小的元素末尾
for( j=p; j<r; j++) { // 以a[r-1]为基准
if( a[j]<=a[r-1]) swap( a, ++i, j);
}
return i; // 返回中间值
}
/* 快排 注明: 不存在a[r]元素, 此写法仅为使用方便 */
void qsort( int* a, int p, int r)
{
if( p>=r-1) return;
int q = partition( a, p, r);
qsort( a, p, q);
qsort( a, q+1, r);
}
int main()
{
int i=0;
int a[N] = { 13, 24, 35, 15, 27, 39, 30, 4, 23, 21, 6};
for( i=0; i<N; i++) printf( "%d ", a[i]);
printf( "\n");
qsort( a, 0, N);
for( i=0; i<N; i++) printf( "%d ", a[i]);
printf( "\n");
return 0;
}
//output:
// 13 24 35 15 27 39 30 4 23 21 6
// 4 6 13 15 21 23 24 27 30 35 39
归并排序 （Merge Sort）
归并排序是分治策略的一种应用，归并排序分为两个过程：分解（利用递归将数组分解成不想交的两部分，直到分解到不能分解为止）、合并。
合并的过程：
1）申请数组空间用于存放合并后的数组元素；
2）两个指针i、j分别指向要合并的两个数组a、b头；
3）比较a[ i ] 和 b[ j ] 的大小，将较大的元素放入合并空间并使其指针+1.
重复3）操作直至数组合并完成，并重复1）、2）、3）操作直到归并完成，则排序完成。
归并排序具有稳定性，但需要消耗较大的辅助空间；适用于对稳定性有要求的排序。
/**
* 归并排序
* zhanw15 @2018/4/9
*/
#include<stdio.h>
#define N 11
/* 对数组进行合并 */
void merge( int* a, int p, int q, int r)
{
int temp[r-p]; //开辟存储合并后元素空间
int i=p, j=q, k=0; //三个指针分别指向三个数组
while(i<q && j<r) { //将较小的元素放入合并空间
if( a[i]<=a[j]) temp[k++]=a[i++];
else temp[k++]=a[j++];
}
/* 将剩余元素放入合并空间 */
while( i<q) temp[k++]=a[i++];
while( j<r) temp[k++]=a[j++];
for( i=0; i<r-p; i++) { //将合并后的元素放入数组a
a[p+i] = temp[i];
}
}
void mersort( int* a, int p, int r)
{
if( p>=r-1) return;
/* 先排左半部分，再排右半部分，再合并 */
int q = ( p+r)/2;
mersort( a, p, q); // 分解
mersort( a, q, r); // 分解
merge( a, p, q, r); // 合并
}
int main()
{
int i=0;
int a[N] = { 13, 24, 35, 15, 27, 39, 30, 4, 23, 21, 6};
for( i=0; i<N; i++) printf( "%d ", a[i]);
printf( "\n");
mersort( a, 0, N);
for( i=0; i<N; i++) printf( "%d ", a[i]);
printf( "\n");
return 0;
}
//output:
// 13 24 35 15 27 39 30 4 23 21 6
// 4 6 13 15 21 23 24 27 30 35 39 计数排序 （Counting sort）
计数排序的基本思想：
对于输入中的一个元素x，确定比其小的元素个数c，那么将x放在第c+1个位置，排序完成。注意有可能多个元素有相同的值，我们记录所有值出现的次数，然后确定元素的位置。
排序的基本过程：
1）对于一个输入为a[ 1...n ] 的数组，首先寻找其最大值max和最小值min，建立一个数组c[ 0...(max-min) ] 大小临时存储空间，来记录每个值出现的次数。
2）遍历数组a中的所有元素，将他们值出现的次数记录到c数组中。方法：使用c[a[k]-min]++，将值为x的元素投影到c数组的x-min位置。
3）确定值为k元素所在的位置。值为 k 元素的个数记录在了c[k-min]中，因此使用{ for i=1 to max-min, c[i] += c[i-1] } 后，c[i] 的值为 小于等于 i+min 的元素的个数。
4） 使用数组b[ 1...n ]记录排序后的数组a 。使用{ for i=n to 0, b[--c[a[i]-min]] = a[i] }来将元素a[i]调整到特定的位置（每次c[]--，表示a[i]元素已调整好位置，剩下相同值的元素-1）。若有必要，将b数组重新赋值给a数组。
注意：由于是从a数组最后一个元素开始调整的，若还有相同值的元素则会被放在c[]--的位置，因此计数排序是稳定的。
/**
* 计数排序
* zhanw15 @2018/4/9
*/
#include<stdio.h>
#define N 11
void countsort( int *a, int n)
{
int min, max=min=a[0];
for( int i=1; i<n; i++) {
min = min<a[i]?min:a[i];
max = max>a[i]?max:a[i];
}
int b[n], c[max-min+1]; // c数组记录元素出现次数
for( int i=0; i<=max-min; c[i]=0,i++); //清零
for( int i=0; i<n; i++) c[a[i]-min]++; //计数
for( int i=1; i<=max-min; i++) {
c[i] +=c[i-1]; //确定值为i元素所在位置
}
for( int i=n-1; i>=0; i--) {
b[--c[a[i]-min]] = a[i]; // 将a[i]调整到相应位置
}
for( int i=0; i<n; a[i]=b[i],i++); // 回调给a
}
int main()
{
int i=0;
int a[N] = { 13, 24, 35, 15, 27, 39, 30, 4, 23, 21, 6};
for( i=0; i<N; i++) printf( "%d ", a[i]);
printf( "\n");
countsort( a, N);
for( i=0; i<N; i++) printf( "%d ", a[i]);
printf( "\n");
return 0;
}
//output:
// 13 24 35 15 27 39 30 4 23 21 6
// 4 6 13 15 21 23 24 27 30 35 39基数排序（Radix Sort）
给定一系列d位10进制数进行排序，当然我们可以使用计数排序对其进行排序，但是当数列中的max和min相差很大时，时间复杂度O( k+n ) 中的 k = max-min+1 将变的很大，将带来很大的时空开销。我们可以采用另一种策略，将数列中的数 x 看作： x = x0*10^0 + x1*10 + x2*10^2 + . . . + xd*10^d，那么先对所有数字的最低位x0进行排序，然后对x1进行排序，因此类推，直到d位全部排序完成，那么这系列数也排序完成。我们对每位上的数字使用计数排序，因为是十进制，那么计数排序的时间复杂度为O( 10+n )，共进行d轮排序，则整体时间复杂度为O( d( 10+n) )。
上述方法被称为基数排序，10就是上述排序中的基数。基数排序可以用作以任何数为基数的排序上，例如对字符串进行排序，可选用基数为26，先排序最后一位的字母，再向前依次排序。
引理（算法导论引理8.4）：给定一个b位数和任何正整数r≤b，如果RADIX-SORT使用的稳定排序算法对数据取值区间是0到k的输入进行排序耗时Θ( n+k ) (这里即使用计数排序)，那么它就可以在Θ( (b/r)(n+2^r) ) 时间内完成排序（即化为r为基数的基数排序）。
通过上述引理，可以通过选取不同的基数将Θ( (b/r)(n+2^r) )达到时间复杂度最小化。
- 对于d<logn时，对任意r≤d结果都为Θ( (b/r) n )，那么选择r=d使时间复杂度最低，为Θ( n )；
- 对于d≥logn时，选择r=logn时会获得最低的时间复杂度，Θ( bn/logn )；----自行证明
/**
* 基数排序
* zhanw15 @2018/4/9
*/
#include<stdio.h>
#include<math.h>
#define N 11
/* 获取数组中最大元素位数 radix为基数 */
int getDigit( int radix, int *a, int n)
{
int d = 0;
for( int i=0; i<n; i++) {
while( a[i]>=pow(radix,d)) d++;
}
return d;
}
/* 获取数字以radix为基数的第k位的值 */
int getNum( int num, int radix, int k) {
return num%(int)pow(radix,k)/(int)pow(radix,k-1);
}
void radixsort( int *a, int n)
{
int radix=10, d=getDigit( radix, a, n);
int b[n], c[radix]; // b数组暂存排序结果，c记录元素出现次数
for( int i=0; i<d; i++) { // 进行 d 轮计数排序
for( int j=0; j<radix; j++) c[j]=0; // 清零
for( int j=0; j<n; j++) c[getNum(a[j],radix,i+1)]++; // 计数
for( int j=1; j<radix; j++) c[j] += c[j-1]; // 确定位置
for( int j=n-1; j>=0; j--) b[--c[getNum(a[j],radix,i+1)]]=a[j]; // 移动位置
for( int j=0; j<n; j++) a[j] = b[j]; // 回调
}
}
int main()
{
int i=0; // 相比于其它排序改动了一下数据大小
int a[N] = { 133, 224, 35, 175, 27, 39, 30, 114, 293, 21, 1256};
for( i=0; i<N; i++) printf( "%d ", a[i]);
printf( "\n");
radixsort( a, N);
for( i=0; i<N; i++) printf( "%d ", a[i]);
printf( "\n");
return 0;
}
// output:
// 133 224 35 175 27 39 30 114 293 21 1256
// 21 27 30 35 39 114 133 175 224 293 1256桶排序（Bucket Sort）
假设输入数据服从均匀分布，那么我们可以将数据投影到 [ 0, 1) 区间上，并将 [ 0, 1) 这段区间划分为n个大小相同的子区间（这些子区间被称为桶）。我们将落入相同桶的元素进行排序，然后依次收集每个桶中的数据，最终得到排序好的结果。
假设每个桶的大小为di，每个桶内执行插入排序，那么桶排序时间复杂度为：O(n) + nO(E(d^2))
其中O(n) 为将数据放入桶的时间复杂度，插入排序时间复杂度为O(d^2)，n个桶的插入排序为nO(E(d^2))，其中E()表示期望。当输入数据均匀分布时，E(d^2) = 2-1/n，那么桶排序的时间复杂度为：O(n)
PS：看网上很多人把桶排序和基数排序混为一谈，基数排序是从最小基数项开始，到最大基数项结束，对数组整体进行排序，然后得到有序序列。而桶排序是先通过投影将n个数分组，然后再组内对数据进行排序，最后进行合并。基数排序的思想是对整体的部分（基数项）进行排序，而桶排序的思想是将整体分割，分别进行排序。