目录
  1. 1. 前言
  2. 2. 八大排序
    1. 2.1. 直接插入排序
      1. 2.1.1. 基本思想
      2. 2.1.2. 步骤
      3. 2.1.3. 代码
    2. 2.2. 希尔排序
      1. 2.2.1. 基本思想
      2. 2.2.2. 步骤
      3. 2.2.3. 代码
    3. 2.3. 简单选择排序
      1. 2.3.1. 基本思想
      2. 2.3.2. 步骤
      3. 2.3.3. 代码
    4. 2.4. 堆排序
      1. 2.4.1. 基本思想
      2. 2.4.2. 步骤
      3. 2.4.3. 代码
      4. 2.4.4. Q&A
    5. 2.5. 冒泡排序
      1. 2.5.1. 基本思想
      2. 2.5.2. 步骤
      3. 2.5.3. 代码
    6. 2.6. 快速排序
      1. 2.6.1. 基本思想
      2. 2.6.2. 步骤
      3. 2.6.3. 代码
    7. 2.7. 归并排序
      1. 2.7.1. 基本思想
      2. 2.7.2. 步骤
      3. 2.7.3. 代码
    8. 2.8. 计数排序&桶排序&基数排序(了解)
      1. 2.8.1. 计数排序
        1. 2.8.1.1. 介绍
        2. 2.8.1.2. 代码
      2. 2.8.2. 基数排序
        1. 2.8.2.1. 介绍
        2. 2.8.2.2. 两种多关键码排序方法
        3. 2.8.2.3. 基于LSD方法的链式基数排序的基本思想
        4. 2.8.2.4. 步骤
        5. 2.8.2.5. Q&A
        6. 2.8.2.6. 代码
      3. 2.8.3. 桶排序
        1. 2.8.3.1. 介绍
        2. 2.8.3.2. 步骤
        3. 2.8.3.3. 缺点
    9. 2.9. 总结
      1. 2.9.1. 前7种算法的各种指标对比
      2. 2.9.2. 后3种算法的各种指标对比
      3. 2.9.3. 其它
      4. 2.9.4. 如何选择排序算法?
leetcode-排序

前言

回顾一下八大排序还有在leetcode中排序的经典题目。

  • 215-数组中的第k个最大元素
  • 347-前k个高频元素
  • 451-根据字符出现频率排序
  • 75-颜色分类

根据在排序过程中待排序记录是否全部被放置在内存中,排序分为:内排序和外排序。

内排序是在排序整个过程中,待排序的所有记录全部被放置在内存中。(八大排序)

外排序是由于排序的记录个数太多,不能同时放置在内存,整个排序过程需要在内外存之间多次交换数据才能进行。

八大排序

  • 插入排序
    • 直接插入排序
    • 希尔排序
  • 选择排序:
    • 简单选择排序
    • 堆排序
  • 交换排序:
    • 冒泡排序
    • 快速排序
  • 归并排序
  • 基数排序

直接插入排序

基本思想

 把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素,无序表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,将它插入到有序表中的适当位置,使之成为新的有序表,重复n-1次可完成排序过程。

步骤

  1. 从第一个元素开始,该元素可以认为已经被排序
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5

代码

#直接插入排序

def insertionSort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key

arr1 = [1,3,4,2,5]
insertionSort(arr1)
print(arr1)
  • 时间复杂度O(n2)O(n^2)
  • 空间复杂度O(1)O(1)
  • 稳定性:稳定

希尔排序

基本思想

 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录"基本有序"时,再对全体记录进行依次直接插入排序。

步骤

  1. 选择一个增量序列t1,t2,...,tkt_1,t_2,...,t_k,其中ti>tj,tk=1t_i > t_j, t_k = 1
  2. 按增量序列个数k,对序列进行k 趟排序;
  3. 每趟排序,根据对应的增量tit_i,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。

 我们简单处理增量序列:增量序列$d = {n/2 ,n/4, n/8 …1} n为要排序数的个数。即:先将要排序的一组记录按某个增量d$(n/2,n为要排序数的个数)分成若干组子序列,每组中记录的下标相差d。

 对每组中全部元素进行直接插入排序,然后再用一个较小的增量d/2(d/2)对它进行分组,在每组中再进行直接插入排序。继续不断缩小增量直至为11,最后使用直接插入排序完成排序。

代码

#希尔排序

def shellSort(arr):

n = len(arr)
gap = int(n/2)

while gap > 0:

for i in range(gap , n):

temp = arr[i]
j = i
while j >= gap and arr[j - gap] > temp:
arr[j] = arr[j - gap]
j -= gap
arr[j] = temp
gap = int(gap/2)

