数据结构 - 排序算法

Posted on | Post modified: | In
Words count in article: 4.7k

本系列为数据结构学习笔记(待汇总)。

1 排序

假设含有n个记录的序列为${r_1,r_2,…,r_n}$，其相应的关键字分别为$(k_1,k_2,…,k_n)$，需确定$1,2,…,n$的一种排列$p_1,p_2,…,p_n$,使其相应的关键字满足$K_{p1} \leq k_{p2} \leq … \leq k_{pn}$关系，即使得序列成为一个按关键字有序的序列$r_{p1},r_{p2},…,r_{pn}$，这样的操作就称为排序。

1.1 排序的稳定性

假设$k_i = k_j (1 \leq i \leq n，1 \leq j \leq n，i \neq j)$，且在排序前的序列中$r_i$领先于$r_j$（即$i＜j$）。如果排序后$r_i$仍领先于$r_j$，则称所用的排序方法是稳定的；反之，若可能使得排序后的序列中$r_j$领先$r_i$，则称所用的排序方法是不稳定的。

1.2 内排序与外排序

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

对于内排序来说，排序算法的性能主要受3个方面影响：

  1. 时间性能：内排序中主要进行两种操作，比较和移动。高效率的内排序算法应该是具有尽可能少的关键字比较次数和尽可能少的记录移动次数。
  2. 辅助空间：辅助存储空间是除了存放待排序所占用的存储空间之外，执行算法所需要的其他存储空间。
  3. 算法的复杂性：算法本身的复杂度，而不是指算法的时间复杂度。

内排序按主要操作分类：
插入排序
交换排序
选择排序
归并排序

排序按复杂度分类
简单算法：冒泡排序，简单选择排序，直接插入排序
改进算法：希尔排序，堆排序，归并排序，快速排序

2 常见排序算法

2.1 冒泡排序

冒泡排序是一种交换排序，基本思想是：两两比较相邻记录的关键字，如果反序则交换，知道没有反序的记录为止。

2.1.1 冒泡排序初级版

mark
让每一个关键字，都和他后面的每一个关键字比较，如果大则交换，这样第一位置的关键字在一次循环后一定变成最小值。

1
2
3
4
5
6
7
8
9
def BubbleSort0(L):
    for i in range(len(L)):
        for j in range(i+1,len(L)):
            if L[i]>L[j]:
                L[i],L[j] = L[j],L[i]
    return L
if __name__ == '__main__':
    result = BubbleSort0([9,1,5,8,3,7,4,6,2])
    print(result)

2.1.2 冒泡排序正宗版

mark

1
2
3
4
5
6
7
8
9
def BubbleSort(L):
    for i in range(len(L)):
        for j in range(len(L)-2,i-1,-1):
            if L[j] > L[j+1]:
                L[j],L[j+1]=L[j+1],L[j]
    return L
if __name__ == '__main__':
    result = BubbleSort([9,1,5,8,3,7,4,6,2])
    print(result)

2.1.3 冒泡排序优化

mark
当i=2时，我们已经对9与8,8与7，。。。，3与2作了比较，没有任何数据交换，说明此序列已经有序，不需要再继续后面的循环判断工作了。增加标记变量flag来实现这一算法的改进。

1
2
3
4
5
6
7
8
9
10
11
12
13
def BubbleSort(L):
    flag = True
    for i in range(len(L)):
        if flag:
            flag = False
            for j in range(len(L)-2,i-1,-1):
                if L[j] > L[j+1]:
                    L[j],L[j+1]=L[j+1],L[j]
                    flag = True
    return L
if __name__ == '__main__':
    result = BubbleSort([9,1,5,8,3,7,4,6,2])
    print(result)

2.1.4 冒泡排序的算法复杂度：

最好情况：要排序的表本身就是有序的，需要$n-1$次比较，没有数据交换，时间复杂度为$O(n)$。
最坏情况：待排序表示逆序的情况，需要比较$1+2+3+…+(n-1) = n(n-1)/2$次，并做等数量级的记录移动，总时间复杂度为$O(n^2)$。
冒泡排序是稳定的。

2.2 简单选择排序

通过$n-i$次关键字间的比较，从$n-i+1$个记录中选出关键字最小的记录，并和第$i,(1≤i≤n)$个记录交换之。

1
2
3
4
5
6
7
8
9
10
11
12
def SelectSort(L):
    for i in range(len(L)):
        min = i
        for j in range(i+1,len(L)):
            if L[j] < L[min]:
                min = j
        if min != i:
            L[i],L[min] = L[min],L[i]
    return L
if __name__ == '__main__':
    result = SelectSort([9,1,5,8,3,7,4,6,2])
    print(result)

2.2.1 简单选择排序复杂度分析

