排序算法

排序算法(英语: Sorting algorithm)是一-种能将一串 数据依照特定顺序进行排列的一种算法。

排序算法稳定性

稳定性:稳定排序算法会让原本有相等键值的纪录维持相对次序。也就是如果- - 个排序算法是稳定的，当有两个相等键值的纪录R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。当相等的元素是无法分辨的，比如像是整数，稳定性并不是一个问题。然而，假设以下的数对将要以他们的第一个数字来排序。

冒泡排序

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

图示

实现

# coding: utf-8


def bubble_sort(alist):
    """冒泡排序"""
    n = len(alist)
    for j in range(n-1):            # for j in rang(len(alist)-1,0,-1):
        count = 0
        for i in range(0, n-1-j):       # for i in range(j):
            # 从头走到尾
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]
                count += 1
        if 0 == count:
            return


if __name__ == "__main__":
    li = [45, 65, 54, 87, 9, 4, 5, 55]
    print(li)
    bubble_sort(li)
    print(li)

运行结果

时间复杂度

最优时间复杂度: O(n) (表示遍历- -次发现没有任何可以交换的元
素，排序结束。)
最坏时间复杂度: o(n^2)
稳定性:稳定

选择排序

        选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。

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

图示

实现

def select_sort(alist):
    """选择排序"""
    n = len(alist)
    for j in range(n-1):    # j: 0~ n-2
        min_index = j
        for i in range(j+1, n):
            if alist[min_index] > alist[i]:
                min_index = i
        alist[j], alist[min_index] = alist[min_index], alist[j]


if __name__ == "__main__":
    li = [45, 65, 54, 87, 9, 4, 5, 55]
    print(li)
    select_sort(li)
    print(li)

 运行结果

时间复杂度

最优时间复杂度: O(n^2)
最坏时间复杂度: O(n^2)
稳定性:不稳定(考虑升序每次选择最大的情况)

插入排序

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

图示

实现

# coding : utf-8

def insert_sort(alist):
    """插入排序"""
    n = len(alist)
    for j in range(1, n):       # 从右边的无序序列中取出多少个元素执行这样的过程
        i = j       # i代表内层循环起始值
        while i > 0:    # 执行从右边的无序序列中取出第一个元素，即i位置的元素,然后将其插入到前面位置中
            if alist[i] < alist[i-1]:
                alist[i], alist[i-1] = alist[i-1], alist[i]
                i -= 1
            else:
                break


if __name__ == "__main__":
    li = [25, 65, 54, 87, 19, 4, 35, 55]
    print(li)
    insert_sort(li)
    print(li)

运行结果

时间复杂度

最优时间复杂度: O(n) (升序排列， 序列已经处于升序
状态)
最坏时间复杂度: 0(n^2)
稳定性:稳定