一、综述
排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括：
时间复杂度
-
平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。
-
线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序。
-
O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序。
-
线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序
关于稳定性
稳定的排序算法：冒泡、插入、归并；
不稳定的排序算法有：选择、希尔、快速、堆排序
名词解释
n:数据规模
in-place:占用常数内存，不占用额外内存
out-place：占用额外的内存
稳定性：前后两个值相等的元素排序后相对位置不变
说明：所有的排序都是按照由小到大来讲解的。
二、冒泡排序
作为最简单的排序算法，冒泡排序是大家入门算法学习时的必经之路。
冒泡很形象的说明了该算法的思想：
①选取序列的第一个元素，与下一个元素比较大小
②如果小于下一个元素，则选定下一个元素与下下一个元素进行比较；大于下一个元素，则这两个元素交换位置，并选择这个元素与下下个元素进行比较。
③重复步骤①②直到序列的最后
④将序列分为以排序序列和未排序序列，对未排序序列重复①②③。
Python实现：
import time
def bubbleSort(arr):
n = len(arr)-1
while n > 0:
i = 0
while i < n:
if arr[i] > arr[i+1]:
arr[i],arr[i+1] = arr[i+1],arr[i]
i+=1
n-=1
return arr
arr = [45,2.1,3,67,21,90,20,13,45,23,12,34,56,78,90,0,1,2,3,1,2,9,7,8,4,6]
t0 = time.perf_counter()
bubbleSort(arr)
t1 = time.perf_counter()
print('共%.5f秒' %(t1-t0))
print (arr) 三、插入排序
插入排序的思路类似于打扑克牌，将无序的牌插到有序的牌的合适位置。
①将序列分成有序序列（初始设置第一个元素为有序序列）和无序序列。
②将无序序列中的每一个元素插入到有序序列中的合适位置，并更新有序序列
③重复步骤①②
Python代码实现：
import time
def insertSort(arr):
for i in range(0,len(arr)):#大循环，遍历所有元素，以进行插入
current = arr[i] #将被选中带插入的元素选中
preIndex = i - 1
while preIndex >= 0 and arr[preIndex] > current:#判断在有序序列中的插入位置
arr[preIndex + 1] = arr[preIndex]
preIndex-=1 #向前移位排序
arr[preIndex + 1] = current#将选中待排序的元素插入列表
return arr
arr = [45,2.1,3,67,21,90,20,13,45,23,12,34,56,78,90,0,1,2,3,1,2,9,7,8,4,6]
t0 = time.perf_counter()
insertSort(arr)
t1 = time.perf_counter()
print('共%.5f秒' %(t1-t0))
print (arr)
四、选择排序
选择排序是选定一个假设的最小的值，从剩下列表里选出最小的与之交换。再依次循环下去。
①选择未排序序列的第一个元素为选定的元素
②将选定的元素与剩下的比较，找到序列中的最小值，放到序列起始位置
③从剩余未排序序列中寻找最小的元素，放到有序序列的最后
④重复步骤①②③
Python代码实现:
import time
def selectSort(arr):
i = 0
for i in range(0,len(arr)-1):
smaller = arr[i] #每次循环选择下一个元素作为选定的最小值
for j in range(i+1,len(arr)):
if arr[j] < smaller:
smaller = arr[j] #找出剩下未排序元素中的最小值
smallerIndex = j#最小值的索引
if smaller < arr[i]:
arr[i],arr[smallerIndex] = arr[smallerIndex],arr[i]#将最小值与选定的值互换位置
return arr
arr = [45,2.1,3,67,21,90,20,13,45,23,12,34,56,78,90,0,1,2,3,1,2,9,7,8,4,6]
t0 = time.perf_counter()
selectSort(arr)
t1 = time.perf_counter()
print('共%.5f秒' %(t1-t0))
print (arr) 五、希尔排序
希尔排序是插入排序的变种，基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
①选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
②按增量序列个数 k，对序列进行 k 趟排序；
③每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
Python代码实现：
import time
def shellSort(arr):
n = len(arr)
h = 1
while h < n/3:
h = h*3 +1
while h >=1:
for i in range(h,n):
j = i
while j >= h and arr[j] < arr[j-h]:
arr[j],arr[j-h] = arr[j-h],arr[j]
j-=h
h = h//3
print(arr)
arr = [45,2.1,3,67,21,90,20,13,45,23,12,34,56,78,90,0,1,2,3,1,2,9,7,8,4,6]
t0 = time.perf_counter()
shellSort(arr)
t1 = time.perf_counter()
print('共计%.6f' %(t1 - t0))
print (arr) 六、归并排序
归并排序是一种典型的采用分治思想的排序算法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之。
示意图如下：
①Divide：将序列一直分割成单个元素（单个元素是有序的）
②申请空间，将两个指针分别指向两个序列的第一个元素
③两个指针依次遍历序列，将排序结果依次放入申请的空间中
④重复操作②③，直到合并成原始序列长度。
Python代码实现：
import time
def mergeUnite(left,right):
result = []
while left and right:
if left[0] > right[0]:
result.append(right.pop(0))
else:
result.append(left.pop(0))
while left:
result.append(left.pop(0))
while right:
result.append(right.pop(0))
return result
def mergeDivide(arr):
if len(arr)<2: #Divide的终止条件（arr所含元素为一个）
return arr
middle = len(arr)//2
left = arr[0:middle]
right = arr[middle:]
return mergeUnite(mergeDivide(left),mergeDivide(right))
def mergeSort(arr):
return mergeDivide(arr)
arr = [45,2.1,3,67,21,90,20,13,45,23,12,34,56,78,90,0,1,2,3,1,2,9,7,8,4,6]
t0 = time.perf_counter()
mergeSort(arr)
t1 = time.perf_counter()
print('共计%.6f' %(t1 - t0))
print (arr) 七、快速排序
快速排序是一种比较常用的排序算法，快排也是采用的分治思想。可以看做是冒泡排序基础上的递归分治算法。选定一个分区（元素），将小于该分区的元素全部放到分区的前面，大于该分区的元素放到后面。然后对于得到到的两个列表重复上面的操作。
①从列表中挑出一个基准，一般初始选择第一个元素
②将小于基准的元素放到基准前面，大于基准的元素放到基准后面
③递归地将小于基准和大于基准的子序列排序
关于快速排序有许多种实现的方法，这里主要给出两种：单向扫描和双向扫描。
Python代码实现：
#快速排序方法一
''''''
方法一单向扫描划分数组。使用两个下标i和j，分别指向最后一个小记录的下标和第一个未处
理记录的下标。
优点：思路清晰，代码简洁易懂。
缺点：只向一个方向扫描，每遇到小记录元素就与下标i所指的大记录元素交换位置，不能将该
大记录元素一步到位交换到右侧的正确位置，导致某些大记录元素需要交换多次才能到达正确
位置。
一个极端的例子，a=[5,6,4,2,3,1]，值为6的元素被交换了4次，才最终到达正确位置，都快赶
上冒泡排序的低效了。
''''''
import time
def quickPartition(arr,left,right):
base = left
i = left
par = arr[left]
index = left+1
while index < right:
if par>arr[index]:
i+=1 #记录小于par的元素个数
if i != index:
arr[i],arr[index] = arr[index],arr[base] #将小的元素换到大的元素前面去
index+=1
arr[i],arr[left] = arr[left],arr[i]#将par放到合适的位置
return index
def quickSort(arr,left = None,right = None):
left = 0 if not isinstance(left,(int,float)) else left
right = len(arr)-1 if not isinstance(right,(int,float)) else right
if left < right: #停止排序条件
partitionIndex = quickPartition(arr,left,right)
quickSort(arr,left,partitionIndex-1)
quickSort(arr,partitionIndex+1,right)
return arr
arr = [45,2.1,3,67,21,90,20,13,45,23,12,34,56,78,90,0,1,2,3,1,2,9,7,8,4,6]
t0 = time.perf_counter()
quickSort(arr)
t1 = time.perf_counter()
print('共计%.6f' %(t1 - t0))
print (arr)
#快速排序方法二
'''
方法二：双向扫描划分数组。方法一中被交换的大记录元素不能一步到位交换到右侧的正确位置
，导致出现重复交换。
我们可以通过从数组的两端交替向中间扫描，每扫描一次就把“不合群”的元素交换到另一侧的方
法，确保每个位置的元素最多只被交换一次，这样效率要高于方法一。
为了保证小记录元素小于枢纽元，我们需要选取a[right]作为枢纽元，这样向右扫描时才不会越
界。
'''
import time
def quickPartition(arr,left,right):
par = arr[right]#分区边界，小于边界值放到前面，大于边界值放到后面
i = left
j = right
while i < j:
while arr[i] < par:
i+=1 #记录不满足后向小于边界值的值的索引
while i < j and arr[j] >= par:
j-=1#记录不满足向前大于边界值的值的索引
if i < j:
arr[i],arr[j] = arr[j],arr[i]#将违规的元素交换位置
arr[i],arr[right] = arr[right],arr[i]#将分区边界放到合适的位置
return i
def quickSort(arr,left = None,right = None):
left = 0 if not isinstance(left,(int,float)) else left
right = len(arr)-1 if not isinstance(right,(int,float)) else right
if left < right: #停止排序条件
partitionIndex = quickPartition(arr,left,right)
quickSort(arr,left,partitionIndex-1)
quickSort(arr,partitionIndex+1,right)
return arr
arr = [45,2.1,3,67,21,90,20,13,45,23,12,34,56,78,90,0,1,2,3,1,2,9,7,8,4,6]
t0 = time.perf_counter()
quickSort(arr)
t1 = time.perf_counter()
print('共计%.6f' %(t1 - t0))
print (arr)
八、总结
排序算法是算法体系中最基本最简单的算法了，就是因为其很基本很简单所以可以很快地上手，可以自己动手实践实践。
后续会继续学习堆排序和TimSort。
京公网安备 11010502036488号