很少有只描述算法的书籍，一般都是数据结构和算法结合起来进行描述。但是数据结构和算法不是同一个概念，在这里我们要做一下区分，以便进入误区，“数据结构=算法”。
根据维基百科对数据结构的释义
在计算机科学中，数据结构（英语：data structure）是计算机中存储、组织数据的方式。
根据维基百科对算法的释义
算法（algorithm），在数学（算学）和计算机科学之中，为任何良定义的具体计算步骤的一个序列，常用于计算、数据处理和自动推理。精确而言，算法是一个表示为有限长列表的有效方法。算法应包含清晰定义的指令用于计算函数。
让我们来回顾一下，在计算机领域解决一个问题的步骤。
- 分析问题，从问题中提取出有价值的数据，将其存储
- 对存储的数据进行处理，最终得出问题的答案
数据结构在这个过程中，承担的任务就是解决数据存储，也就是步骤1。针对数据的不同逻辑结构和物理结构，可以选出最优的数据存储结构来存储数据。
当然，步骤2就是算法应该承担的责任。从表面的意思来看，算法就是用来解决问题的方法。我们知道，评价要给算法的好坏，取决在解决相同问题的前提下，哪种算法的效率高，而这里的效率指的就是处理数据、分析数据的能力。
补充，其实在解决问题的过程中不能只考虑算法的高效，还要考虑算法过程中，数据存储空间是否合理。
因此，我们得出来结论，数据结构用于存储数据，而算法用于处理和分析数据，他们是完全不同的学科，但是他们是相辅相成的。
总结一下，在解决问题的过程中，数据结构要配合算法选择最优的存储结构来存储数据，而算法也要结合数据存储的特点，用最优的策略来分析并处理数据，由此可以最高效地解决问题。
这里对应的是两个概念，时间复杂度和空间复杂度，后面会展开论述。
我们先从客观方面来描述一下，很多大公司，比如BAT，Google，Facebook面试的时候都喜欢考算法，让人现场写代码。很多人技术不错，但是基本上每次面试都“跪“在算法上面。因此为了找一份好工作，学好算法是很重要的。
接下来我们从主观方面来描述一下，掌握数据结构和算法，不管对应阅读框架源码，还是理解其背后的设计思想，或者说在实际应用中解决问题，都是至关重要的。能给你工作的场景带来快速高效的解决问题。因此，学习好算法和数据结构也是势在必行的事情。
想要学习数据结构和算法，首页要掌握一个数据结构与算法中最重要的概念——复杂度分析。
这个概念很重要。可以这么说，它几乎占了数据结构和算法这门课的半壁江山，是数据结构和算法的精髓。
数据结构和算法解决的是如何更省，更快的存储和处理数据问题。因此，我们就需要一个考量效率和资源消耗的方法，这就是复杂度分析。只有学会了复杂度分析，你才能了然于胸。
我们都知道，数据结构和算法本身解决的是”快“和”省“的问题，即如何让代码运行得更快，同时如何让代码消耗的空间更少。因此，执行效率是算法一个非常重要的考量指标。那如何来衡量你编写的算法代码的执行效率呢？两方面，时间复杂度和空间复杂度。
对于算法不是很了解的同学，可能会认为我把代码执行一遍，通过统计、监控，就能获得算法执行的时间和内存占用的大小。为什么还要做时间和空间的复杂度分析呢？
首先，上述描述的估算算法执行效率的方法是正确的。这个方法有个名词，事后评估法。但是这种统计方法具有很大的局限性。
测试环境中硬件的不同会对测试结果造成很大的影响。比如，我们同样的一段代码，分别用Intel Core i9和Intel Core i3处理器来执行，不用说，i9比i3执行的要快。
拿排序来举个例子，如果给予的数据是已经排好序的，那么执行的时间和没有排序的数据差别会很明显。 因此，我们需要一个不用具体的测试数据来测试，就可以粗略的估计算法的执行效率的方法。
算法的执行效率，也就是算法的执行时间。但是如何在不运行代码的情况下，直接分析出代码的执行时间呢？
这里我们通过一段代码来进行算法时间分析：
1 int cal(int n) {
2 int sum = 0;
3 int i = 1;
4 for (; i <= n; i++) {
5 sum = sum + i;
6 }
7 return sum;
}
这段代码，基本描述的就是类似操作，读数据-运算-写数据。尽管不同的机器执行的时间不同，但是我们可以通过粗略估计，来给每段代码执行的时间定义一个常量，unit_time。基于这个常量，我们来给上述代码进行执行时间预估。
第2行和第3行代码需要一个unit_time执行时间，第4行和第5行执行了n遍，因此2*n*unit_time，因此可以得出代码的总执行市场是(2n+2)*unit_time。在这里可以看出，代码的执行时间T(n)与每行代码的执行次数成正比。
按照这个思路，我们再来分析一段代码
1 int cal(int n) {
2 int sum = 0;
3 int i = 1;
4 int j = 1;
5 for (; i <= n; i++) {
6 j = 1;
7 for (; j <= n; j++) {
8 sum = sum + i * j;
9 }
10 }
11 }
第2，3，4行代码执行了一次，因此执行时间是3*unit_time, 第5，6行代码执行了n次，需要2n*unit_time的执行时间，第7，8行代码执行了n²遍，需要2n²*unit_time的执行时间。因此，整段代码的执行时间是(2n²+2n+3)*unit_time。
尽管我们不清楚unit_time的具体值，但是我们通过这两段代码，可以推导出一个重要的规律，所有代码的执行时间T(n)与每行代码的执行次数n成正比。
所以我们可以总结如下公式，大O表示法：T(n) = O(f(n))
具体解释下公式。其中T(n)是表示代码的执行的时间，n表示数据的规模，f(n)表示每行代码执行的次数总和。因为这是一个公式，所以用f(n)来表示。公式中的O,表示代码的执行时间T(n)和f(n)表达式成正比。
所以，第一个例子中，T(n) = O(2n+2)，第二个例子中,T(n) = O(2n²+2n+3)。这就是大O时间复杂度表示法。大O时间复杂度实际上并不具体表示代码的真正执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫做渐进时间复杂度（asymptotic time complexity），简称时间复杂度。
以上例子，当n变得很大的时候，比如100000，10000000。而公式中的低阶、常量、系数三部分不左右增长趋势，所以都可以忽略。我们只要记住最大数量级的就可以了。因此以上两个例子大O表示法，可以简化如下，T(n) = O(n)，T(n) = O(n²)。
以下开始算法正片内容
我们先来介绍下快速排序的思想：如果要排序数组中下标从p到r之间的一组数据，我们选择p到r之间的任意一个数据作为pivot（分区点）。
我们遍历p到r之间的数据，将小于pivot的数据放到左边，将大于pivot的数据放到右边，将pivot放到中间。经过这一个步骤，数据p到r之间的数据就被分割成了三部分，前面p到q-1之间都是小于pivot的，中间是pivot，后面的q+1到r之间的数据都是大于pivot的。
在这里需要解释两个名次，分治，递归。 根据维基百科对分治的释义：
在计算机科学中，分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
根据维基百科对递归的释义：
在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。
这里快速的排序用到了分治和递归的思想，因此我们可以用递归排序下标从p到q-1之间的数据和下标q+1到r之间的数据，直到区间缩小为1，就说明所有的数据都有序了。
如果我们用递推公式来描述上面的公式，就是这样：
递推公式：
quick_sort(p...r) = quick_sort(p...q-1) + quick_sort(q+1...r)
终止条件
p >= r
我们将递推公式转化为递归代码，我们用伪代码来实现：
// 快速排序，A是数组， n表示数组的大小
quick_sort(A, n) {
quick_sort_c(A, 0, n-1);
}
// 快速排序递归函数，p, r 为下标
quick_sort_c(A, p, r) {
if (p >= r) {
return;
}
q = partition(A, p, r); // 获取分区点(pivot)
quick_sort_c(A, p, q-1);
quick_sort_c(A, q+1, r);
}
这里partition()分区函数，就是随机选择一个元素作为pivot（一般情况下，可以选择p到r区间最后一个元素），然后对A[p...r]进行分区，函数返回pivot下标。
partition(A, p, r) {
pivot := A[r];
i := p;
for (j := p; j <= r-1; j++) {
if (A[j] < pivot) {
swap A[i] with A[j];
i := i + 1
}
}
swap A[i] with A[r]
return i
}
在这里，我们通过游标i把A[p...r-1]分成两部分，A[p...i-1]的元素都是小于pivot的，我们暂且叫它“已处理区间“，A[i...r-1]是”未处理区间“。我们每次都从未处理的区间A[i...r-1]中取第一个元素A[j],与pivot相比，如果小于pivot，则将其加入到已处理区间的尾部，也就是A[i]的位置。
数组的插入操作，比较耗时，因此我们可以采取交换操作的思想。
以下，通过图来解释会更清楚一些：
因为分区的过程设计交换操作，如果数组中有两个相同元素，比如序列6，8，7，6，3，5，9，4，在经过第一次分区操作之后，两个6的相对先后顺序就会改变。所以，快排是一个不稳定的排序算法。
以下是一张快速排序的图：
快速排序，是自上而下的处理过程，先分区，然后再处理子问题。
现在，我们来分析下快速排序的性能。
快排是用递归来实现的。如果每次分区操作，都能正好把数组分成大小接近相等的两个小区间，那快排的时间复杂度递推公式跟归并是相同的。所以，快排的时间复杂度也是O(nlogn)。
T(1) = C； n=1时，只需要常量级的执行时间，所以表示为C。
T(n) = 2*T(n/2) + n; n > 1。d
选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。 重复第二步，直到所有元素均排序完毕。
def selection_sort():
# 选择排序
arr = [86, 12, 211, 114, 45, 15, 3, 21312, 212]
for i in range(len(arr)-1):
# 记录最小数的索引
min_index = i
print ('i=%d' % i)
for j in range(i + 1, len(arr)):
print ('j=%d' % j)
if arr[j] < arr[min_index]:
min_index = j
# i 不是最小数时，将 i 和最小数进行交换
if i != min_index:
arr[i], arr[min_index] = arr[min_index], arr[i]
print (arr)
return arr
if __name__ == "__main__":
selection_sort()
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法： 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列； 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列； 堆排序的平均时间复杂度为 Ο(nlogn)。
创建一个堆 H[0……n-1]； 把堆首（最大值）和堆尾互换； 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置； 重复步骤 2，直到堆的尺寸为 1。
#-*- encoding=utf8 -*-
import math
def build_max_heap(arr):
# 创建堆
for i in range(int(math.floor(len(arr)/2)), -1, -1):
heapify(arr, i)
def heapify(arr, i):
# 取最大值的位置
left = 2 * i + 1
right = 2 * i + 2
largest = i
if left < arr_len and arr[left] > arr[largest]:
largest = left
if right < arr_len and arr[right] > arr[largest]:
largest = right
if largest != i:
# print (i)
swap(arr, i, largest)
# print (arr)
heapify(arr, largest)
def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]
def heap_sort():
arr = [31, 33, 19, 82, 13, 11, 19]
global arr_len
arr_len = len(arr)
build_max_heap(arr)
print (arr)
for i in range(len(arr)-1, 0, -1):
swap(arr, 0, i)
arr_len -= 1
heapify(arr, 0)
return arr
if __name__ == "__main__":
print(heap_sort())
插入排序（Insertion sort）是一种简单直观且稳定的排序算法。适用于少量数据的排序，时间复杂度为O(n^2)。基于以上特点，插入排序适用于较少的数据量排序
每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止
插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
就像许多人排序一手扑克牌。
开始时，我们左手为空，并且桌子上的牌面朝下。
然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。（为了找到一张牌的正确位置，我们从右到左将他与在手中的每张牌进行比较）
拿在手中的牌总是排序好的，原来这些牌是桌子上牌堆中顶部的牌
INSERTION_SORT(A)
1 for j ← 2 to Length(A)
2 key = A[i]
3 // Insert A[j] into the sorted sequence A[1, j - 1]
4 i = j - 1
5 while i > 0 and A[i] > key
6 A[i+1] = A[i]
7 i -= 1
8 A[i+1] = key
折半插入排序（binary insertion sort）是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。
在将一个新元素插入已排好序的数组的过程中，寻找插入点时，将待插入区域的首元素设置为a[low]，末元素设置为a[high]，则轮比较时将待插入元素与a[m]，其中m=(low+high)/2相比较,如果比参考元素小，则选择a[low]到a[m-1]为新的插入区域(即high=m-1)，否则选择a[m+1]到a[high]为新的插入区域（即low=m+1），如此直至low<=high不成立，即将此位置之后所有元素后移一位，并将新元素插入a[high+1]
func binInsertionSort(_ array: inout Array<Int>){
for i in 1..<array.count {
var low = 0;
var high = i - 1
var mid = 0
while high >= low {
mid = (high + low) / 2
if array[i] < array[mid]{
high = mid - 1
}else{
low = mid + 1
}
}
let key = array[i]
for j in stride(from: i, to: low, by: -1){
array[j] = array[j - 1]
}
array[low] = key
}
}| 最坏 | 最好 | 稳定性 | 空间复杂度 |
|---|---|---|---|
| O(n^2) | O(nlog2n) | 稳定 | O(1) |
p.s.
最好情况：
每次插入的位置k都是已序数组的最后的位置，则无需再执行移位赋值操作 O(n*log2n)
最坏情况：
每次插入的位置k都是已序数组的最前的位置，则整个已序数组需要移位赋值 O(n^2) 二分查找时间复杂度 O(log2n)
希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名
希尔排序是记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止
初始时，有一个大小为 10 的无序序列。
-
在第一趟排序中，我们不妨设 gap1 = N / 2 = 5，即相隔距离为 5 的元素组成一组，可以分为 5 组。
-
接下来，按照直接插入排序的方法对每个组进行排序。
在第二趟排序中，我们把上次的 gap 缩小一半，即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组，可以分为 2 组。
-
按照直接插入排序的方法对每个组进行排序。
-
在第三趟排序中，再次把 gap 缩小一半，即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组，即只有一组。
-
按照直接插入排序的方法对每个组进行排序。此时，排序已经结束
func shellInsertionSort(_ array: inout Array<Int>){
var step = array.count / 2
while step > 0 {
for group in 0..<step {
for i in stride(from: group + step, to: array.count - 1, by: step) {
let key = array[i]
var backIndex = i - step
while backIndex >= 0 && array[backIndex] > key {
array[backIndex + step] = array[backIndex]
backIndex -= step
}
array[backIndex + step] = key
}
}
step = step / 2;
}
}时间复杂度：
最好情况：由于希尔排序的好坏和步长gap的选择有很多关系，因此，目前还没有得出最好的步长如何选择(现在有些比较好的选择了，但不确定是否是最好的)。所以，不知道最好的情况下的算法时间复杂度。
最坏情况下：O(N*logN)，最坏的情况下和平均情况下差不多。
已知的最好步长序列是由Sedgewick提出的(1, 5, 19, 41, 109,...)。
这项研究也表明“比较在希尔排序中是最主要的操作，而不是交换。”用这样步长序列的希尔排序比插入排序和堆排序都要快，甚至在小数组中比快速排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。
空间复杂度
由直接插入排序算法可知，我们在排序过程中，需要一个临时变量存储要插入的值，所以空间复杂度为1。
算法稳定性
希尔排序中相等数据可能会交换位置，所以希尔排序是不稳定的算法。
是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。冒泡排序对n个项目需要O(n^2)的比较次数，且可以原地排序。尽管这个算法是最简单了解和实现的排序算法之一，但它对于包含大量的元素的数列排序是很没有效率的 。冒泡排序是与插入排序拥有相等的运行时间，但是两种算法在需要的交换次数却很大地不同。在最坏的情况，冒泡排序需要O(n^2)次交换，而插入排序只要最多O(n)交换。冒泡排序的实现（类似下面）通常会对已经排序好的数列拙劣地运行 O(n^2)，而插入排序在这个例子只需要 {O(n)个运算.
1:比较相邻的元素, 如果第一个比第二个大，就交换他们两个。 2:对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。 3:针对所有的元素重复以上的步骤，除了最后一个。最后一个数一定是数组中最大的一个数，所以在比较第二趟的时候，最后一个数是不参加比较的。 4:在第二趟比较完成后，倒数第二个数也一定是数组中倒数第二大数，所以在第三趟的比较中，最后两个数是不参与比较的。 5:持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
函数 冒泡排序 输入 一个数组名称为array 其长度为length i 从 1 到 (length - 1) j 从 0 到 (length - 1 - i) 如果 array[j] > array[j + 1] 交换 array[j] 和 array[j + 1] 的值 j循环结束 i循环结束 函数结束
swift 代码
func bubbleSort(data:inout Array<Int>)
{
for i in 0..<data.count-1
{
for j in 0..<data.count-i-1
{
if (data[j]>data[j+1])
{
data.swapAt(j, j+1);
}
}
}
}
bubbleSort(data: &dataArr)
改进代码
func bubbleSort(data:inout Array<Int>)
{
for i in 0..<data.count-1
{
var exchange = false;
for j in 0..<data.count-i-1
{
if (data[j]>data[j+1])
{
data.swapAt(j, j+1);
exchange = true;
}
}
if !exchange {
break;
}
}
}
bubbleSort(data: &dataArr)
(1): 由此可见：N个数字要排序完成，总共进行N-1趟排序，每i趟的排序次数为(N-i)次，所以可以用双重循环语句，外层控制循环多少趟，内层控制每一趟的循环次数
(2): 冒泡排序的优点：每进行一趟排序，就会少比较一次，因为每进行一趟排序都会找出一个较大值。如上例：第一趟比较之后，排在最后的一个数一定是最大的一个数，第二趟排序的时候，只需要比较除了最后一个数以外的其他的数，同样也能找出一个最大的数排在参与第二趟比较的数后面，第三趟比较的时候，只需要比较除了最后两个数以外的其他的数，以此类推……也就是说，没进行一趟比较，每一趟少比较一次，一定程度上减少了算法的量。
(3): 时间复杂度
1: 如果我们的数据正序，只需要走一趟即可完成排序。所需的比较次数C和记录移动次数M均达到最小值，即：Cmin=n-1;Mmin=0;所以，冒泡排序最好的时间复杂度为O(n)。
2: 如果很不幸我们的数据是反序的，则需要进行n-1趟排序。每趟排序要进行n-i次比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：
(4): 综上所述：冒泡排序总的平均时间复杂度为：O(n2) ,时间复杂度和数据状况无关。
Cmax = n(n-1)/2 = O(n^2)
Mmax = 3n(n-1)/2 = 0(n^2)
### 1.4.9鸡尾酒排序算法
鸡尾酒排序，也就是定向冒泡排序，鸡尾酒搅拌排序，搅拌排序（也可以视作选择排序的一种变形），涟漪排序，来回排序或快乐小时排序，是冒泡排序的一种变形。此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。
#### 1.4.9.1算法原理
鸡尾酒排序等于是冒泡排序的轻微变形。不同的地方在于从低到高然后从高到低，而冒泡排序则仅从低到高去比较序列里的每个元素。他可以得到比冒泡排序稍微好一点的性能，此算法与冒泡排序的不同之处在于从低到高排然后从高到低，而冒泡排序则仅从低到高去比较序列中的每个元素，可以得到比冒泡排序稍微好一点的效能.
算法原理：数组中的数字本是无规律的排放，先找到最小的数字，把他放到第一位，然后找到最大的数字放到最后一位。然后再找到第二小的数字放到第二位，再找到第二大的数字放到倒数第二位。以此类推，直到完成排序。
func shakerSort(data:inout Array<Int>) { var left = 0; var right = data.count - 1 ; while(left<right){ for i in left..<right { if(data[i]>data[i+1]) { data.swapAt(i, i+1); } } right -= 1; for j in ((left+1)...right).reversed(){ if(data[j]<data[j-1]) { data.swapAt(j, j-1); } } left += 1; } } shakerSort(data: &dataArr)
#### 1.4.9.3性能分析
|平均|最坏|最好|稳定性|空间复杂度|
|:--|:--|:--|:--|:--|
|O(n^2)|O(n^2)|O(n)|稳定|O(1)|
计数排序（Counting sort）是一种稳定的线性时间排序算法。该算法于1954年由 Harold H. Seward 提出。计数排序使用一个额外的数组 C ，其中第 i 个元素是待排序数组 A 中值等于 i 的元素的个数。然后根据数组 C 来将 A 中的元素排到正确的位置。
- 根据待排序集合中最大元素和最小元素的差值范围，申请额外空间；
- 遍历待排序集合，将每一个元素出现的次数记录到元素值对应的额外空间内；
- 对额外空间内数据进行计算，得出每一个元素的正确位置；
- 将待排序集合每一个元素移动到计算得出的正确位置上。
void counting_sort(int *ini_arr, int *sorted_arr, int n) {
int min = ini_arr[0];
int max = ini_arr[0];
for(int i = 0 ; i < n ; i ++){
if (min > ini_arr[i]) {
min = ini_arr[i];
}
if (max < ini_arr[i]) {
max = ini_arr[i];
}
}
int len = max - min + 1;
int *count_arr = (int *) malloc(sizeof(int) * len);
for (int m = 0; m < len; m++){
count_arr[m] = 0;
}
for (int k = 0; k < n; k++){
count_arr[ini_arr[k]-min]++;
}
int index = 0;
for (int j = 0; j < len; j++) {
while (count_arr[j] > 0) {
sorted_arr[index] = j + min;
index++;
count_arr[j]--;
}
}
}
o(n+k)
桶排序(Bucket sort)是一种基于计数的排序算法，工作的原理是将数据分到有限数量的桶子里，然后每个桶再分别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）。
- 设置固定数量的空桶。
- 把数据放到对应的桶中。
- 对每个不为空的桶中数据进行排序。
- 拼接从不为空的桶中数据，得到结果。
伪代码如下：
- 设置桶的数量为5个空桶，找到最大值110，最小值7，每个桶的范围20.8=(110-7+1)/5 。
- 遍历原始数据，以链表结构，放到对应的桶中。数字7，桶索引值为0，计算公式为floor((7 – 7) / 20.8)， 数字36，桶索引值为1，计算公式floor((36 – 7) / 20.8)。
- 当向同一个索引的桶，第二次插入数据时，判断桶中已存在的数字与新插入数字的大小，按照左到右，从小到大的顺序插入。如：索引为2的桶，在插入63时，桶中已存在4个数字56，59，60，65，则数字63，插入到65的左边。
- 合并非空的桶，按从左到右的顺序合并0，1，2，3，4桶。
- 得到桶排序的结构