排序算法

2019-05-30 本文已影响0人 pubalabala

冒泡排序(优化)

冒泡排序的概念:冒泡排序是一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直至没有反序的记录为止。因为按照该算法，每次比较会将当前未排序的记录序列中最小的关键字移至未排序的记录序列最前（或者将当前未排序的记录序列中最大的关键字移至未排序的记录序列最后），就像冒泡一样，故以此为名。
冒泡排序算法的算法描述如下：
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
冒泡排序的复杂度：
- 时间复杂度 $O(n^{2})$
- 最优时间复杂度 $O(n)$
- 平均时间复杂度 $O(n^{2})$
- 空间复杂度：总共 $O(n)$
*前面的是位置参数 - 传参时只需要参数值对号入座即可
*后面的时命名关键字参数 - 传参是必须书写为"参数名=参数值"格式
好的函数应该是没有副作用的(调用函数不会让函数的调用者收到任何影响)

def bubble_sort(origin_items, comp = lambda x, y: x > y):
    """冒泡排序 - 平方复杂度 - O(N**2)"""
    items = origin_items[:] # 此处优化算法不对原始数据造成影响
    for i in range(1, len(items),):
        swapped = False
        for j in range(0, len(items)-i):
            if comp(items[j], items[j+1]): # 此处解耦比较运算符, 扩大函数适用范围
                items[j], items[j+1] = items[j+1], items[j]
                swapped = True

       # 此处优化为双向排序, 经过此优化后的冒泡排序算法又称为搅拌排序、鸡尾酒排序等
       for j in range(len(items) - i, 0, -1):
             if comp(items[j-1], items[j]):
                 items[j], items[j-1] = items[j-1], items[j]
                 swapped = True
        if not swapped: # 如果某一轮比较全程没有发生交换则终止循环
            break
    return items

归并排序

归并排序的概念:归并排序是创建在归并操作上的一种有效的排序算法，效率为O(n log n)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

归并排序的算法描述如下：

迭代法：
1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针到达序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾
递归法：
原理如下（假设序列共有n个元素）：
1. 将序列每相邻两个数字进行归并操作，形成 {\displaystyle floor(n/2)} floor(n/2)个序列，排序后每个序列包含两个元素
2. 将上述序列再次归并，形成 {\displaystyle floor(n/4)} floor(n/4)个序列，每个序列包含四个元素
3. 重复步骤2，直到所有元素排序完毕
归并排序的复杂度:
- 时间复杂度 $O(nlog{n})$
- 最优时间复杂度 $O(n)$
- 平均时间复杂度 $O(nlog{n})$
- 空间复杂度 $O(n)$

def merge(items1, items2, comp):
    """有序列表合并"""
    items = []
    index1, index2 = 0, 0
    while index1 < len(items1) and index2 < len(items2):
        if comp(items[index1], items2[index2]):
            items.append(items1[index1]
            index1 += 1
        else:
            items.append(items2[index2])
            index2 += 1
    items += items1[index1:]
    items += items2[index2:]
    return items


# 函数的递归调用 - 一个函数如果直接或者简介的调用了自身就成为递归调用
# 写递归调用的函数又两个关键点:
# 1. 收敛条件 - 什么时候可以停止递归
# 2. 递归公式 - 下一轮的调用跟当前轮次的关系
def merge_sort(items, comp=lambda x, y: x <= y):
    """归并排序"""
    if len(items) < 2:
        return items[:]
    mid = len(items) // 2
    left = merge_sort(items[:mid])
    right = merge_sort(items[mid:])
    return merge(left, right, comp)

插入排序

插入排序的概念::是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
插入排序的算法描述如下：
1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5
插入排序复杂度:
- 时间复杂度 $O(n^{2})$
- 最优时间复杂度 $O(n)$
- 平均时间复杂度 $O(n^{2})$
- 空间复杂度总共 $O(n)$

def insert_sort(items):
    for i in range(1, len(items)):
        for j in range(i):
            if items[j] > items[i]:
                items.insert(j, items.pop(i))
                break

# 或者
def insert_sort(items):
    for i in range(1, len(items)):
        temp = items[i]
        for j in range(i, 0, -1):
            if temp < items[j-1]:
                items[j] = items[j-1]
                items[j-1] = temp
            else:
                break

快速排序

import random


# 三数取中
def get_mid(arr, left, right):
    mid = left + ((left-right)>>1)
    if arr[left] < arr[right]:
        if arr[mid] > arr[right]:
            return right
        elif arr[mid] < arr[left]:
            return left
        else:
            return mid
    else:
        if arr[mid] > arr[left]:
            return left
        elif arr[mid] < arr[right]:
            return right
        else:
            return mid


# 挖坑法
def partition1(arr, left, right):
    mid = get_mid(arr, left, right)
    arr[mid], arr[right] = arr[right], arr[mid]
    key = arr[right]
    while left < right:
        while left < right and arr[left] <= key:
            left += 1
        arr[right] = arr[left]
        while left < right and arr[right] >= key:
            right -= 1
        arr[left] = arr[right]
    arr[right] = key
    return right


# 左右指针法
def partition2(arr, left, right):
    mid = get_mid(arr, left, right)
    arr[mid], arr[right] = arr[right], arr[mid]
    key = right
    while left < right:
        while left < right and arr[left] <= arr[key]:
            left += 1
        while left < right and arr[right] >= arr[key]:
            right -= 1
        arr[left],arr[right] = arr[right], arr[left]
    arr[left], arr[key] = arr[key], arr[left]
    return left


# 前后指针法
def partition3(arr, left, right):
    mid = get_mid(arr, left, right)
    arr[right], arr[mid] = arr[mid], arr[right]
    cur = left
    pre = cur - 1
    while cur < right:
        if arr[cur] < arr[right]:
            pre += 1
            if pre != cur:
                arr[pre], arr[cur] = arr[cur], arr[pre]
        cur += 1
    pre += 1
    arr[pre], arr[right] = arr[right], arr[pre]
    return pre


def quick_sort(arr, left, right):
    if left >= right:
        return
    mid = partition1(arr, left, right)
    quick_sort(arr, left, mid-1)
    quick_sort(arr, mid+1, right)


def random_arr(length, min, max):
    arr = []
    for i in range(length):
        arr.append(random.randint(min, max))
    return arr


def main():
    arr = random_arr(100, 0, 10000)
    print(arr)
    quick_sort(arr, 0, len(arr)-1)
    print(arr)


if __name__ == '__main__':
    main()

排序算法

冒泡排序(优化)

归并排序

插入排序

快速排序

猜你喜欢

热点阅读