arr1 = [1,3,4,2,5]
shellSort(arr1)
print(arr1)

 希尔排序时效分析很难,关键码的比较次数与记录移动次数依赖于增量因子序列d的选取,特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的增量因子序列的方法。增量因子序列可以有各种取法,有取奇数的,也有取质数的,但需要注意:增量因子中除1 外没有公因子,且最后一个增量因子必须为1。

  • 时间复杂度O(n2)O(n^2)

  • 空间复杂度O(1)O(1)

  • 稳定性:不稳定

简单选择排序

基本思想

 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

步骤

  1. 从第一个元素开始,该元素可以被认为已经排序
  2. 从未排序的元素中,取出一个元素,与已排序的最后一个元素比较
  3. 如果已排序的最后一个元素大于该元素,则交换位置
  4. 直到排序完成

代码

#简单选择排序

def selectionSort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[min_idx] > arr[j]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]

arr1 = [1,3,4,2,5]
selectionSort(arr1)
print(arr1)
  • 时间复杂度O(n2)O(n^2)
  • 空间复杂度O(1)O(1)
  • 稳定性:稳定

堆排序

基本思想

  • 概念:堆排序(Heap Sort)是利用堆这种数据结构而设计的一种排序算法,是对直接选择排序的有效改进。
  • 堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。
  • 堆排序思想:将一个无序序列调整为一个堆,就能找出序列中的最大值(或最小值),然后将找出的这个元素与末尾元素交换,这样有序序列元素就增加一个,无序序列元素就减少一个,对新的无序序列重复操作,从而实现排序。
  • 堆的应用:是实现优先队列首选的数据结构,解决 TopK 问题、堆排序等。

步骤

  1. 构造初始堆。将给定无序序列构造成一个大顶堆(一般升序采用大顶堆,降序采用小顶堆);
  2. 将堆顶元素与末尾元素进行交换,使末尾元素最大。然后继续调整堆,再将堆顶元素与末尾元素交换,得到第二大元素;
  3. 重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素;
  4. 如此反复进行交换、重建、交换,直到整个序列有序。

 从算法描述来看,**堆排序需要两个过程,一是建立堆,二是堆顶与堆的最后一个元素交换位置。**所以堆排序有两个函数组成。一是建堆的渗透函数,二是反复调用渗透函数实现排序的函数。

代码

#堆排序-升序-大顶堆

#调整堆
def heapify(arr, n, i):

largest = i
l = 2 * i + 1 #left = 2 * i + 1
r = 2 * i + 2 #right = 2 * i + 2

if l < n and arr[i] < arr[l]: #小顶堆:if l < n and arr[i] > arr[l]
largest = l
if r < n and arr[largest] < arr[r]: #小顶堆:if l < n and arr[i] > arr[l]
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i] #change

heapify(arr, n, largest)


def heapSort(arr):
n = len(arr)

#bulid a maxheap
for i in range(n, -1, -1):
heapify(arr, n, i)

#一个个交换元素
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] #change
heapify(arr, i, 0)


arr1 = [1,3,4,2,5]
heapSort(arr1)
print(arr1)

'''
output:1,2,3,4,5
'''
#完善版

class Heap:
def __init__(self,s):
self.heap = self.bulid_max_heap(s)

def max_heapify(self, heap, heap_size, root):
left = 2 * root + 1
right = 2 * root + 2
larger = root
#如果小于 list 的长度则进行判断。
if left <= heap_size and heap[larger] < heap[left]:
larger = left
if right <= heap_size and heap[larger] < heap[right]:
larger = right
if larger != root:
#相当于如果交换就与最小的那个交换
heap[larger], heap[root] = heap[root], heap[larger]
self.max_heapify(heap, heap_size, larger)