简单选择排序最大的特点是交换移动数据次数相当少。
无论最好最差的情况，其比较次数都是一样多，第$i$躺排序需要进行$n-i$次关键字的比较，需要比较$(n-1)+(n-2)+…+1 = n(n-1)/2$次;
而对于交换次数而言，最好的时候交换0次，最坏时候交换n-1次。总的时间复杂度仍为$O(n^2)$。
性能略优于冒泡排序，简单选择排序是稳定的。

2.3 直接插入排序

直接插入排序的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。

1
2
3
4
5
6
7
8
9
10
11
12
13
def InsertSort(L):
    for i in range(1,len(L)):
        if L[i] < L[i-1]:
            temp = L[i]#设置哨兵
            k = i
            while temp < L[k-1] and k >= 1:
                L[k] = L[k-1]#记录后移
                k -= 1
            L[k] = temp#插入到正确位置
    return L
if __name__ == '__main__':
    result = InsertSort([9,1,5,8,3,7,4,6,2])
    print(result)

2.3.1 直接插入排序复杂度分析

  • 空间复杂度：只需要一个记录的辅助空间，$O(1)$
  • 最好时间复杂度：待排序表是有序时，n-1次比较，0次移动，复杂度为$O(n)$
  • 最坏时间复杂度：待排序表示逆序时，需要比较$2+3+…+n=(n+2)(n-1)/2$次，移动$(n+4)(n-1)/2$次。
  • 平均比较和移动次数$n^2/4$次。总的时间复杂度为$O(n^2)$，直接插入排序法比冒泡和简单选择排序的性能要好一些。
  • 直接插入排序是稳定的。

2.4 希尔排序

希尔排序算法是突破$O(n^2)$这个时间复杂度的第一批算法。
采用跳跃分割的策略：将相距某个“增量”的记录组成一个字序列，这样才能保证在子序列内分别进行插入排序后得到的结果就是基本有序而不是局部有序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def ShellSort(L):
    increment = len(L) // 2
    while increment > 0:
        for i in range(increment,len(L)):
                temp = L[i]
                k = i - increment
                while temp < L[k] and k >= 0:
                    L[k+increment] = L[k]
                    k -= increment
                L[k+increment] = temp
        increment = increment // 2
    return L
if __name__ == '__main__':
    result = ShellSort([9,1,5,8,3,7,4,6,2])
    print(result)

2.4.1 希尔排序复杂度分析

增量的选取很关键，迄今为止还没有人找到一种最好的增量序列。
增量序列的最后一个增量值必须等于1才行，由于记录是跳跃式的移动，希尔排序并不是一种稳定的算法。
时间复杂度为$O(n^{3/2})$。优于直接排序的$O(n^2)$。

2.5 堆排序

堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
mark
如果按照层序遍历的方式给结点从1进行编号，则结点之间满足以下关系：
mark

2.5.1 堆排序算法

堆排序就是利用堆（假设利用大顶堆求升序）进行排序的方法，他的基本思想是：将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的$n-1$个序列重新构造成一个堆，这样就会得到n个元素中的次小值。如此反复执行，便能得到一个有序序列了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def HeapSort(L):
    for i in range(len(L)//2,-1,-1):
        HeapAdjust(L,i,len(L))
    for j in range(1,len(L))[::-1]:
        L[j],L[0] = L[0],L[j]
        HeapAdjust(L,0,j)
    return L
def HeapAdjust(L,parent,length):
    temp = L[parent]
    child  = 2*parent+1
    while child < length:
        if child+1<length and L[child]<L[child+1]:
            child += 1
        if temp >= L[child]:
            break
        L[parent] = L[child]
        parent = child
        child = 2*parent+1
    L[parent] = temp

if __name__ == '__main__':
    result = HeapSort([9,1,5,8,3,7,4,6,2])
    print(result)

2.5.2 堆排序复杂度分析

运行时间主要消耗在初始构建堆和重建堆的反复筛选。

  • 构建堆的时间复杂度为$O(n)$
  • 重建堆的时间复杂度为$O(nlogn)$
  • 总的时间复杂度为$O(nlogn)$

空间复杂度，只需要一个用来交换的暂存单元，$O(1)$。

堆排序是不稳定的。

2.6 归并排序

归并排序的原理是假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两合并，得到[n//2]个长度为2或1的有序子序列；再两两合并，…，如此重复，直至得到一个长度为n的有序序列为止，这种方法称为2路归并排序。

mark

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 MergeSort(L):
    temp = [0]*len(L)
    MSort(L,temp,0,len(L)-1)
    return L
def MSort(L,temp,left,right):
    if left >= right:
        return
    mid = (left+right)//2
    MSort(L,temp,left,mid)
    MSort(L,temp,mid+1,right)
    Merge(L,temp,left,mid,right)

def Merge(L,temp,left,mid,right):
    l,r = left,mid+1
    k = 0
    while l <= mid and r <= right:
        if L[l]<L[r]:
            temp[k] = L[l]
            l += 1
        else:
            temp[k] = L[r]
            r += 1
        k += 1
    while l <= mid:
        temp[k] = L[l]
        l+=1
        k+=1
    while r <= right:
        temp[k] = L[r]
        r += 1
        k += 1
    k = 0
    while left <= right:
        L[left] = temp[k]
        left += 1
        k += 1
        
if __name__ == '__main__':
    result = MergeSort([9,1,5,8,3,7,4,6,2])
    print(result)

2.6.1 归并排序复杂度分析

一趟归并需要将待排序序列中的所有记录扫描一遍，耗费$O(n)$时间，而由完全二叉树的深度可知，整个归并排序需要进行$[log2^n]$次，因此总的时间复杂度为$O(nlogn)$，而且这是归并排序算法中最好、最坏、平均的时间性能。
由于归并排序在归并过程中需要与原始记录序列同样数量的存储空间存放归并结果以及递归时深度为$log2^n$的栈空间，因此空间复杂度为$O(n+logn)$。
由于Merge函数中有$if L[l]<L[r]$语句，说明需要两两比较，不存在跳跃，因此归并排序是一种稳定的排序算法。
归并排序是一种比较占用内存，但效率高且稳定的算法。

2.7 快速排序

快速排序的基本思想是：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可以分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def QuickSort(L):
    QSort(L,0,len(L)-1)
    return L
def QSort(L,low,high):
    if low <high:
        pivot = Partition(L,low,high)
        QSort(L,low,pivot-1)
        QSort(L,pivot+1,high)
def Partition(L,low,high):
    pivotkey = L[low]
    while low<high:
        while low<high and L[high]>=pivotkey:
            high -= 1
        L[low],L[high] = L[high],L[low]
        while low<high and L[low]<=pivotkey:
            low += 1
        L[low], L[high] = L[high], L[low]
    return low

if __name__ == '__main__':
    result = QuickSort([9,1,5,8,3,7,4,6,2])
    print(result)

Partition 函数要做的，就是先选取当中的一个关键字，比如选择第一个关键字，然后想尽办法将它放到一个位置，使得它左边的值都比它小，右边的值比它大，我们将这样的关键字称为枢轴( pivot) 。

2.7.1 快速排序复杂度分析

快速排序的时间性能取决于快速排序递归的深度。
mark

在最优情况下,Partition每次划分都很均匀，如果排序n个关键字，其递归树的深度就为$[logn]+1$，仅需递归$logn$次，需要时间为$T(n)$的话，第一次Partition应该是对整个数组扫描一遍，做n次比较。然后获得的枢轴将数组一份为二，那么各自还需要$T(n/2)$的时间。

  • 在最优的情况下，快速排序算法的时间复杂度为$O(nlogn) $。
  • 最坏时间复杂度为$O(n^2)$。

空间复杂度主要是递归造成的栈空间的使用:

  • 最好情况，递归树的深度为$logn$ ，其空间复杂度也就为$O(logn)$
  • 最坏情况，需要进行$n - 1$ 递归调用，其空间复杂度为$O(n)$
  • 平均情况， 空间复杂度也为$O (logn) $。
  • 由于关键字的比较和交换是跳跃进行的，因此，快速排序是一种不稳定的排序方法。

2.7.2 快速排序优化

2.7.2.1 优化选取枢轴

三数取中：即取三个关键字先进行排序，将中间数作为枢轴， 一般是取左端、右端和中间三个数。
三数取中对小数组来说有很大的概率选择到一个比较好的pivotkey ，

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 QuickSort(L):
    temp = [0]*len(L)
    QSort(L,0,len(L)-1)
    return L
def QSort(L,low,high):
    if low <high:
        pivot = Partition(L,low,high)
        QSort(L,low,pivot-1)
        QSort(L,pivot+1,high)
def Partition(L,low,high):
    m= low+(high-low)//2
    if L[low]>L[high]:
        L[low], L[high] = L[high], L[low]
    if L[m]>L[high]:
        L[m], L[high] = L[high], L[m]
    if L[m]>L[low]:
        L[m], L[low] = L[low], L[m]
    pivotkey = L[low]
    while low<high:
        while low<high and L[high]>=pivotkey:
            high -= 1
        L[low],L[high] = L[high],L[low]
        while low<high and L[low]<=pivotkey:
            low += 1
        L[low], L[high] = L[high], L[low]
    return low

if __name__ == '__main__':
    result = QuickSort([9,1,5,8,3,7,4,6,2])
    print(result)

2.7.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
def QuickSort(L):
    temp = [0]*len(L)
    QSort(L,0,len(L)-1)
    return L
def QSort(L,low,high):
    if low <high:
        pivot = Partition(L,low,high)
        QSort(L,low,pivot-1)
        QSort(L,pivot+1,high)
def Partition(L,low,high):
    m= low+(high-low)//2
    if L[low]>L[high]:
        L[low], L[high] = L[high], L[low]
    if L[m]>L[high]:
        L[m], L[high] = L[high], L[m]
    if L[m]>L[low]:
        L[m], L[low] = L[low], L[m]
    pivotkey = L[low]
    temp = pivotkey
    while low<high:
        while low<high and L[high]>=pivotkey:
            high -= 1
        L[low] = L[high]
        while low<high and L[low]<=pivotkey:
            low += 1
        L[high] = L[low]
    L[low] = temp
    return low

if __name__ == '__main__':
    result = QuickSort([9,1,5,8,3,7,4,6,2])
    print(result)

2.7.2.3 优化小数组时的排序方案

2.7.2.4 优化递归操作

2.8 桶排序

使用空间换时间，首先统计出数组中元素的频次。接着，将数组中的元素按照出现频次进行分组，即出现频次为 i 的元素存放在第 i 个桶。最后，从桶中逆序取出前 k 个元素；
桶排序使用Hashmap散列表。

2.8.1 桶排序复杂度分析

假设有n个数字，有m个桶，如果数字是平均分布的，则每个桶里面平均有$n/m$个数字。如果 对每个桶中的数字采用快速排序，那么整个算法的复杂度是
$O(n + m n/mlog(n/m)) = O(n + nlogn - nlogm) $

当m接近n的时候，桶排序复杂度接近$O(n)$。
前面说的几大排序算法 ，大部分时间复杂度都是$O(n^2)$，也有部分排序算法时间复杂度是$O(nlogn)$。而桶式排序却能实现$O(n)$的时间复杂度。但桶排序的缺点是：

  • 首先是空间复杂度比较高，需要的额外开销大。排序有两个数组的空间开销，一个存放待排序数组，一个就是所谓的桶，比如待排序值是从0到m-1，那就需要m个桶，这个桶数组就要至少m个空间。
  • 其次待排序的元素都要在一定的范围内。
  • 桶式排序是一种分配排序。分配排序的特点是不需要进行关键码的比较，但前提是要知道待排序列的一些具体情况。

参考

2.8.2 桶排序实现

桶排序求前K个高频元素

题目描述
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

  • 示例 1:

    输入: nums = [1,1,1,2,2,3], k = 2
    输出: [1,2]

  • 示例 2:

    输入: nums = [1], k = 1
    输出: [1]

  • 说明：

    你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
    你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。

解题思路

使用桶排序算法

  • 首先使用散列表统计数组中元素出现的频次；
  • 接着新建len(nums)+1个桶，用于保存出现次数对应的元素；
  • 最后，从逆序桶中取出前k个元素。
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
class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        if len(nums)<k:
            return []
        Dict = {}
        for x in nums:
            Dict[x] = Dict.get(x,0)+1
        bucket = [[] for _ in range(len(nums)+1)]
        for key, val in Dict.items():
            bucket[val].append(key)
        res = []
        for i in range(len(nums),-1,-1):
            if bucket[i]:
                res.extend(bucket[i])
            if len(res)>=k:
                break
        return res

if __name__ == '__main__':
    result = Solution().topKFrequent([1,1,1,2,2,3], 2)
    print(result)

根据字符出现频率排序

题目描述
给定一个字符串，请将字符串里的字符按照出现的频率降序排列。

  • 示例 1:

    输入:”tree”
    输出: “eert”
    解释: ‘e’出现两次，’r’和’t’都只出现一次。因此’e’必须出现在’r’和’t’之前。此外，”eetr”也是一个有效的答案。

  • 示例 2:

    输入:”cccaaa”
    输出:”cccaaa”
    解释:’c’和’a’都出现三次。此外，”aaaccc”也是有效的答案。注意”cacaca”是不正确的，因为相同的字母必须放在一起。

  • 示例 3:

    输入:”Aabb”
    输出:”bbAa”
    解释:此外，”bbaA”也是一个有效的答案，但”Aabb”是不正确的。注意’A’和’a’被认为是两种不同的字符。

解题思路

桶排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def frequencySort(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s)==0:
            return ''
        Dict = {}
        for x in s:
            Dict[x] = Dict.get(x,0)+1
        bucket = ['' for _ in range(len(s)+1)]
        for key,val in Dict.items():
            bucket[val] += val * key
        res = ''
        for i in range(len(s),-1,-1):
            if bucket[i]:
                res += bucket[i]
        return res

if __name__ == '__main__':
    result = Solution().frequencySort('tree')
    print(result)

3 总结

mark

参考文献：
程杰. 大话数据结构

Donate comment here
------------The End------------
0%