Ylin's Blog
0%

18:十大排序算法

发表于 更新于 分类于

用Python感受十大排序算法，首先我们对这十个排序进行分类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
十大排序算法：
	非线性时间比较类：
		交换类：
			冒泡排序
			快速排序
		插入类：
			直接插入排序
			希尔排序
		选择类：
			简单选择排序
			堆排序
		归并类#：
			归并排序
	线性时间排序：
		计数排序
		桶排序
		基数排序

非线性排序

冒泡排序

最经典的排序算法

算法思想

将数据中的每个数与相邻的数进行比较并交换，大数往上冒，小数向下沉。将每个数遍历排序一遍

算法步骤

  • 取第一个数，依次与下一个数进行排序，然后与小于(或大于)自己的数交换位置直到最后一个数
  • 如果未发生位置交换，说明数据有序，排序结束。如果发生了位置交换重复上一步

算法分析

时间复杂度：

  • 当排序为正序时，只需要排序一次，比较n-1次，时间复杂度为O(n),这是最优情况
  • 当排序为逆序时，需要进行n-1次遍历，每次比较n-i次，时间复杂度为O(n^2)，这是最差情况

算法代码

1
2
3
4
5
6
7
8
9
10
11
# 冒泡排序
def bubble_sort(nums):
    # 冒泡排序进行的次数n-1,每次遍历确定一个最大值
    for i in range(len(nums)-1):
        # j为进行比较的数据下标
        for j in range(len(nums)-1-i):
            # 若下标为j的数据大于其右相邻数据
            if nums[j] > nums[j+1]:
                # 二者交换数据
                nums[j],nums[j+1] = nums[j+1],nums[j]
    return nums

快速排序

也称为分区交换排序，它采用了分治思想，是冒泡排序的改良版。冒泡排序只能比较和交换两个数据，但是快速排序可以交换和比较两个分区，其效率更高

算法思想

选取一个基准值，将待排序数据分为左（小于基准值）和右（大于基准值）两个区间，然后对两个分区的数据进行相同的操作，最终得到一组有序数据

算法步骤

  • 选取待排序数据的第一个数值作为分区标准
  • 遍历数组，将小于标准的放在左边，大于标准的放在右边，则中间为标准数
  • 对标准数左右两个子序列分别进行（1）和（2）的操作
  • 当左右序列的长度均小于等于1时，排序完成

算法分析

时间复杂度

  • 如果选取的标准数位待排序数组的中位数，即每次划分后的左右子序列长度基本一致，时间复杂度为 O(n*log_2(n)),为最好情况
  • 如果待排序数组是逆序，且第一趟选取的标准数位待排序数组的最大值，经过n-1次比较后，得到一个n-1个元素的左子序列；然后第二趟选取的标准数仍然是最大值,…依次类推，最终的时间复杂度为 O(n^2)，这是最坏的情况

算法代码

学习版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 快速排序
def quick_sort(array):
    if len(array)<=1:			# 当子序列长度<=1
        return array			# 排序完成,停止递归
    else:
        small = []				# 由所有小于基准值的元素组成的子数组
        equal = []				# 包括基准值在内并且和基准相等的元素
        large = []				# 由所有大于基准值的元素组成的子数组
        reference = array[0]	 # 选择第一个数作为基准值
        # 遍历array中的每一个元素
        for s in array:
            # 当前元素小于基准值时
            if s < reference:
                # 当前元素插入small
                small.append(s)
            # 当前元素等于基准值
            elif s == reference:
                equal.append(s)
            # 当前元素大于基准值
        	else:
                large.append(s)
            print(small,equal,large)
    # 调用自身，即为递归
    return quick_sort(small) + equal + quick_sort(large)

实用版：

1
2
3
4
5
6
7
8
9
def quick_sort(array):
    if len(array) <= 1:
        return array
    else:
        reference = array[0]
        small = [s for s in array[1:] if s < reference]
        equal = [e for e in array if e == reference]
        large = [l for l in array[1:] if l > reference]
    return quick_sort(small) + equal + quick_sort(large)