def bulid_max_heap (self, heap):
heap_size = len(heap) - 1
#即从最后一个非叶子结点进行对排序,一直到根结点,
#确保每一个子堆都是大根堆
for i in range((heap_size - 1)//2, -1, -1):
self.max_heapify(heap, heap_size,i)
return heap


def heap_sort(self):
heap = copy.copy(self.heap)
#对大根堆进行排序,即把最大值放到最后,
#再把最后一个值放到最前,然后进行堆排序,
#循环,直到 list 从小到大排好序。
for i in range(len(heap)-1,-1,-1):
heap[0],heap[i] = heap[i],heap[0]
self.max_heapify(heap, i - 1, 0)
return heap

def heap_insert(self, data):
heap = self.heap
heap.append(data)

heap_size = len(heap) - 1
father = (heap_size - 1) // 2
son = heap_size
while father>=0:
if heap[father] < heap[son]:
heap[father],heap[son] = heap[son], heap[father]
son = father
father = (father -1) // 2
else:
break
return heap

a = [30, 50, 57, 77, 62, 78, 94, 80, 84]
heap = Heap(a)
print(heap.heap)

heap.heap_insert(100)
heap.heap_insert(1)
print(heap.heap)
  • 时间复杂度:O(nlogn)
    • 初始化建堆过程时间:O(n)
    • 更改堆元素后重建堆时间:O(nlogn),循环 n -1 次,每次都是从根节点往下循环查找,所以每一次时间是 logn,总时间:logn(n-1) = nlogn - logn ,所以复杂度是 O(nlogn)
  • 空间复杂度:O(1)
  • 稳定性:不稳定

Q&A

Q1:如何把一棵完全二叉树构造成一个大顶堆?

A1:一个很好的方法是遍历二叉树的非叶子节点自下往上的构造大顶堆,针对每个非叶子节点,都跟它的左右子节点比较,把最大的值换到这个子树的父节点。


Q2:为什么要从非叶子节点开始,而不是从最后一个节点开始?

A2:因为叶子节点下面没有子节点了,就没必要操作了。


Q3:为什么要从下往上而不是从上往下遍历非叶子节点?

A3:我们从下面开始遍历调整每个节点成为它左右节点的最大值,那么一直往上的话,最后根节点一定是最大的值;但是如果我们从上往下,上面满足了大顶堆,下面不满足,调整后,上面可能又不满足了,所以从下往上是最好的方案。


Q4:海量数据中找出最大的100个数字?

A4:使用高效的排序算法,如快排、堆排。


Q5:如果数据量很大,一个机器的内存不足以一次读取那么多数据,就不能使用A4方法。该如何解决?

A5:不使用分布式机器计算,使用一个机器也能找出TopK的经典算法就是使用堆排序了,具体方法是:

  • 维护一个大小为 K 的小顶堆,依次将数据放入堆中,当堆的大小满了的时候,只需要将堆顶元素与下一个数比较
    • 如果小于堆顶元素,则直接忽略,比较下一个元素;
    • 如果大于堆顶元素,则将当前的堆顶元素抛弃,并将该元素插入堆中。遍历完全部数据,Top K 的元素也自然都在堆里面了。

冒泡排序

基本思想

 在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。

步骤

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

代码

#冒泡排序

def bubbleSort(arr):
n = len(arr)

#遍历所有数组元素
for i in range(n):

#Last i elements are already in place
for j in range(0, n - i - 1):

if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]


arr1 = [1,3,4,2,5]
bubbleSort(arr1)
print(arr1)
  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)
  • 稳定性:稳定

快速排序

基本思想

快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为较小和较大的2个子序列,然后递归地排序两个子序列。

步骤

  1. 挑选基准值:从数列中挑出一个元素,称为"基准"(pivot);
  2. 分割:重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(与基准值相等的数可以到任何一边)。在这个分割结束之后,对基准值的排序就已经完成;
  3. 递归排序子序列:递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

递归到最底部的判断条件是数列的大小是零或一,此时该数列显然已经有序。

选取基准值有数种具体方法,此选取方法对排序的时间性能有决定性影响。

代码

#快速排序-递归

def partition(arr, low, high):
i = low - 1 #最小元素索引
pivot = arr[high]

for j in range(low, high):

#当前元素小于或等于pivot
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]

arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1

# arr[] --> 排序数组
# low --> 起始索引
# high --> 结束索引

def quickSort(arr, low, high):
if low < high:

pi = partition(arr, low, high)

quickSort(arr, low, pi - 1)
quickSort(arr, pi + 1, high)


arr1 = [1,3,4,2,5]
quickSort(arr1, 0, len(arr1) - 1)
print(arr1)
  • 任何递归的本质,实际上就是入栈出栈的过程。也就是说只要是递归的,都可以改成非递归,因此快排也可以通过栈来实现。
#快速排序-非递归

def partition(arr, low, high):
i = low - 1 #最小元素索引
pivot = arr[high]

for j in range(low, high):

#当前元素小于或等于pivot
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]

arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1

# arr[] --> 排序数组
# low --> 起始索引
# high --> 结束索引

def quickSort(arr, low, high):
if len(arr) < 2:
return arr
stack = [len(arr) - 1, 0]
while stack:
low = stack.pop()
high = stack.pop()
index = partition(arr, low, high)
if low < index - 1:
stack.append(index - 1)
stack.append(low)
if high > index + 1:
stack.append(high)
stack.append(index + 1)

