Posted on | In

算法性能分析

  • 分类

    • 内排序：带排序的记录全部保存在内存中
    • 外排序：针对外存（磁盘等）数据的排序

  • 基本操作：

    • 比较关键码的操作，通过这种操作确定数据的顺序关系
    • 移动数据记录的操作，用于调整记录的位置顺序

  • 基于关键码的比较的排序问题，时间复杂度是O(n log n)，也就是说任何算法都不能优于O(n log n)

  • 稳定的排序算法：对于待排序的序列里任何一对排序码相同的记录Ri和Rj，在排序后后的序列中Ri和Rj的前后顺序不变。也就是说，稳定的排序算法能够维持序列中所有排序码相同记录的相对位置。

插入排序

思想：
1.对一段连续表进行排序时，可以把序列看为两段，左边为排好序的，右边为待排序的。
2.每次仅考虑右边序列的第一个元素在左边序列的插入位置。

1
2
3
4
5
6
7
8
def insert_sort(lst):
    for i in range(1, len(lst)):  # 开始时片段[0:1]已排好序
        x = lst[i]
        j = i
        while j > 0 and lst[j-1] > x:
            lst[j] = lst[j-1]  # 反序逐个后移元素，确定插入位置
            j -= 1
        lst[j] = x
  • 空间复杂度：O(1)，计算中只用了两个辅助变量
  • 时间复杂度：这个算法具有适应性。
    • 最坏情况：O(n^2)，关键码的比较次数由内层循环while决定，为n-1次，while循环总执行n(n-1)/2次，记录移动次数包括内层循环外边的两次和循环中的一些次，为2(n-1)次，最终总共2(n-1)+n(n-1)/2次。
    • 最好情况：O(n)
    • 平均情况：O(n^2)，一个元素可能插入一排序序列里的任何位置，假设插入个位置的概率相等，内层循环每次的迭代次数就是j/2，求和后就是n*(n-1)/4次。

选择排序

思想：
1.维护需要考虑的所有记录中最小的i个记录的已排序序列；
2.每次从剩余未排序的记录中选取关键码最小的记录，将其放在已排序序列记录的后面，作为序列的第i+1个记录；
3.执行到尚未排序序列里只有一个元素时，最后一个元素必然是整个序列中最大的，只需将其放在已排序的记录后排序完成。（这里以升序为例）

1
2
3
4
5
6
7
8
def select_sort(lst):
    for i in range(len(lst)-1):  # 只需循环len(lst)-1次
        k = i
        for j in range(i, len(lst)):  # k是已知最小元素的位置
            if lst[j] < lst[k]:
                k = j
        if i != k:  # lst[k]是确定的最小元素，检查是否需要交换
            lst[i], lst[k] = lst[k], lst[i]
  • 空间复杂度：O(1)，计算中只用了几个辅助变量
  • 时间复杂度：两个for循环按固定方式重复执行固定次，比较的次数总是1+2+3+…=n(n-1)/2。移动次数为2(n-1)次。此算法没有适应性。
    • 最坏情况：O(n^2)
    • 最好情况：O(n^2)
    • 平均情况：O(n^2)

交换排序（又名起泡排序）

思想：
1.一个序列中的记录没排好序，那么其中一定有逆序存在。
2.通过不断减少序列中的逆序，最终得到排序序列。
基本操作就是发现相邻的逆序对时就交换他们，通过反复比较和交换，最终完成整个序列的排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def bubble_sort(lst):
    for i in range(len(lst)):
        for j in range(1, len(lst)-i):
            if lst[j-1] > lst[j]:
                lst[j-1], lst[j] = lst[j], lst[j-1]


# 改进后（当序列中没有逆序对时，立刻结束循环）
 def bubble_sort(lst):
    for i in range(len(lst)):
        found = False
        for j in range(1, len(lst)-i):
            if lst[j-1] > lst[j]:
                lst[j-1], lst[j] = lst[j], lst[j-1]
                found = True
        if not found:
            break
  • 空间复杂度：O(1)，计算中只用了几个辅助变量
  • 时间复杂度：此算法没有适应性。改进后的算法具有适应性。
    • 最坏情况：O(n^2)
    • 最好情况：O(n^2)
    • 平均情况：改进后的为 O(n)

快速排序

思想（基本过程）：
1.选择一种标准，把被排序列中的记录按某种标准分为大小两组，较小一组的记录应该排在前面
2.采用同样的方式，递归的分别划分得到这两组记录，并继续递归地划分下去
3.划分得到越来越小的组，直到每个记录组中最多包含一个记录时，整个序列的排序就完成了。
（一次）划分的实现：
取出第一个记录作为标准，设其为R，已知的小记录积累在左边，大记录积累在右边，中间是尚未检查的记录。取出记录R使表左边出现了一个空位。这时从右端开始检查，就可以利用这个空位，把发现的第一个小记录（小于R的记录）移到左边。这一迁移操作也导致右边留下一个空位，可供存放在左边发现的一个大记录。
算法：
1.利用两个下标变量i和j，其初值分别是序列中第一个和最后一个记录的位置。然后取出第一个和记录R，设其排序码为K，作为划分标准。
2.交替执行下面两套操作：
2.1.从右向左逐一检查j一边的记录，检查中j值不断减一，直至找到第一个关键字小于K的记录，将其存入i所指的空位。注意，移动记录后位置j变成空位，i值加一后只想下一需要检查的记录。
2.2.从左向右逐一检查i一边的记录，检查i值不断加一，直至找到第一个关键字大于K的记录并将其存入j所指的空位。转做上面操作。
3.重复交替上述两套操作，直到i不再小于j为止。由于第一种操作中j值不断减小，第二种操作中i值不断增大，划分一定能完成。
一次划分完成后对两边子序列按照同样方式递归处理。快速排序算法的执行形成了一种二叉树形式的递归调用。

