menu Chancel's Blog
rss_feed lightbulb_outline

烂熟于心的基础排序算法

warning 这篇文章距离上次更新于561天前,文中部分信息可能已失效,请自行甄别无效内容。

工作之后实在是很少使用排序算法了(拧螺丝拧螺丝),在这里整理下常见的排序算法,熟练熟练,其实这些排序算法都应该要烂熟于心的

概要

算法概览

名称 稳定程度 最好时间复杂度 最坏时间复杂度 平均时间复杂度 空间复杂度
冒泡排序 稳定 O(n) O(n^2) O(n^2) O(1)
插入排序 稳定 O(n) O(n^2) O(n^2) O(1)
希尔排序
(Diminishing Increment Sort)
不稳定 O(n^1.3 / / O(1)
快速排序 不稳定 O(nlogn) O(n^2) O(nlogn) O(nlog^2n)
选择排序 不稳定 O(n^2) O(n^2) O(n^2) O(1)
计数排序 稳定 / / O(n+k) O(n+k)

算法概念

  • 算法稳定性 : 算法稳定性是指对于待排序列中相同项的原来次序不能被算法改变则称该算法稳定

  • 时间复杂度 : 在计算机科学中,算法的时间复杂度(Time complexity)是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况.

  • 空间复杂度 : 空间复杂度是指计算机科学领域完成一个算法所需要占用的存储空间,一般是输入参数的函数。它是算法优劣的重要度量指针,一般来说,空间复杂度越小,算法越好。

算法说明

  • 冒泡排序 : 冒泡排序(英语:Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。

  • 插入排序 : 插入排序(英语:Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

  • 希尔排序 : 希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

  • 快速排序 : 快速排序(英语:Quicksort),又称划分交换排序(partition-exchange sort),简称快排,一种排序算法,最早由东尼·霍尔提出。在平均状况下,排序n个项目要 O(nlogn)(大O符号)次比较。在最坏状况下则需要 O(n^2)次比较,但这种状况并不常见。事实上,快速排序O(nlogn)通常明显比其他算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地达成。

  • 选择排序 : 选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

  • 归并排序 : 归并排序(英语:Merge sort,或mergesort),是创建在归并操作上的一种有效的排序算法,效率为O(nlogn)(大O符号)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。

  • 计数排序 : 计数排序是一个非基于比较的排序算法,该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时,它的复杂度为Ο(n+k)(其中k是整数的范围),快于任何比较排序算法。 [1-2] 当然这是一种牺牲空间换取时间的做法,而且当O(k)>O(nlog(n))的时候其效率反而不如基于比较的排序(基于比较的排序的时间复杂度在理论上的下限是O(nlog(n)), 如归并排序,堆排序)

实现

以下代码实现均基于Python3.6版本

import random


'''
    冒泡排序
    1. 循环数组,从左向右开始,比较A1与A2的值,如果A1>A2,则交换A1与A2的位置,再比较A2与A3的大小,如A2>A3..
    2. 以此类推,第一次循环结束时最大的数字已经在最右边,循环n-1次,即排序结束
'''


def bubble_sort(sort_list):
    bubble_list_length = len(sort_list)
    while bubble_list_length > 0:
        for _i in range(0, bubble_list_length-1):
            if sort_list[_i] > sort_list[_i + 1]:
                sort_list[_i], sort_list[_i +
                                         1] = sort_list[_i+1], sort_list[_i]
        bubble_list_length -= 1
    return sort_list


'''
    插入排序
    1. 获取数组长度n,循环range(1,n),获得A0,A1,比较A0,A1大小并交换位置
    2. 第二次循环,获得A0,A1,A2,比较A0,A1,A2,从右往左比较交换位置,以此类推
'''


def insert_sort(sort_list):
    length = len(sort_list)
    for i in range(1, length):
        for j in range(i, 0, -1):
            if sort_list[j] < sort_list[j-1]:
                sort_list[j], sort_list[j-1] = sort_list[j-1], sort_list[j]
    return sort_list


'''
    希尔排序
    1. 改良版插入排序,基本等同于插入排序的分组
'''


def diminishing_increment_sort(sort_list):
    length = len(sort_list)
    h = 1
    while h < length/3:
        h = 3*h+1
    while h >= 1:
        for i in range(h, length):
            j = i
            while j >= h and sort_list[j] < sort_list[j-h]:
                sort_list[j], sort_list[j-h] = sort_list[j-h], sort_list[j]
                j -= h
        h = h//3
    return sort_list


'''
    快速排序
    1. 取任意一个数作为基准数(第一个/倒数第一均可),并在源数组中删除该数
    2. 建立两个新数组,分别为左数组和右数组
    3. 循环源数组,将每一个数与基准数进行比较,较小的归入左数组,较大的归入右数组
    4. 递归调用自身,将左数组跟右数组递归调用至数组大小小于2,将所有数组合并即可
'''


def quick_sort(sort_list):
    if len(sort_list) > 2:
        mid = sort_list[0]
        sort_list.remove(mid)
        left_list = []
        right_list = []
        for i in range(0, len(sort_list)):
            if sort_list[i] < mid:
                left_list.append(sort_list[i])
            if sort_list[i] > mid:
                right_list.append(sort_list[i])
        return quick_sort(left_list) + [mid] + quick_sort(right_list)
    else:
        return sort_list

'''
    直接选择排序
    1. 创建新数组,循环当前数据,pop出最小数,添加到新数组,以此类推
'''
def selection_sort(sort_list):
    def _select_min_number(temp_list):
        if len(temp_list) is 0:
            return None
        min_number = temp_list[0]
        for _n in temp_list:
            if _n < min_number:
                min_number = _n
        return min_number

    new_list = []
    length = len(sort_list)
    while length > 0:
        min_number = _select_min_number(sort_list)
        new_list.append(min_number)
        sort_list.remove(min_number)
        length -= 1
    return new_list

'''
    计数排序
    1. 新建一个一样大小的数组
    2. 循环旧数组,取出第一个数A1,再循环一遍旧数组,逐一比较,记所有小于A1的数为p,记所有等于A1的数为q
    3. 赋值给新数组下标为[p]-[p+q]范围的数为A1,以此类推
'''
def counting_sort(sort_list):
    length = len(sort_list)
    new_list = [None]*length
    for i in range(length):
        p = 0
        q = 0
        for j in range(length):
            if sort_list[j]<sort_list[i]:
                p+=1
            if sort_list[j]==sort_list[i]:
                q+=1
        for k in range(p,p+q):
            new_list[k] = sort_list[i]
    return new_list



if __name__ == '__main__':
    _range = 100
    length = 5
    _list = random.sample(range(_range), length)
    print('before sort is ', _list)
    _list = diminishing_increment_sort(_list)
    print('alter sort is', _list)

其他排序算法

上述的排序算法都是简单的排序算法,应该属于比较直观容易一次理解的,但也有不少排序算法是比较复杂的,下列排序算法后续会一个一个整理出来。

  • 归并算法
  • 堆排序
  • 桶排序
  • 基数排序
阅读: 153
分类: 算法理论
创建时间: 2019-03-12 14:54:02
更新时间: 2019-12-05 15:47:02
博文目录

[[replyMessage== null?"发表评论":"@" + replyMessage.m_author]]

account_circle
email
web_asset
textsms

评论列表([[messageList.data.items.length]])

[[messageItem.m_author]] [[messageItem.m_author]]
[[messageItem.create_time]]
[[messageItem.m_environ.browser]] [[messageItem.m_environ.os]] [[messageItem.m_environ.device]]
[[subMessage.m_author]] [[subMessage.m_author]] @ [[subMessage.parent_message.m_author]] [[subMessage.parent_message.m_author]]
[[subMessage.create_time]]
[[subMessage.m_environ.browser]] [[subMessage.m_environ.os]] [[subMessage.m_environ.device]]