arr1 = [1,3,4,2,5]
quickSort(arr1, 0, len(arr1) - 1)
print(arr1)
  • 时间复杂度:O(nlogn)~O(n^2)
  • 空间复杂度:O(logn)~O(n)
  • 稳定性:不稳定

 快速排序是通常被认为在同数量级(O(nlog2n))的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时,快排序反而蜕化为冒泡排序。为改进之,通常以“三者取中法”来选取基准记录,即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。

归并排序

基本思想

 归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

步骤

  • 递归-有序数组的合并
    1. arr[i…n]由两个有序子表arr[i…m]arr[m+1…n]组成,两个子表长度分别为n-i +1n-m
    2. j=m+1;k=i;i=i; //置两个子表的起始下标及辅助数组的起始下标
    3. i>mj>n,转4 //其中一个子表已合并完,比较选取结束
    4. //选取arr[i]arr[j]较小的存入辅助数组arrf
      如果arr[i]<arr[j],arrf[k]=arr[i]; i++; k++; 转2
      否则,arrf[k]=arr[j]; j++; k++; 转2
    5. //将尚未处理完的子表中元素存入arrf
      如果i<=m,将arr[i…m]存入arrf[k…n] //前一子表非空
      如果j<=n , 将arr[j…n] 存入arrf[k…n] //后一子表非空
    6. 合并结束。
  • 非递归-不需要额外的空间。直接在原数组上进行切割合并

代码

#归并排序-递归(按步骤描述的代码)

#归并排序

def merge(arr, l, m, r):
n1 = m - l + 1
n2 = r - m

#创建临时数组
L = [0] * n1
R = [0] * n2

#拷贝数据到临时数组 arrays L[] 和 R[]
for i in range(0, n1):
L[i] = arr[l + i]

for j in range(0, n2):
R[j] = arr[m + 1 + j]

#归并临时数组到arr[l..r]
i = 0 #初始化第一个子数组的索引
j = 0 #初始化第二个子数组的索引
k = l #初始归并子数组的索引

while i < n1 and j < n2:
if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1

# 拷贝 L[] 的保留元素
while i < n1:
arr[k] = L[i]
i += 1
k += 1

# 拷贝 R[] 的保留元素
while j < n2:
arr[k] = R[j]
j += 1
k += 1

def mergeSort(arr,l,r):
if l < r:


m = int((l+(r-1))/2)


mergeSort(arr, l, m)
mergeSort(arr, m+1, r)
merge(arr, l, m, r)


arr1 = [1,3,4,2,5]
mergeSort(arr1, 0, len(arr1) - 1)
print(arr1)
#归并排序-简化版递归!!

def merge(left, right):
result = []
l = r = 0
while l < len(left) and r < len(right):
if left[l] < right[r]:
result.append(left[l])
l += 1
else:
result.append(right[r])
r += 1
result += left[l:]
result += right[r:]
return result


def mergeSort(arr):
if len(arr) <= 1:
return arr
mid = len(arr)//2
left = mergeSort(arr[:mid])
right = mergeSort(arr[mid:])
return merge(left, right)


arr = [1,3,4,2,5]
print(mergeSort(arr))
#非递归
def merge(arr, l, m, r):
left = arr[l: m] #切割数组
right = arr[m: r]
l = 0 #指向左边数组的索引
r = 0 #指向右边数组的索引
result = []
while l < len(left) and r < len(right):
if left[l] <= right[r]:
result.append(left[l])
l += 1
else:
result.append(right[r])
r += 1
result += left[l:]
result += right[r:]
arr[l: r] = result

def mergeSort(arr):
i = 1 # 初始时子数组元素个数是1
while i < len(arr):
low = 0
while low < len(arr):
mid = low + i #mid前后均为有序
right = min(low + 2 * i, len(arr))
if mid < right:
merge(arr, low, mid, right)
low += 2 * i
i *= 2 #每次合并两个,子数组元素个数是以2的倍数增长

arr = [1,3,4,2,5]
mergeSort(arr)
print(mergeSort(arr))
  • 时间复杂度:O(nlogn)
  • 空间复杂度:O(n)
  • 稳定性:稳定

计数排序&桶排序&基数排序(了解)

 计数排序,基数排序,桶排序等非比较排序算法平均时间复杂度都是O(n)。这些排序因为其待排序元素本身就含有了定位特征,因而不需要比较就可以确定其前后位置,从而可以突破比较排序算法时间复杂度O(nlgn)的理论下限。

