- 1 . 冒泡排序
- 2. 选择排序
- 3. 插入排序
- 4. 希尔排序
- 5. 归并排序
- 6. 快速排序
- 7. 堆排序
- 8. 计数排序
- 9. 桶排序
- 10. 基数排序
- 基数排序 vs 计数排序 vs 桶排序
- 参考
排序算法是《数据结构与算法》中最基本的算法之一。
排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等
1 . 冒泡排序
算法思想：
冒泡排序（英语：Bubble Sort）是一种简单的排序算法。
它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
算法步骤
1、比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。
2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3、针对所有的元素重复以上的步骤，除了最后一个。
4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
Python 代码
def bubbbleSort(alist):
for passnum in range(len(alist) - 1, 0, -1):
for i in range(passnum):
if alist[i] > alist[i + 1]:
alist[i], alist[i + 1] = alist[i + 1], alist[i]
return alist
alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(bubbbleSort(alist))
# 改进的冒泡排序, 加入一个校验, 如果某次循环发现没有发生数值交换, 直接跳出循环
def modiBubbleSort(alist):
exchange = True
passnum = len(alist) - 1
while passnum >= 1 and exchange:
exchange = False
for i in range(passnum):
if alist[i] > alist[i + 1]:
alist[i], alist[i + 1] = alist[i + 1], alist[i]
exchange = True
passnum -= 1
return alist
print(modiBubbleSort(alist))
2. 选择排序
算法思想
选择排序（Selection sort）是一种简单直观的排序算法。
它的工作原理如下：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。
算法步骤
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
- 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
- 重复第二步，直到所有元素均排序完毕。
动图演示
Python 代码
def selection_sort(alist):
for i in range(len(alist) - 1):
min = i
for j in range(i + 1, len(alist)):
if alist[j] < alist[min]:
min = j
alist[i], alist[min] = alist[min], alist[i]
return alist
alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(selection_sort(alist))
3. 插入排序
算法思想
插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
算法步骤
- 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
- 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
动图演示
Python 代码
def insertionSort(alist):
for key, item in enumerate(alist):
index = key
while index > 0 and alist[index - 1] > item:
alist[index] = alist[index - 1]
index -= 1
alist[index] = item
return alist
alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(insertionSort(alist))
4. 希尔排序
希尔排序(Shell Sort)是插入排序的一种, 也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样(竖着的元素是步长组成)：
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
然后我们对每列进行排序：
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]。这时10已经移至正确位置了，然后再以3为步长进行排序：
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
排序之后变为：
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
最后以1步长进行排序（此时就是简单的插入排序了）
算法步骤
- 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
- 按增量序列个数 k，对序列进行 k 趟排序；
- 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
Python 代码
def shell_sort(alist):
sublist_count = len(alist) // 2
while sublist_count > 0:
for start_position in range(sublist_count):
gap_insertion_sort(alist, start_position, sublist_count)
sublist_count = sublist_count // 2
return alist
def gap_insertion_sort(alist, start, gap):
for i in range(start + gap, len(alist), gap):
current_value = alist[i]
position = i
while position >= gap and alist[position - gap] > current_value:
alist[position] = alist[position - gap]
position = position - gap
alist[position] = current_value
alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(shell_sort(alist))
5. 归并排序
算法思想
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
归并排序的思想就是先递归分解数组，再合并数组。将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。
算法步骤
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
- 重复步骤 3 直到某一指针达到序列尾；
- 将另一序列剩下的所有元素直接复制到合并序列尾。
动图演示
Python 代码
def merge_sort(alist):
if len(alist) > 1:
mid = len(alist) // 2
left_half = alist[:mid]
righ_thalf = alist[mid:]
merge_sort(left_half)
merge_sort(righ_thalf)
i = 0
j = 0
k = 0
while i < len(left_half) and j < len(righ_thalf):
if left_half[i] < righ_thalf[j]:
alist[k] = left_half[i]
i += 1
else:
alist[k] = righ_thalf[j]
j += 1
k += 1
# 如果左半边或者右半边有一个先到末尾，上面的循环就退出了
# 那么就把没有到末尾那半边的最后的元素添加到新的序列中，以免数值少算
while i < len(left_half):
alist[k] = righ_thalf[i]
i += 1
k += 1
while j < len(left_half):
alist[k] = righ_thalf[j]
j += 1
k += 1
a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
merge_sort(a_list)
print(a_list)
6. 快速排序
算法思想
快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
算法步骤
- 从数列中挑出一个元素，称为 “基准”（pivot）;
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
动图演示
Python 代码
def quick_sort(alist, start, end):
"""快速排序"""
if start >= end:
return
# 基准
mid = alist[start]
# 左边的游标
left = start
# 右边游标
right = end
while left < right:
while left < right and alist[right] >= mid:
# 右边的游标移动，左边的游标不动
right -= 1
alist[left] = alist[right]
while left < right and alist[left] < mid:
# 左边的游标移动，右边的游标不动
left += 1
alist[right] = alist[left]
# 退出循环后，left 与 right 重合，即相等
alist[left] = mid
# 递归的方式，排左边的序列
quick_sort(alist, start, left - 1)
# 递归方式排右边的序列
quick_sort(alist, left + 1, end)
if __name__ == "__main__":
alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(f"原列表为：{alist}")
quick_sort(alist, 0, len(alist) - 1)
print(f"新列表为：{alist}")
7. 堆排序
算法思想
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
- 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
- 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
算法步骤
- 创建一个堆 H[0……n-1]；
- 把堆首（最大值）和堆尾互换；
- 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
- 重复步骤 2，直到堆的尺寸为 1。
动图演示
Python 代码
def heap_sort(alist):
if alist == None or len(alist) == 0:
return
length = len(alist)
output = []
for i in range(length):
tempLen = len(alist)
for j in range(tempLen // 2, -1, -1):
preIndex = j
pexVal, heap = alist[preIndex], False
while 2 * preIndex < tempLen - 1 and not heap:
curIndex = 2 * preIndex + 1
if curIndex < tempLen - 1:
if alist[curIndex] < alist[curIndex + 1]:
curIndex += 1
if preIndex >= alist[curIndex]:
heap = True
else:
alist[preIndex] = alist[curIndex]
preIndex = curIndex
alist[preIndex] = preIndex
output.insert(0, alist.pop(0))
return output
test = [2, 6, 5, 9, 10, 3, 7]
print(heap_sort(test))
8. 计数排序
算法思想：
假设要排序的数组为 A = {1,0,3,1,0,1,1}这里最大值为3，最小值为0， 那么我们创建一个数组C，长度为3+1-0=4。然后一趟扫描数组A，得到A中各个元素的总数， 并保持到数组C的对应单元中。比如0 的出现次数为2次，则 C[0] = 2;1 的出现次 数为4次，则C[1] = 4。C=[2,4,0,1]由于C 是以A的元素为下标的，所以这样一做，A中的元素在C 中自然就成为有序的了,然后我们分别统计比0,1,3小的元素个数，如比1小（包括1）的元素有6个。更新 C,C=[2,6,0,7]，更新C是为了保证排序稳定。然后把这个在C中的记录按每个元素的计数展开到输出数组B中，排序就完成了。 也就是B[0] 到 B[1] 为0, B[2] 到 B[5] 为1 这样依此类推。
动图演示
python实现
def countSort(nums, order=1):
max_num = max(nums)
min_num = min(nums)
extra = [0] * (max_num - min_num + 1) # 创建桶
for n in nums:
extra[n - min_num] += 1
result = []
for i in range(len(extra)):
if extra[i] != 0:
result = result + ([min_num + i] * extra[i])
if order == 1:
return result
else:
return result[::-1]
test = [-2, 4, 6, 9, 0, 76, 21, 87, 65, 43, 32]
print(countSort(test))
print(countSort(test, 2))
9. 桶排序
算法思想：
桶排序的工作的原理：将数据通过函数映射到有限数量的桶里，每个桶再分别排序。这里对于每个桶的排序可以使用其他排序方法，也可以使用递归的桶排序。
桶排序的效率和两个因素有关：
- 映射函数
- 对每个桶选择的排序算法
同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
什么时候最快
当输入的数据可以均匀的分配到每一个桶中。
什么时候最慢
当输入的数据被分配到了同一个桶中。
算法步骤
Step 1： 设定一定数量的桶作为容器 Step 2： 遍历数据，将所有的数据放到桶里 Step 3： 对每个不是空的桶进行排序 Step 4： 将每个桶的数据合并起来
python实现
# 首先定义插入排序法
def insert_sort(nums, order=1):
# 第一个数不动，从第二个数开始比较
for i in range(1, len(nums)):
j = i - 1
tmp = nums[i] # 记录本次待比较的词语
while j >= 0:
if tmp < nums[j]:
nums[j + 1] = nums[j]
nums[j] = tmp
j = j - 1
else:
break
if order == 1:
return nums
else:
return nums[::-1]
def bucket_sort(nums, n, order=1):
max_num = max(nums)
min_num = min(nums)
step = (max_num + 0.1 - min_num) / int(n)
# print(step)
tong = [[] for _ in range(n)]
for i in range(len(nums)):
# int((nums[i] - min_num) / step) 第几个桶
tong[int((nums[i] - min_num) / step)].append(nums[i])
result = []
print(tong)
for k in range(n):
tong[k] = insert_sort(tong[k])
result = result + tong[k]
if order == 1:
return result
else:
return result[::-1]
nums = [50, 100, 10, 8, 9, 5, 6, 7, 18, 13, 6.5, 10.1, 10.2, 100.3]
print(bucket_sort(nums, 5))
print(bucket_sort(nums, 5, 0))
10. 基数排序
算法思想：
使用python实现基数排序，基数排序也是非比较的排序方法，并且它也是基于桶排序的。
基数排序的原理在于把数字按照不同的位切分，首先排序最后一位，然后排序倒数第二位，一直到排序最高位。因为最高位是最重要的，所以放在最后。
基数排序的缺点在于不能处理小数和负数。相对于计数排序和桶排序，基数排序的优点在于当数据的分布不均匀的时候，占用的空间更少。
算法步骤
Step 1: 获取最大位数，确定循环次数 Step 2: 设置10个桶，因为0-9只有10个数 Step 3: 每次循环排序1个位数
动图演示
python实现
def radix_sort(nums, order=1):
k = len(str(max(nums))) # 最大的数的位数
for i in range(k):
buckets = [[] for _ in range(10)]
for num in nums:
# 获取当前排序位数上的数字
buckets[int(num / (10 ** i)) % 10].append(num)
nums = []
for bucket in buckets:
nums = nums + bucket
if order == 1:
return nums
else:
return nums[::-1]
nums = [1, 3, 5, 7, 9, 11, 0, 2, 100, 102, 103, 98, 78]
print(radix_sort(nums, 1))
print(radix_sort(nums, 0))
基数排序 vs 计数排序 vs 桶排序
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
- 基数排序：根据键值的每位数字来分配桶；
- 计数排序：每个桶只存储单一键值；
- 桶排序：每个桶存储一定范围的数值；