直接插入排序

直接插入法是直接排序的典型方法，毫无技术可言

算法思想

将排序数组中的数据逐一插入已排序的子序列中，从而得到一个完整的有序数组

算法步骤

  • 将数组的第一个数据看成一个有序的的子序列
  • 从第二个数据开始，依次与前面的有序子序列进行比较，若待插入数据array[i]大于或等于array[i-1]，则原位插入；若待插入数据array[i]小于数据array[i-1]，则将array[i]临时存在临时变量temp中，将有序序列中大于temp的所有数据都后移一位，然后将temp插入对应的位置
  • 重复步骤(2)

算法分析

时间复杂度：

  • 当数组为正序排列时，比较次数为n-1，移位次数为0，均为最小值，因此时间复杂度为 O(n)
  • 当数组为逆序排列时，每次比较都需要做一次位移，此时时间复杂度为 O(n^2)，是最差情况

空间复杂度：

​ O(1)

算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# 直接插入排序
def inset_sort(array):
    n = len(array)
    # 切记是从1到n-1，前闭后开
    for i in range(1,n):
    	# 如果待插入数据小于前一个数据
        if array[i] < array[i-1]:
            # index为待插入的下标
            index = i
            # 将待插入的数据放在temp中
            temp = array[i]
            # 从i-1循环到0,反向取值，间距为1
            # 前两个参数为区间范围，第三个参数为取值方向和大小
            for j in range(i-1,-1,-1):
                # 如果array[j]大于temp
                if array[j] > temp:
                    # 将array[j]后移一位
                    array[j+1] = array[j]
                    # 更新待插入的下标
                    index = j
                # 如果array[j]小于或等于temp
            	else:
                    # 跳出并结束
                    break
            # 将temp插入有序子数列
            array[index] = temp
       # 如果待插入数据大于前一个数据，则不需要移动
    return array

希尔排序

即shell排序，也叫缩小增量排序，通过将原始列表分解为多个子列表来改进插入排序

算法排序

shell排序摒弃了直接插入排序逐一比较的区别，而是对指定距离(增量d)的元素进行比较，并不断把增量减小到1,直到排序完成

算法步骤

  • 选取增量d = n/2
  • 将排序数组分成d个子序列，然后分别进行直接插入排序
  • 将增量取半，即 d = d/2 = n/2/2
  • 重复步骤(2)和(3)
  • 对整个待排序数组进行直接插入排序

算法分析

似乎希尔排序并不比直接插入排序快多少，但是我们可以注意到它的特点：

  • 当d较大时，分组多，每组记录少，因此直接插入排序快
  • 当d教小时，分组少，每组记录多，但是此时各组记录已经为正序，因此排序比正常的直接插入要快

实际上希尔排序相较于直接排序，主要是优化了待排序数组的初始顺序，使其达到或接近于直接插入排序的最优情况

时间复杂度：

  • 最好的情况下为O(n^1.3)
  • 最差的情况仍然为O(n^2)

算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 希尔排序
def shell_sort(array):
    # 设定初始增量d=n/2
    d = len(array)//2
    # 当增量大于0时执行,如果小于0,则退出循环
    while d>0:
        # i 的取值范围为d到n
        for i in range(d,len(array)):
            # 类似直接插入排序，比较当前值与指定增量的值
            while i>=d and array[i-d]>array[i]:
                # 符号条件则交换
                array[i],array[i-d] = array[i-d],array[i]
                # 取前一个指定增量的值，继续下一个判断
                i -= d
        # 将增量取半,回到while循环
        d = d//2
    return array

简单选择排序

选择排序的思想和简单，每次从待排序数据中选择最小的一个放在最前面，直到将所有数据都遍历完

算法思想

遍历待排序数组并选出其中的最小数据元素，并于第一个元素交换位置，第二小的元素和第二个元素交换位置，直到剩下最后一个数据为最大数据，排序结束