计数排序

介绍

计数排序是一种非基于元素比较的排序算法,而是将待排序数组元素转化为计数数组的索引值,从而间接使待排序数组具有顺序性。

计数排序的实现一般有两种形式:基于辅助数组和基于桶排序。

  • 基于辅助数组
    • 整个过程包含三个数组:待排序数组A、计数数组B和输出数组C。
    • 简单来说,就是通过统计待排序数组A中元素不同值的分布直方图,生成计数数组B,然后计算计数数组B的前缀和(此步操作可以看成计算待排序数组A中每个元素的位置信息),最后通过逆序循环将元素对应赋值到输出数组C中,输出数组C即是最终排序结果。
  • 基于桶排序
    • 其实就是用桶排序来维护稳定性,因为在每个桶中的元素是以队列结构排序的,可以维护元素的顺序。
    • 主要步骤:
      1. 按元素的最大健值与最小健值之差来创建指定数量的桶,并在每个桶中创建一个队列。
      2. 按顺序遍历待排序数组,将它们放到对应桶的队列中。
      3. 按桶编号顺序进行遍历,将每个桶中队列按顺序输出回原数组中。
    • 举例:
      • nums=[2, 1, 3, 1, 5] , 首先扫描一遍获取最小值和最大值。 maxValue = 5 , minValue = 1 ,于是开一个长度maxValue - minValue + 1长度的计数器数组 counter 。
        1. 分配:扫描一遍原始数组,以当前值 - minValue 作为下标,将该下标的计数器增1。即统计每个元素出现的频率,得到 counter = [2, 1, 1, 0, 1] ,例如 counter[0] 表示值 0 + minValue = 1 出现了2次。
        2. 收集:扫描一遍计数器数组,按顺序把值收集起来。即counter[0] = 2 表示 1 出现了两次,那就向原始数组写入两个1, counter[1] = 1 表示 2 出现了1次,那就向原始数组写入一个2,依次类推,最终原始数组变为 [1,1,2,3,5] ,排序好了。
  • 计数排序本质上是一种特殊的桶排序,当桶的个数最大的时候,就是计数排序。
  • 缺点:可以看到辅助数组的长度和桶的数量由最大值和最小值决定,假如两者之差很大,而待排序数组又很小,那么就会导致辅助数组或桶大量浪费。
  • 应用:计数排序是用来排序0到100之间的数字的最好的算法,但是它不适合按字母顺序排序人名。但是,计数排序可以用在基数排序中的算法来排序数据范围很大的数组。当输入的元素是 n 个 0 到 k 之间的整数时,它的运行时间是 O(n+k)。
假定输入是个数组A【1...n】, length【A】=n。 另外还需要一个存放排序结果的数组B【1...n】,以及提供临时存储区的C【0...k】(k是所有元素中最大的一个)。算法伪代码:

COUNTING-SORT(A, B, n, k)
for i <- 0 to k
do C[i] <- 0
for j <- 1 to n
do C[A[j]] <- C[A[j]] + 1
for i <- 1 to k
do C[i] <- C[i] + C[i - 1]
for j <- n downto 1
do B[C[A[j]]] <- A[j]
C[A[j]] <- C[A[j]] - 1

1、找出待排序的数组中最大和最小的元素
2、统计数组中每个值为t的元素出现的次数,存入数组C的第t项
3、对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加)
4、反向填充目标数组:将每个元素t放在新数组的第C(t)项,每放一个元素就将C(t)减去1

代码

def countSort(arr): 

output = [0 for i in range(256)]

count = [0 for i in range(256)]

ans = ["" for _ in arr]

for i in arr:
count[ord(i)] += 1

for i in range(256):
count[i] += count[i-1]

for i in range(len(arr)):
output[count[ord(arr[i])]-1] = arr[i]
count[ord(arr[i])] -= 1

for i in range(len(arr)):
ans[i] = output[i]
return ans

arr = "wwwrunoobcom"
ans = countSort(arr)
print ( "字符数组排序 %s" %("".join(ans)) )
  • 计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。

基数排序

介绍

  • 基数排序改善了计数排序,简单来说,基数排序算法就是将整数或字符串切分成不同的数字或字符,然后按对应位置的数或字符分别进行比较,这样就能将辅助数组或桶的数量降低到一个较小的值,经过多轮排序后得到最终的排序结果
  • 是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以是稳定的。

