关于时间复杂度：
平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。
线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；
O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。希尔排序
线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。
关于稳定性：
排序后 2 个相等键值的顺序和排序之前它们的顺序相同
稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。
不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。
名词解释：
n：数据规模
k：“桶”的个数
In-place：占用常数内存，不占用额外内存
Out-place：占用额外内存
1.冒泡排序
算法思想：数组中的数字，两两比较，大的下沉，小的上浮，第一轮遍历0-N，第二轮0-N-2，一直到只有一个数停止，这个数组就是有序的了。
代码展示：
def BubbleSort(arr):
for i in range(1,len(arr)):
for j in range(0,len(arr)-i):
if arr[j]>arr[j+1]:
arr[j],arr[j+1]=arr[j+1],arr[j]
return arr
if __name__ == '__main__':
a=[1,2,3,5,4,8]
print(BubbleSort(a))2.选择排序
算法思想：首先是在n个数里面选择最小的，然后再2到n个数里面选择最小的，一直循环，一直到整个数组有序。
代码展示：
def SelectSort(arr):
for i in range(len(arr)-1):
minIndex=i
for j in range(i+1,len(arr)):
if arr[j]<arr[minIndex]:
minIndex=j
if i != minIndex:
arr[i],arr[minIndex]=arr[minIndex],arr[i]
return arr
if __name__ == '__main__':
a=[1,4,3,9,7,6]
print(SelectSort(a))3.插入排序
算法思想：将第一元素看做一个有序序列，第二到第N个元素看做一个序列，一次将前两个看做有序，后面的看做一个序列，一直到整个序列有序为止。
代码展示：
def InsertSort(arr):
for i in range(len(arr)):
preIndex=i-1
current=arr[i]
while preIndex>=0 and arr[preIndex]>current:
arr[preIndex+1]=arr[preIndex]
preIndex-=1
arr[preIndex+1]=current
return arr
if __name__ == '__main__':
a=[1,5,9,6,4,84,3,2]
print(InsertSort(a))4.归并排序
算法思想：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；设定两个指针，最初位置分别为两个已经排序序列的起始位置；比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；重复步骤 3 直到某一指针达到序列尾；将另一序列剩下的所有元素直接复制到合并序列尾。
代码展示：
def mergeSort(arr):
import math
if(len(arr)<2):
return arr
middle = math.floor(len(arr)/2)
left, right = arr[0:middle], arr[middle:]
return merge(mergeSort(left), mergeSort(right))
def merge(left,right):
result = []
while left and right:
if left[0] <= right[0]:
result.append(left.pop(0));
else:
result.append(right.pop(0));
while left:
result.append(left.pop(0));
while right:
result.append(right.pop(0));
return result
if __name__ == '__main__':
a=[1,3,5,8,11,6,2]
print(mergeSort(a))5.堆排序
算法原理：首先要理解堆的概念，堆我们可以想象成为一棵完全二叉树，（完全二叉树就是任意节点都存在左孩子和右孩子，或者是按照左右顺序插入的二叉树）在堆里面有两个操作，一个是add也就是添加操作，另一个是popmax操作。add就是向完全二叉树中添加值。一般情况我们默认从0开始，则对于每个节点来说，左孩子=2i+1，右孩子=2i+2,父节点=i+1/2。结果都是取整的。
堆有大根堆和小根堆，大根堆就是最大的数作为头结点的完全二叉树。用于生序排序。小根堆就是头结点小于等于子节点，用于降序。
我们默认使用大根堆进行排序，add操作完成后，我们执行popmax操作，每次将头结点跟尾结点交换，对长度减一，然后新的头结点通过比较自己和子节点大小的方式将最大的值转移到头结点，在进行popmax操作，直到堆为1.
注意：要将取出来的最大值放在新的数组中，数组空间不够时采用每次翻倍的方式申请空间。
代码展示;
def buildMaxHeap(arr):
import math
for i in range(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 < arrLen and arr[left] > arr[largest]:
largest = left
if right < arrLen and arr[right] > arr[largest]:
largest = right
if largest != i:
swap(arr, i, largest)
heapify(arr, largest)
def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]
def heapSort(arr):
global arrLen
arrLen = len(arr)
buildMaxHeap(arr)
for i in range(len(arr)-1,0,-1):
swap(arr,0,i)
arrLen -=1
heapify(arr, 0)
return arr
if __name__ == '__main__':
a=[2,3,5,7,9,4,5,1]
print(heapSort(a))6.快速排序
算法思想：快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n²)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好，可是这是为什么呢，我也不知道。好在我的强迫症又犯了，查了 N 多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案：
快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
（1）算法步骤
从数列中挑出一个元素，称为 “基准”（pivot）;
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
代码展示：
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 = partition(arr, left, right)
quickSort(arr, left, partitionIndex-1)
quickSort(arr, partitionIndex+1, right)
return arr
def partition(arr, left, right):
pivot = left
index = pivot+1
i = index
while i <= right:
if arr[i] < arr[pivot]:
swap(arr, i, index)
index+=1
i+=1
swap(arr,pivot,index-1)
return index-1
def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]
if __name__ == '__main__':
a=[2,3,5,7,9,4,5,1]
print(quickSort(a))7.计数排序
算法原理：计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
代码展示：
def countingSort(arr, maxValue):
bucketLen = maxValue+1
bucket = [0]*bucketLen
sortedIndex =0
arrLen = len(arr)
for i in range(arrLen):
if not bucket[arr[i]]:
bucket[arr[i]]=0
bucket[arr[i]]+=1
for j in range(bucketLen):
while bucket[j]>0:
arr[sortedIndex] = j
sortedIndex+=1
bucket[j]-=1
return arr8.桶排序
算法原理：桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：
在额外空间充足的情况下，尽量增大桶的数量
使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
什么时候最快
当输入的数据可以均匀的分配到每一个桶中。
什么时候最慢
当输入的数据被分配到了同一个桶中。
代码展示：
def bucket_sort(s):
"""桶排序"""
min_num = min(s)
max_num = max(s)
# 桶的大小
bucket_range = (max_num-min_num) / len(s)
# 桶数组
count_list = [ [] for i in range(len(s) + 1)]
# 向桶数组填数
for i in s:
count_list[int((i-min_num)//bucket_range)].append(i)
s.clear()
# 回填，这里桶内部排序直接调用了sorted
for i in count_list:
for j in sorted(i):
s.append(j)
if __name__ == __main__ :
a = [3.2,6,8,4,2,6,7,3]
bucket_sort(a)
print(a) # [2, 3, 3.2, 4, 6, 6, 7, 8]9.基数排序
算法原理：基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
基数排序 vs 计数排序 vs 桶排序
基数排序有两种方法：
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
基数排序：根据键值的每位数字来分配桶；
计数排序：每个桶只存储单一键值；
桶排序：每个桶存储一定范围的数值；
代码展示：
def RadixSort(list):
i = 0 #初始为个位排序
n = 1 #最小的位数置为1（包含0）
max_num = max(list) #得到带排序数组中最大数
while max_num > 10**n: #得到最大数是几位数
n += 1
while i < n:
bucket = {} #用字典构建桶
for x in range(10):
bucket.setdefault(x, []) #将每个桶置空
for x in list: #对每一位进行排序
radix =int((x / (10**i)) % 10) #得到每位的基数
bucket[radix].append(x) #将对应的数组元素加入到相 #应位基数的桶中
j = 0
for k in range(10):
if len(bucket[k]) != 0: #若桶不为空
for y in bucket[k]: #将该桶中每个元素
list[j] = y #放回到数组中
j += 1
i += 1
return list
京公网安备 11010502036488号