算法步骤

  • 将第一个位置上的元素依次与后面的元素进行比较，若前者大，则交换二者位置
  • 重复步骤（1），比较第二个位置上的元素，然后比较第三个位置上的元素…直到比到倒数第二个元素

算法分析

这个算法被视作在排序算法中最差劲的算法

时间复杂度：

无论时最好的情况还是最差的情况，都需要与所有数据进行遍历，因此时间复杂度始终为 O(n^2)

算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
# 简单选择排序
def select_sort(array):
    # 从0遍历到待排序数组的长度len(array)-1
    for i in range(len(array)-1):
        # smallest为最小值的index，初始默认为当前的i
        smallest = i
        # j为比较index,从当前的index的下一位到数组结束
        for j in range(i+1,len(array)):
            # 如果当前最小值大于当前值
            if array[smallest]>array[j]:
                # 则二者交换位置
                array[smallest],array[j] = array[j],array[smallest]
    return array

堆排序（这个和数据结构相关，我不是太理解）

简单排序只顾着，一次又一次的重新比对，却不对每一次的比较结果进行分析保存，所以导致效率低下，而堆排序加以改进

算法思想

首先需要直到什么是堆，堆是用数组实现的已标号的完全二叉树。接着需要引入小顶堆和大顶堆的思想：

  • 如果父节点的键值均不小于子节点，则为大顶堆：arr[i]>=arr[2*i+1] && arr[i]>=arr[2*i+2]
  • 如果父节点的键值均不大于子节点，则为小顶堆：arr[i]<=arr[2*i+1] && arr[i]<=arr[2*i+2]

也就是说，堆排序实际上就是一次又一次的将待排序数组构造成一个大顶堆，又一次次的将大顶堆的根节点(最大值)和最末尾的元素互换位置，并末尾的元素隔离，直到整个序列变得有序

算法步骤

  • 将待排序数组构建成一个大顶堆（如果降序排列，则使用小顶堆）。为了构建大顶堆，我们需要从从最后一个非叶子节点开始先从上到下，再从左往右进行调整。最后一个非叶子节点的计算公式为 arr.length//2-1
  • 将堆顶元素与末尾元素交换，使最大元素沉至数组末尾
  • 重复步骤（1）和（2），直到整个序列都变得很有序。重新调整数组结构，使其满足大顶堆的结构

算法分析