两种多关键码排序方法

  • 实例:扑克牌中52 张牌,可按花色和面值分成两个字段,其大小关系为:
    • 花色:梅花<方块<红心<黑心
    • 面值:2<3<4<5<6 < 7 < 8 < 9 < 10 < J < Q < K < A

 若对扑克牌按花色、面值进行升序排序,得到如下序列:梅花2<梅花3<…<梅花A<方块2<方块3<…<方块A<红心2<红心3<…<红心A<黑心2<黑心3<…<黑心A。

 即两张牌,若花色不同,不论面值怎样,花色低的那张牌小于花色高的,只有在同花色情况下,大小关系才由面值的大小确定。这就是多关键码排序。

  • 为得到排序结果,我们讨论两种排序方法:

    • 方法1:先对花色排序,将其分为4 个组,即梅花组、方块组、红心组、黑心组。再对每个组分别按面值进行排序,最后,将4 个组连接起来即可。

    • 方法2:先按13 个面值给出13 个编号组(2 号,3 号,…,A 号),将牌按面值依次放入对应的编号组,分成13 堆。再按花色给出4 个编号组(梅花、方块、红心、黑心),将2号组中牌取出分别放入对应花色组,再将3 号组中牌取出分别放入对应花色组,……,这样,4 个花色组中均按面值有序,然后,将4 个花色组依次连接起来即可。

    • 设n 个元素的待排序列包含d 个关键码{k1,k2,…,kd},则称序列对关键码{k1,k2,…,kd}有序是指:对于序列中任两个记录r[i]和rj都满足下列有序关系:

      (ki1,ki2,...,kid)<(kj1,kj2,...,kjd)(k^1_i,k^2_i,...,k^d_i) < (k^1_j,k^2_j,...,k^d_j)

其中,其中k1 称为最主位关键码,kd 称为最次位关键码 。

  • 多关键码排序按照从最主位关键码到最次位关键码或从最次位到最主位关键码的顺序逐次排序,分两种方法:
    • 最高位优先(Most Significant Digit first)法,简称MSD 法:
      1. 先按k1 排序分组,将序列分成若干子序列,同一组序列的记录中,关键码k1 相等。
      2. 再对各组按k2 排序分成子组,之后,对后面的关键码继续这样的排序分组,直到按最次位关键码kd 对各子组排序后。
      3. 再将各组连接起来,便得到一个有序序列。扑克牌按花色、面值排序中介绍的方法一即是MSD 法。
    • 最低位优先(Least Significant Digit first)法,简称LSD 法:
      1. 先从kd 开始排序,再对kd-1进行排序,依次重复,直到按k1排序分组分成最小的子序列后。
      2. 最后将各个子序列连接起来,便可得到一个有序的序列, 扑克牌按花色、面值排序中介绍的方法二即是LSD 法。
  • 由于不需要分堆对每堆单独排序,LSD方法往往比MSD简单而开销小。

基于LSD方法的链式基数排序的基本思想

 “多关键字排序”的思想实现“单关键字排序”。对数字型或字符型的单关键字,可以看作由多个数位或多个字符构成的多关键字,此时可以采用“分配-收集”的方法进行排序,这一过程称作基数排序法,其中每个数字或字符可能的取值个数称为基数。比如,扑克牌的花色基数为4,面值基数为13。在整理扑克牌时,既可以先按花色整理,也可以先按面值整理。按花色整理时,先按红、黑、方、花的顺序分成4摞(分配),再按此顺序再叠放在一起(收集),然后按面值的顺序分成13摞(分配),再按此顺序叠放在一起(收集),如此进行二次分配和收集即可将扑克牌排列有序。

 基数排序的简单描述就是将数字拆分为个位十位百位,每个位依次排序。因为这对算法稳定要求高,所以我们对数位排序用到上一个排序方法计数排序。因为基数排序要经过d (数据长度)次排序, 每次使用计数排序, 计数排序的复杂度为 On), d 相当于常量和N无关,所以基数排序也是 O(n)。基数排序虽然是线性复杂度, 即对n个数字处理了n次,但是每一次代价都比较高, 而且使用计数排序的基数排序不能进行原地排序,需要更多的内存, 并且快速排序可能更好地利用硬件的缓存, 所以比较起来,像快速排序这些原地排序算法更可取**。对于一个位数有限的十进制数,我们可以把它看作一个多元组,从高位到低位关键字重要程度依次递减。可以使用基数排序对一些位数有限的十进制数排序。**

步骤

  1. 将所有待排序整数(注意,必须是非负整数)统一为位数相同的整数,位数较少的前面补零。一般用10进制,也可以用16进制甚至2进制。所以前提是能够找到最大值,得到最长的位数,设 k 进制下最长为位数为 d 。
  2. 从最低位开始,依次进行一次稳定排序。这样从最低位一直到最高位排序完成以后,整个序列就变成了一个有序序列。
    举个例子,有一个整数序列,0, 123, 45, 386, 106,下面是排序过程:
  • 第一次排序,个位,000 123 045 386 106,无任何变化
  • 第二次排序,十位,000 106 123 045 386
  • 第三次排序,百位,000 045 106 123 386
  • 最终结果,0, 45, 106, 123, 386, 排序完成。

Q&A

 为什么同一数位的排序子程序要用稳定排序?因为稳定排序能将上一次排序的成果保留下来。例如十位数的排序过程能保留个位数的排序成果,百位数的排序过程能保留十位数的排序成果。能不能用2进制?能,可以把待排序序列中的每个整数都看成是01组成的二进制数值。那这样的话,岂不是任意一个非负整数序列都可以用基数排序算法?理论上是的,假设待排序序列中最大整数为2 4 . 1,则最大位数 d=64 ,时间复杂度为 O(64n) 。可见任意一个非负整数序列都可以在线性时间内完成排序。

 既然任意一个非负整数序列都可以在线性时间内完成排序,那么基于比较排序的算法有什么意义呢?基于比较的排序算法,时间复杂度是 O(nlogn) ,看起来比 O(64n) 慢,仔细一想,其实不是, O(nlogn) 只有当序列非常长,达到2 个元素的时候,才会与 O(64n) 相等,因此,64这个常数系数太大了,大部分时候, n 远远小于2 ,基于比较的排序算法还是比 O(64n) 快的。
当使用2进制时, k=2 最小,位数 d 最大,时间复杂度 O(nd) 会变大,空间复杂度 O(n+k) 会变小。当用最大值作为基数时, k=maxV 最大, d=1 最小,此时时间复杂度 O(nd) 变小,但是空间复杂度 O(n+k) 会急剧增大,此时基数排序退化成了计数排序。

代码

import math
def radix_sort(lists, radix=10):
k = int(math.ceil(math.log(max(lists), radix)))
bucket = [[] for i in range(radix)]
for i in range(1, k+1):
for j in lists:
bucket[j/(radix**(i-1)) % (radix**i)].append(j)
del lists[:]
for z in bucket:
lists += z
del z[:]
return lists

桶排序

介绍

 桶排序是改善计数排序的方法之一,其基本思想是将待排序数组分配到若干个桶内,然后每个桶内再各自进行排序,桶内的排序可以使用不同的算法,比如插入排序或快速排序,属于分治法。每个桶执行完排序后,最后依次将每个桶内的有序序列拿出来,即得到完整的排序结果。

步骤

  1. 将待排序元素划分到不同的桶。先扫描一遍序列求出最大值 maxV 和最小值 minV ,设桶的个数为 k ,则把区间 [minV, maxV] 均匀划分成 k 个区间,每个区间就是一个桶。将序列中的元素分配到各自的桶。
  2. 对每个桶内的元素进行排序。可以选择任意一种排序算法。
  3. 将各个桶中的元素合并成一个大的有序序列。
  4. 假设数据是均匀分布的,则每个桶的元素平均个数为 n/k 。假设选择用快速排序对每个桶内的元素进行排序,那么每次排序的时间复杂度为 O(n/klog(n/k)) 。总的时间复杂度为 O(n)+O(m)O(n/klog(n/k)) = O(n+nlog(n/k)) = O(n+nlogn-nlogk) 。当 k 接近于 n 时,桶排序的时间复杂度就可以金斯认为是 O(n) 的。即桶越多,时间效率就越高,而桶越多,空间就越大。

当然,以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的 ,实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中,那就退化成一般的排序了。