你想输入的替代文字

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(lst):
    qsort_rec(lst, 0, len(lst)-1)


def qsort_rec(lst, l, r):
    if l >= r:  # 分段无记录或只有一个记录
        return
    i = l
    j = r
    pivot = lst[i]  # lst[i] 是初始空位
    while i < j:  # 找pivot的最终位置
        while i < j and lst[j] >= pivot:
            j -= 1  # 用j向左扫描找小于pivot的记录
        if i < j:
            lst[i] = lst[j]
            i += 1  # 小记录移到左边
        while i < j and lst[i] <= pivot:
            i += 1  # 用i向右扫描找大于pivot的记录
        if i < j:
            lst[j] = lst[i]
            j -= 1  # 大记录移到右边
    lst[i] = pivot  # 将pivot存入其最终位置
    qsort_rec(lst, l, i-1)  # 递归处理左半区间
    qsort_rec(lst, i+1, r)  # 递归处理右半区间
  • 空间复杂度：最坏情况O(n)，与递归深度有关
  • 时间复杂度：
    • 最坏情况：O(n^2)
    • 平均情况：O(n log n)

另外一种简单实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def quick_sort(lst):
    def qsort(lst, begin, end):
        if begin >= end:
            return
        pivot = lst[begin]
        i = begin
        for j in range(begin+1, end+1):
            if lst[j] < pivot:  # 发现一个小元素
                i += 1
                lst[i], lst[j] = lst[j], lst[i]  # 小元素换位
        lst[begin], lst[i] = lst[i], lst[begin]  # 枢纽元换位
        qsort(lst, begin, i-1)
        qsort(lst, i+1, end)

    qsort(lst, 0, len(lst)-1)

归并排序

归并是一种典型的序列操作，其工作是把两个或更多有序序列合并为一个有序序列。
思想：
1.初始时，把待排序序列中的n个记录看成n个有序子序列（因为一个记录的序列总是排好序的），每个子序列的长度均为1
2.把当时序列组里的有序子序列两两归并，完成一遍后序列组里的排序序列个数减半，每个子序列的长度加倍
3.对加长的有序子序列重复上面的操作，最终得到一个长度为n的有序序列
这种方法为二路归并法，也可使用多路归并法。
操作：
1.最下层：实现表中相邻的一对有序序列的归并操作，将归并的结果存入另一个顺序表里的相同位置
2.中间层：基于操作1（一对序列的归并操作），实现对整个表里顺序各对有序序列的归并，完成一遍归并，各对序列的归并结果顺序存入另一个表里的相同位置分段
3.最高层：在两个顺序表之间往复执行操作2，完成一遍归并后交换两个表的地位，然后再重复操作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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def merge(lfrom, lto, low, mid, high):
    i, j, k = low, mid, low
    while i < mid and j < high:  # 反复复制两分段首记录中较小的
        if lfrom[i] <= lfrom[j]:
            lto[k] = lfrom[i]
            i += 1
        else:
            lto[k] = lfrom[j]
            j += 1
        k += 1
    while i < mid:  # 复制第一段剩余记录
        lto[k] = lfrom[i]
        i += 1
        k += 1
    while j < high:  # 复制第二段剩余记录
        lto[k] = lfrom[j]
        j += 1
        k += 1


def merge_pass(lfrom, lto, llen, slen):
    i = 0
    while i + 2 * slen < llen:  # 归并长slen的两段
        merge(lfrom, lto, i, i + slen, i + 2 * slen)
        i += 2
    if i + slen < llen:  # 剩下的两段，后段长度小于slen
        merge(lfrom, lto, i, i + slen, llen)
    else:  # 只剩下一段，复制到表lto
        for j in range(i, llen):
            lto[j] = lfrom[j]


def merge_sort(lst):
    slen, llen = 1, len(lst)
    templst = [None] * llen
    while slen < llen:
        merge_pass(lst, templst, llen, slen)
        slen *= 2
        merge_pass(templst, lst, llen, slen)  # 结果存回原位
        slen *= 2
  • 空间复杂度：O(n)
  • 时间复杂度：O(n log n)，有序子序列的长度将为2^k，完成整个排序需要做的归并遍数不会多于log 2 ^n + 1，总的比较次数和移动次数都为O(n log n)

蒂姆排序

Python中的内置函数sort
蒂姆排序是一种基于归并技术的稳定排序算法，结合了归并排序和插入排序技术，该算法具有适应性。
时间复杂度：最坏情况是O(n log n)，
空间复杂度：最坏情况是O(n)，最坏情况下需要n/2各工作空间

几种排序的比较

排序算法 最坏情况时间复杂度 平均情况时间复杂度 最好情况时间复杂度 空间复杂度 稳定性 适应性
简单插入排序 O(n^2) O(n^2) O(n) O(1) 是 是
二分插入排序 O(n^2) O(n^2) O(n log n) O(1) 是 是
表插入排序 O(n^2) O(n^2) O(n) O(1) 是 是
直接选择排序 O(n^2) O(n^2) O(n^2) O(1) 否 否
堆选择排序 O(n log n) O(n log n) O(n log n) O(1) 否 否
起泡排序 O(n^2) O(n^2) O(n) O(1) 是 是
快速排序 O(n^2) O(n log n) O(n log n) O(log n) 否 否
归并排序 O(n log n) O(n log n) O(n log n) O(n) 是 否
蒂姆排序(sort函数) O(n log n) O(n log n) O(n) O(n) 是 是

Posted on

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment