查找、排序

发表于 | 分类于

一、排序

程序员小吴：https://cxyxiaowu.com/articles/2019/06/11/1560233679033.html

  • 堆选归基 与初始序列无关 ；
    堆选快希 不稳定
  • 快排：填坑法；选第一个值为pivot，根据 pivot 分成左右两部分
  • 拓扑排序运算只能用于：有向无环图【拓扑排序是指将偏序集变为全序集，一个偏序有向图是可以表示流程图的，但是显然，这个有向图一旦出现了环，即表示有顶点自己以自己为先决条件，这是错误的

  • 基数排序：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

  • 1. 快排 O(nlongn)
    pivot partition recursive
    原地排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    def quickSort(arr, left, right):
        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:
            index = partition(arr, left, right)
            quickSort(arr, left, index-1) 
            quickSort(arr, index+1, right)
        return arr

    def partition(arr, left, right):
        pivot = left
        index = pivot+1
        i = index
        while i <= right:
            if arr[i] < arr[pivot]:
                arr[i], arr[index] = arr[index], arr[i]
                index += 1
        return index-1

  • 2. 归并 O(nlongn)
    和选择排序一样，性能不受输入数据影响，O(nlogn)，额外空间

  1. 申请空间，用于存放排序后的序列

  2. 两个指针，分别为两个已排序序列的起始位置

  3. 比较两个指针指向的元素，小的放入合并空间

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    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(left, right)

    def merge(left, right):
        res = []
        while left and right:
            if left[0] <= right[0]:
                res.append(left.pop(0))
            else:
                res.append(right.pop(0))
        if left:
            res += left
        if right:
            res += right
        return res
  • 3. 堆排 O(nlongn)
    堆：完全二叉树，且每个结点值小（大）于左右结点值
    大顶堆：升序排列 ；小顶堆：降序排序
    i结点的父结点下标就为(i-1)/2。i结点的左右子结点下标分别为2*i+1 和 2*i+2
    （注：如果根结点是从1开始，则左右孩子结点分别是2i和2i+1。）

  1. 建堆 H[0…n-1]，构建最大堆

  2. 把堆首（最大值）和堆尾互换

  3. 把堆尺寸缩小 1，调用 shift_down(0),使新数组顶端的数据调整到合适位置

  4. 重复 2，不断出堆，直到堆尺寸为 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
    29
    30
    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

  • 冒泡

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    def bubbleSort(alist):
        n = len(alist)
        for j in range(n-1):
            count = 0   # count == 0 代表没有交换，序列已经有序
            for i in range(0, n-1-j):
                if alist[i] > alist[i + 1]:
                    alist[i], alist[i + 1] = alist[i + 1], alist[i]
                    count += 1
            if 0 == count:
                break
        return alist

  • 选择
    遍历找到最小，与数组第一个交换，次小，放到第二个，好坏都是 N2

    1
    2
    3
    4
    5
    6
    7
    8
    def selectSort(arr):
        for i in range(0, len(arr) - 1):
            min_index = i    # 记录最小值索引
            for j in range(i+1, len(arr)):
                if arr[j] < arr[min_index]:
                    min_index = j
            if i != min_index:  # i 不是最小数时，将 i 和最小数交换
                alist[min_index], alist[i] = alist[i], alist[min_index]

  • 插入
    一次一次从左到右，小到大调换，不断扩大有序部分

    1
    2
    3
    4
    5
    6
    7
    8
    9
    def insertionSort(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

  • 希尔

    1. 插入排序的改进版本，但是非稳定排序
    2. 对几乎已经排好序的数据，效率高
    3. 定义一个增量序列 Dm > Dm-1 > … > D1 = 1，对每个 Dk-间隔排序
      每次在 Dk-1-间隔排序后，仍是 Dk 有序的
      但，若增量不互质，后面小的增量可能根本不起作用
    4. 适合几万量级