时间复杂度：

  • 最好的情况是正序，只需要进行 O(n*log_2(n)复杂度的比较操作，而不需要移动
  • 最坏的情况时间复杂度还是O(n*log_2(n)
  • 从上面可以看出待排序数据的原始分布情况堆堆排序的效率影响较少

算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# 堆排序
def heap_sort(array):
    """
    需要注意两点：
    （1）递归思想
    （2）切片思想
    """
    length = len(array)
    # 当数组array的长度为1时，说明只有一个元素
    if length <= 1:
        return array
    # 若存在两个及以上的节点
	else:
        # 调整为大顶堆，按照从下往上从左往右的顺序进行调整
        # 从最后一个非叶子节点开始想前遍历，直到根节点
        for i in range(len(array)//2-1,-1,-1):
            # 当左孩子大于父节点
            if array[2*i+1]>array[i]:
                # 交换位置
                array[2*i+1],array[i] = array[i],array[2*i+1]
            # 如果右孩子存在且大于父节点
            if 2*i+2 <= length-1:
                if array[2*i+2]>array[i]:
                    # 交换位置
                    array[2*i+2],array[i] = array[i],array[2*i+2]
        '''此处省略剩余数组重构过程,对结果无影响'''
        # 将堆顶元素与末尾元素进行交换
        array[0],array[length-1] = array[length-1],array[0]
        # 递归调用heap_sort函数堆前n-1个元素进行堆排序并返回堆排序后的结果
        return heap_sort(array[0:length-1]) + array[length-1:]

归并排序

归并排序是包含归并思想的排序方法，它是分治法的一个应用。分治法即“分而治之”

算法思想

先将原数组分为子序列，一生二，二生四，四生无穷，然后使每个子序列有序，再将两个有序子序列合并为一个有序序列，最终合一

算法步骤

  • 将排序数组一分为二，再将两个子序列一分为二，生成两个新的待排序数组
  • 重复步骤（1），直到待排序数组的长度为1
  • 按原路径将长度为1的两个数合并为一个有序序列，然后一直向前合并，最终得到一个完整的有序序列

算法分析

归并排序十分高效，它的分与合的结构都是完成二叉树，而分和合的二叉树深度均为log_2(n)，而每次分合的时间复杂度为 O(n)，故

时间复杂度：

始终为 O(n*log_2(n))，不论情况好坏

算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# 归并排序
def merge(left,right):
    """
    两个有序子序列的有序合并：
    依次对两个有序列表的最小数进行比较，较小的放入result中
    :param left: 左子序列
    :param right: 右子序列
    :return: 左右子序列所合成的有序序列
    """
    # result: 存好已经排序的数组
    result = []
    # 如果不符合左右子序列长度均大于0,则说明至少其中的一个数组已经无数据了
    while len(left)>0 and len(right)>0:
        # 相等的时候优先把左侧的数放进结果列表，以保证其稳定性
        if left[0] <= right[0]:
            # list.pop(0)为移除并返回数组的第一个值
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    # 跳出while循环后,我们便可以把另一个数组尽数加入result后面
    result += left
    result += right
    return result

def merge_sort(array):
	"""
	无序序列的不断拆分
	每次均由中间位置进行拆分,不断自我递归调用，直到子序列长度为1
	"""
    # 如果拆分后仅有单个元素，则返回该元素而不拆分
    if len(array) == 1:
        return array
    # 如果有两个以上元素，则从中间位置开始拆分
    middle = len(array)//2
    # 拆分后的左侧子串
    array_left = array[:middle]
    # 拆分后的右侧子串
    array_right = array[middle:]
    # 对拆分后的左右子串序列再进行拆分，直到len(arr)=1
    left = merge_sort(array_left)
    right = merge_soort(array_right)
    # 合并已拆分的左右子序列的同时进行排列并返回排列后的结果
    return merge(left,right)

线性时间非比较类排序

计数排序

一种非基于比较的排序算法，通过辅助数组来确定各元素的为最终位置。因为在排序过程中不存在元素之间的比较和交换操作，当待排序数组为整数且数组内数据范围较小时，其优势十分明显

算法思想

对待排序数组中的每一个元素分别进行计数，确定整个数组中小于当前元素的个数，计数完成后便可以按照各计数值将各元素直接存放在已排序的数组中

算法步骤

  • 根据待排序序列中的最大元素和最小元素确定计数数组c的空间大小
  • 统计待排序序列中的每个元素i出现的次数并存入c[i-1]
  • 对c中的所有值进行累加，后者为其前面所有的值的总和
  • 将每个元素放入已排序序列的第c[i]项，每放入一个元素，c[i]便减1
  • 所有的元素都放入或者c[i]均为0之后,排序结束

算法分析

我们可以观察到计数排序的弊端,当最大值与最小值间的差值过大,会使开销增大,性能变差.其次当出现浮点数或其他形式时,也会有问题

时间复杂度:

第一个循环用于记录每个元素出现的次数,复杂度为 O(n)第二个循环用于对计数数组进行累加,复杂度为 O(k),k为申请空间的大小(即差值范围),第三个循环用于反向填充已排序的数列,复杂度为O(n).总结可得,时间复杂度为 O(n+k)

空间复杂度:

由于我们额外申请了一个大小为k的计数数组和一个与待排序数组同样大小的排序空间,所以空间复杂度为 O(n+k)

算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 计数排序
def count_sort(arr):
    # 计算序列的最大值和最小值
    maximum,minimum = max(arr),min(arr)
    # 申请额外的空间作为计数数组,大小为最大值减最小值+1
    countArr = [0 for i in range(maximum-minimum+1)]
    # 申请一个存放已排序序列的等长空间
    finalArr = [0 for i in range(len(arr))]
    # 统计各元素出现的次数,并将统计结果存入计数数组
    for i in arr:
        # 出现一次就加1
        countArr[i-minimum] += 1 	# 注意下标index = data - min
    # 对计数数组进行累加
    for i in range(1,len(countArr)):
        # 从第二个位置开始,每个每个位置的值等于其本身加上前者
        countArr[i] += countArr[i-1]
    # 开始将元素反向填充到最终的数组中
    for i in arr:
        finalArr[countArr[i-minimum]-1] = i
        # 填充了一个就减一
        countArr[i-minimum] -= 1
    return finalArr

桶排序

这是计数排序的改进版本

算法思想

根据元素的特性将集合拆分成为多个值域,我们称之为桶,将同一值域的元素存放在同一个桶内排序使其处于有序状态.如果每个桶是有序的,则由这些桶按顺序构成的集合也必定是有序的

算法步骤

  • 根据待排序序列中元素的分布特征和差值范围，确定映射函数与申请桶的个数
  • 遍历序列，将每个记录放到对应的桶中
  • 选取排序算法，对不为空的桶内部进行排序
  • 把已排序的桶中的元素放回已经清空的原序列中

算法分析

我们可以注意到，桶排序和快速排序与计数排序的相似性。为了加深理解，我们在此进行区分：

  • 快速排序是对两个分区的排序，而桶排序是多个分区
  • 快速排序是原地排序方式，即在数组本身内进行排序，而桶排序则是在申请的额外操作空间进行排序
  • 快速排序中的每个区间仍然是快速排序，而桶排序可以自主选择桶内的排序方式
  • 计数排序的申请空间的跨度是从最小元素到最大元素，受待排序序列的范围的影响很大，而桶排序弱化了这种影响，减少了元素大小不连续时计数排序所存在的空间浪费

这里对于桶排序要抓住两个关键点：元素值域的划分和排序算法的选择

时间复杂度：

映射过程的排序复杂度为 O(n)桶内排序算法的时间复杂度则和选择的排序复杂度相关

空间复杂度：

由于桶排序需要申请额外的空间进行分桶操作，所以空间复杂度为 O(m+n)

算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 桶排序
def bucket_sort(arr):
    maximum,minimum = max(arr),min(arr)
    # 确定桶的个数
    buckets = [[] for i in range(maximum-minimum)//10+1]
    for i in arr:
        # 计算各元素的所属的桶位
        index = (i - minimum)//10
        # list.append()---添加元素
        buckets[index].append(i)
    # 将原数组清空
    arr.clear()
    for i in buckets:
        # 桶内排序---堆排序(可以用别的替代)
        i = heap_sort(i)
        # 将已排序的桶重新放回已经清空的原数组中
        arr.extend(i)
    return arr

基数排序

基数排序是桶排序的扩展，因此又称之为”桶子法”,它是通过键值的部分信息，将要排序的元素分配至”桶”中,以达到排序作用

算法思想

将各元素按位数切割成不同的数字，然后分别根据每个位数的比较结果进行排序

算法步骤

  • 确定待排序序列的最大位数
  • 将所有待排序元素统一为最大数位长度(左补0)
  • 从最低位到最高位分别进行排序
  • 当最高位排序完成后，原数组变成有序数列

算法分析

时间复杂度：

每一轮排序的时间复杂度为 O(n)，而轮数由最大值的位数d决定，因此时间复杂度为 O(d*n)

空间复杂度：

需要额外申请空间k，因此空间复杂度为 O(n+k)

算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 基数排序
def radix_sort(arr):
    maximum = max(arr)	 # 确定待排序数组中的最大位数
    d = 0				# 用d记录最大位数 
    while maximum!=0:
        maximum = maximum//10
        d += 1
    # d轮排序
    for i in range(d):					
        # 因为每一位数字都是0~9，所以建十个桶
        s = [[] for k in range(10)]		 
        for j in arr:
            # 从个位数开始注意进行分桶操作
            s[int(j/(10**i))%10].append(j)
        # 用10个桶回填原数组
        arr = [a for b in s for a in b]
    return arr