几种常见的排序算法

几种常见的排序方法

常见算法效率比较：

一. 冒泡排序

冒泡排序是是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把它们交换过来。遍历数列的工作是重复的进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端

理解草图~

代码

def bub(alist):
    for i in range(len(alist)-1,0,-1):
        for j in range(len(alist)):
            if alist[i] < alist[i+1]:
                alist[i],alist[i+1] = alist[i+1],alist[i]                

时间复杂度

算法的时间复杂度是指算法执行的过程中所需要的基本运算次数
（1）最优时间复杂度：O（n）（表示遍历一次发现没有任何可以交换的元素，排序结束）
（2）最坏时间复杂度：O(n2)
（3）稳定性：稳定
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的

二. 选择排序

选择排序是一种简单直观的排序算法。他的工作原理如下：
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置（末尾位置），然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，他们当中至少有一个将被移到最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动 元素的排序方法中，选择排序属于非常好的一种

代码

def select(alist):
    for i in range(len(alist)):
        min = i
        for j in range(i+1,n):
            if alist[j] < alist[min]:
                min = j
        if min != i:
            alist[min],alist[i] = alist[i],alist[min]

2. 时间复杂度

   （1）最优时间复杂度：O(n2)

   （2）最坏时间复杂度：O(n2)

   （3）稳定性：不稳定（升序的时候不稳定，相等两个数的相对位置一定会发生变化）

三. 插入排序

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在从后向前扫描的过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间

代码

def insert_sort(alist):
    # 从第二个元素开始向前插入
    for i in range(1,len(alist)):
        for j in range(i,0,-1):
            if alist[j] < alist[j-1]:
                alist[j],alist[j-1] = alist[j-1],alist[j]
    return alist
                

时间复杂度

（1）最优时间复杂度：O(n)（升序排列，序列已经处于升序状态）
（2）最坏时间复杂度：O(n2)
（3）稳定性：稳定

四. 快速排序

快速排序，又称划分交换排序。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都要小，然后再按此方法对两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
步骤为 ：
（1） 从数列中挑选一个元素，称为“基准”
（2） 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以放到任意一边，但一般都统一放到一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区操作
（3）递归的把小于基准值元素的子数列和大于基准值元素的子数列排序
递归的最底部情形，是数列的大小基准值元素的子数列和大于基准值元素的子数列排序

代码

def quick_sort(alist):
    if len(alist) <= 2:
        return alist
    p = []
    q = []
    m = []
    poi = alist[0]
    while alist:
        if alist[-1] < poi:
            p.append(alist().pop())
        elif alist[-1] == poi:
            q.append(alist().pop())
        else:
            m.append(alist().pop())
    quick_sort(p)
    quick_sort(m)
    alist.extend(p)
    alist.extend(q)
    alist.extend(m)
    return alist

# 一行代码实现
quick_sort = lambda alist:alist if len(alist) < 2 else quick_sort([i for i in alist[1:] if i < alist[0]]) + [alist[0]] + quick_sort([i for i in alist[1:] if i > alist[0]])

2. 时间复杂度

   （1）最优时间复杂度：O(nlogn)

   （2）最坏时间复杂度：O(n2)

   （3）稳定性：不稳定

赏

老板大气

支付宝

微信