缺点

  1. 首先是空间复杂度比较高,需要的额外开销大。排序有两个数组的空间开销,一个存放待排序数组,一个就是所谓的桶,比如待排序值是从0到m-1,那就需要m个桶,这个桶数组就要至少m个空间。
  2. 其次待排序的元素都要在一定的范围内等等。桶式排序是一种分配排序。分配排序的特定是不需要进行关键码的比较,但前提是要知道待排序列的一些具体情况。(分配排序的基本思想:说白了就是进行多次的桶式排序,基数排序过程无须比较关键字,而是通过“分配”和“收集”过程来实现排序。它们的时间复杂度可达到线性阶:O(n)

总结

前7种算法的各种指标对比

排序算法 平均情况 最好情况 最坏情况 辅助空间 稳定性
冒泡排序 O(n2)O(n^2) O(n)O(n) O(n2)O(n^2) O(1)O(1) 稳定
简单选择排序 O(n2)O(n^2) O(n2)O(n^2) O(n2)O(n^2) O(1)O(1) 稳定
直接插入排序 O(n2)O(n^2) O(n)O(n) O(n2)O(n^2) O(1)O(1) 稳定
希尔排序 O(nlogn)O(nlogn)~O(n2)O(n^2) O(n1.3)O(n^{1.3}) O(nlogn)O(nlogn) O(1) 不稳定
堆排序 O(nlogn)O(nlogn) O(nlogn)O(nlogn) O(nlogn)O(nlogn) O(1)O(1) 不稳定
归并排序 O(nlogn)O(nlogn) O(nlogn)O(nlogn) O(nlogn)O(nlogn) O(n)O(n) 稳定
快速排序 O(nlogn)O(nlogn) O(nlogn)O(nlogn) O(n2)O(n^2) O(logn)O(logn)~O(n)O(n) 不稳定

后3种算法的各种指标对比

排序算法 时间复杂度 空间复杂度 适用场景 稳定性
计数排序 O(n + maxV- minV) O(maxV-minV) maxV和minV差距尽可能小 稳定排序
基数排序 O(nd) O(n + k) 1.非负整数;2.maxV和minV差距尽可能小 稳定排序
桶排序 O(n + k) O(n + k) 元素尽可能均匀分布 稳定排序

其中,d表示位数,k在基数排序中表示k进制,在桶排序中表示桶的个数,maxV和minV表示元素的最大值和最小值。

其它

  • 当原表有序或基本有序时直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数,时间复杂度可降至O(n);
  • 当原表基本有序时,快速排序将蜕化为冒泡排序,时间复杂度提高为O(n^2);
  • 原表是否有序,对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。
  • 稳定排序的好处:排序算法如果是稳定的,那么从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。基数排序就是这样,先按低位排序,逐次按高位排序,低位相同的元素其顺序再高位也相同时是不会改变的。另外,如果排序算法稳定,可以避免多余的比较;
  • 首先,基数排序和计数排序都可以看作是桶排序。
  • 计数排序本质上是一种特殊的桶排序,当桶的个数取最大( maxV-minV+1 )的时候,就变成了计数排序。
  • 基数排序也是一种桶排序。桶排序是按值区间划分桶,基数排序是按数位来划分;基数排序可以看做是多轮桶排序,每个数位上都进行一轮桶排序。
  • 当用最大值作为基数时,基数排序就退化成了计数排序。
  • 当使用2进制时, k=2 最小,位数 d 最大,时间复杂度 O(nd) 会变大,空间复杂度 O(n+k) 会变小。当用最大值作为基数时, k=maxV 最大, d=1 最小,此时时间复杂度 O(nd) 变小,但是空间复杂度 O(n+k) 会急剧增大,此时基数排序退化成了计数排序。

如何选择排序算法?

影响排序的因素有很多,平均时间复杂度低的算法并不一定就是最优的。相反,有时平均时间复杂度高的算法可能更适合某些特殊情况。同时,选择算法时还得考虑它的可读性,以利于软件的维护。一般而言,需要考虑的因素有以下四点:

1.待排序的记录数目n的大小;

2.记录本身数据量的大小,也就是记录中除关键字外的其他信息量的大小;

3.关键字的结构及其分布情况;

4.对排序稳定性的要求。

  • 设待排序元素的个数为n
    • 当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序序。
      • 快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;
      • 堆排序 : 如果内存空间允许且要求稳定性
      • 归并排序:它有一定数量的数据移动,所以我们可能过与插入排序组合,先获得一定长度的序列,然后再合并,在效率上将有所提高。
    • 当n较大,内存空间允许,且要求稳定性 =》归并排序
    • 当n较小,可采用直接插入或直接选择排序。
      • 直接插入排序:当元素分布有序,直接插入排序将大大减少比较次数和移动记录的次数。
      • 直接选择排序 :元素分布有序,如果不要求稳定性,选择直接选择排序
    • 一般不使用或不直接使用传统的冒泡排序。
    • 基数排序
      • 它是一种稳定的排序算法,但有一定的局限性:
        • 关键字可分解。
        • 记录的关键字位数较少,如果密集更好
        • 如果是数字时,最好是无符号的,否则将增加相应的映射复杂度,可先将其正负分开排序。
文章作者: Lesy
文章链接: https://lesylin.com/2020/06/24/leetcode-%E6%8E%92%E5%BA%8F/
文章声明: 转载请注明文章链接
打赏
  • 微信
  • 支付宝

Comment