欢迎来访我的博客。

常见排序算法的Python实现,及其复杂度和稳定性分析

Python 小张哥哥 600浏览 2评论

排序算法经过很长时间的演化,产生了很多不同的方法。虽然每一种的算法在时间和空间复杂度上各有不同,但是各种算法也都有不同的应用场景,并不是效率最高的算法就适应所有的使用场景。
下面我们来归纳一下我们常见的一些排序算法,已经这些算法的时间复杂度和空间复杂度,以及这些排序算法的稳定性。
按照大的分类,排序可以分为内排序和外排序。内排序是值在排序过程中,全部记录都是存放在内存中的。而外排序则是在排序过程中需要使用到外部存储。
我们下面总结的是内排序算法:

  • 插入排序

  • 选择排序

  • 冒泡排序

  • 快速排序

  • 归并排序

  • 希尔排序

  • 基数排序

  • 堆排序


插入排序


排序思想

插入排序是思想很简单,就是最初先把一个序列的第一个元素看成一个有序序列,然后把后面的序列看作无序序列。将后面无序序列中的元素逐个放到前面的有序序列中的合适位置。


排序过程示例

现有一个待排序的序列:

5483736



5

4

8

3

7

3

6

首先,我们把[5,] 看作一个单独的有序序列,后面的[4,8,3,7,3,6]看作一个无序序列。

有序序列 = [5,],
无序序列 = [4, 8, 3, 7, 3, 6]
然后选择将后面无序序列,现在我们把无序序列中的第一个元素放到有序序列的合适位置,然后
有序序列 = [4, 5,],
无序序列 = [8, 3, 7, 3, 6]
经过一次排序后,序列变为:

4583736

然后再把前面继续前面类似的操作,将后面无序序列中的元素逐一加到有序序列中。最终完成排序过程。


python实现

# 插入排序算法
def insert_sort(array):
    for i in range(1, len(array)):
        j = i - 1 # array[0:j]是有序序列, array[i:]是无序序列
        temp = array[i] # temp暂存待存入有序序列的数字
        while j >= 0 and array[j] > temp: # 寻找有序序列中的合适位置
            array[j+1] = array[j] # 如果当前数字大于待存入的temp,则把该数字后移一位
            j -= 1
                  
        array[j+1] = temp # 将待排序的数字存到有序序列中的合适位置
            
    return array


算法复杂度

时间复杂度:
最好的情况下,如果序列本来就是有序的,则不会进入到内部循环中,只有一层循环,时间复杂度是O(n);最坏情况下,序列是反序的,则要完全运行两层循环,时间复杂度为O(n2)。平均时间复杂度为O(n2)。

空间复杂度:O(1)


算法稳定性

在排序过程中,是从无序序列的开始到结尾,一个一个与前面的有序序列中的元素做比较,因此该排序是稳定的。


选择排序


排序思想

从待排序的序列中找出最小的元素与第一个元素交换,然后再在剩下的序列中找出最小的元素与第二个元素交换,以此类推。。。直到最后一个元素


排序过程示例

现有一个待排序的序列

5483736

首先,从头到尾找到最小的元素3;
然后,将3与第1个元素交换。
经过1次排序后,序列变为:

3485736

然后,在剩下的序列中找出最小的,也是3,与第2个元素交换,
经过2次排序后,序列变为:

3385746

然后,在剩下的序列中找出最小的,是4,与第3个元素交换。
经过2次排序后,序列变为:

3345786

。。。。。。


python实现

# 选择排序算法
def select_sort(array):
    array_len = len(array)
    for i in range(array_len):
        k = i        
        for j in range(i, array_len): # 从头到尾找出最小的
            if array[k] > array[j]:
                k = j
        array[i], array[k] = array[k], array[i] # 交换位置

    return array


算法复杂度

时间复杂度:
排序的两层循环都需要走一遍,因此该算法安的最好的情况,最坏情况下和平均情况下的时间复杂度均为O(n2)。

空间复杂度:O(1)


算法稳定性

不稳定,比如序列[3,4,3,1,],第1次排序时候,首尾两个数字交换,序列中两个3的相对位置就发生变化了。


冒泡排序


排序思想

排序思想是从第1个元素到第n个元素遍历,如果前一个元素大于后一个元素,则调换两者位置。这样经过一次排序后,最大的元素就排到了最后面。然后再从第1个元素到第n-的元素进行下一轮的冒泡排序


排序过程示例

现有一个待排序的序列

5483736

首先,冒泡一次,第1个元素和第2个元素交换位置:

4583736

然后,一直相互对比,直到最后,
经过一轮冒泡之后,序列变为:

4537368

然后再继续第2轮的冒泡。


python实现

# 冒泡排序
def bubble_sort(array):
    array_len = len(array)
    for i in range(array_len):
        for j in range(array_len-i-1):
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]
    return array


算法复杂度

时间复杂度:
冒泡排序与选择排序类似,无论序列情况,都需要完全走完两层for循环,最好,最坏和平均的时间复杂度都为O(n2)。

空间复杂度:O(1)


算法稳定性

冒泡排序时,相同的元素不会出现位置的调换,排序是稳定的。


快速排序


排序思想

先选取一个基准元素base,一般我们选择第1个元素,然后分别找两个指针left和right分别指向序列的第一个和最后一个元素,然后right往前面去找,找到一个小于基准元素的的元素,将该元素赋值给left所在位置;然后再从left位置继续往后找,找到一个大于基准元素的元素,然后将该元素赋值给right所在位置,然后再right往前。。。。。就这样left以此交替,直到left和right两者相遇。相遇后,则将原来标记的基准元素base赋值到该位置。
这样就将序列以base为界分为了前后两个部分,前一部分是小于基准元素的,后一部分是大于基准元素的。然后我们再分别对base前后的两个子序列按照以上相同的方式递归。最后整个序列就完成了排序了。


排序过程示例

现有一个待排序的序列

5483736

首先,我们选取第1个元素为基准元素,赋值给变量base。然后分别定义两个指针left, right指向第一个元素和最后一个元素:

5483736
base 
left
-----right

然后,先从right指针开始,判断指向的元素是否小于基准元素base,如果满足条件,则一个一个元素地持续向左移动,直到找到元素满足条件。如下:
base = 5

5483736
base 
left
----right-

然后把right指向的元素赋值给base指向的元素。
base = 5

3483736
base 
left
----right-

然后再从左向右移动left指针,直到找到一个大于base的元素:
base = 5

3483736
base-left--right-

然后将left指向的元素赋值给right指向的元素:
base = 5

3483786
base-leftright---

接下来,再去移动right指针,寻找小于base的元素,如果有,则赋值给此时left指向的元素:
base = 5

3433786
base-leftright---

然后再移动left指针,寻找大于base的元素,如果有,赋值给right指向的元素。此时,对于我们的例子,left和right指针已相遇,则停止移动:
base = 5

3433786
base--right
left
---

相遇后,则将base赋值给此时相遇的位置的元素:
base = 5

3435786
base--right
left
---

于是,序列被base给分割成了两个部分,左边的全部小于5, 右边的全部大于5,然后,我们再继续对左半和右半边的元素按照相同的方式递归,直到最终完成所有元素的排序。


python实现

# 快速排序1
def partition(array, left, right):
    base = array[left]
    while left < right:
        while left < right and array[right] >= base: # 从右边找到第一个小于base的元素
            right -= 1
        array[left] = array[right] # 找到后,赋值给left所指位置
        while left < right and array[left] <= base: # 从左边找到第一个大于base的元素
            left += 1
        array[right] = array[left] # 找到后,赋值给right所指的位置
    array[left] = base # left和right相遇时,将base赋值到它们相遇的位置
    return left # 返回中间分界点,此时左边的都小于base, 右边的都大于base
def quick_sort(array, left, right):
    if left < right:
        mid = partition(array, left, right)
        quick_sort(array, left, mid-1)
        quick_sort(array, mid+1, right)
    return array

改进一下,可以将以上两个函数合并为一个,原理是一样的:

# 快速排序2
def quick_sort_2(array, left, right):
    if left >= right:
        return
    base = array[left]
    l, r = left, right    while l < r:
        while l < r and array[r] >= base:
            r -= 1
        while l < r and array[l] <= base:
            l += 1
        if l < r:
            array[l], array[r] = array[r], array[l]
    array[left], array[l] = array[l], array[left]

    quick_sort_2(array, left, l-1)
    quick_sort_2(array, l+1, right)

另外,在网上看到一个很简短的快排的python实现:

def qsort(lst):
    if not lst:
        return []
    return qsort([i for i in lst[1:] if i < lst[0]]) + [lst[0]] + qsort([i for i in lst[1:] if i > lst[0]])


算法复杂度

时间复杂度:
最好的情况下,每次都能将序列平均分为两份,这种情况下的时间复杂度就是O(N*log2N);最坏情况下,每次划分都是一半是1个元素,另一半是n-1个元素,这种极端情况下的时间复杂度为O(n2)。平均时间复杂度为O(n2)。

空间复杂度:
每次都分出一半进行单独的排序,比较占用内存,最好情况下,空间复杂度为O(log2N),最差情况下,空间复杂度为O(n)


算法稳定性

不稳定,比如[3,4,1,1]排序,可能会使原来两个1元素的相对位置发生变化。


归并排序


排序思想

归并排序的思想是将一个序列根据二分法分为两个序列,然后再将这两个序列一直二分下去,直到最后是单个元素,然后再对分出来的两个序列做合并,合并成一个局部有序的子序列,然后再继续向上合并,直到最终所有子序列合并,变成一个完全有序的序列。


排序过程示例

现有一个待排序的序列

5843736

首先,该序列有7个元素,可以分为

584

3736

两个列表,再将前一个继续二分下去得到

5

84

然后,

84

继续二分得到

8

4

现在已经二分到了最小的单元,然后再进行归并排序

8

4

归并排序得到

48

得到的序列再和之前分出来的

5

进行归并排序得到

458

同样的,前面分出的另一半也通过上述归并排序得到

3367

现在这两个子序列也都是局部有序的,再进行一个归并即可得到:

3345678


python实现

# 归并排序
def merge(left, right):
    i, j = 0, 0
    merged_array = []
    while i < len(left) and j < len(right): # 将两个序列中元素从前面开始依次比较,从小到大归并进新序列
        if left[i] <= right[j]:
            merged_array.append(left[i])
            i += 1
        else:
            merged_array.append(right[j])
            j += 1
    merged_array.extend(left[i:]) # 将序列中剩余的元素也归并进去
    merged_array.extend(right[j:]) # 将序列中剩余的元素也归并进去
    return merged_array        
def merge_sort(array):
    array_len = len(array)
    if array_len == 1:
        return array
    mid = array_len//2 # 将序列二分为两个部分
    left = array[:mid]
    right = array[mid:]
    return merge(merge_sort(left), merge_sort(right)) # 递归调用


算法复杂度

时间复杂度:
始终需要对序列进行二分,然后合并,因此时时间复杂度在最好,最坏和平均情况下都为O(N*log2N)。平均时间复杂度为O(n2)。

空间复杂度:O(n), 序列越长,二分需要占用的内存越大。


算法稳定性

归并排序的算法是稳定的。


希尔排序


排序思想

希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率。但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位。

假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为O(n2)的排序(冒泡排序或插入排序),可能会进行n次的比较和交换才能将该数据移至正确位置。而希尔排序会用较大的步长移动数据,所以小数据只需进行少数比较和交换即可到正确位置。


排序过程示例

例如,假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ],如果我们以步长为5开始进行排序,我们可以通过将这列表放在有5列的表中来更好地描述算法,这样他们就应该看起来是这样:
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
然后我们对每列进行排序:
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
将上述四行数字,依序接在一起时我们得到:[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了,然后再以3为步长进行排序:
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
排序之后变为:
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
最后以1步长进行排序(此时就是简单的插入排序了)。

步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序,最终算法以步长为1进行排序。当步长为1时,算法变为普通插入排序,这就保证了数据一定会被排序。


python实现

def shell_sort(array):
    array_len = len(array)
    step = array_len//2

    while step >= 1: # 步长一直减半到1
        for i in range(step, array_len): # 从第二行序列开始,以步长step为间隔进行插入排序
            j = i - step
            temp = array[i]
            while j >= 0  and array[j] > temp:
                array[j+step] = array[j]
                j = j - step
            array[j+step] = temp
        step = step//2 # 步长减半
    
    return array


算法复杂度

时间复杂度:
它的最好及最差时间复杂度和简单插入排序一样,分别是是O(n)和O(n2),平均时间复杂度试增量选取规则而定,一般认为介于O(n)和O(n2)之间

空间复杂度:O(1),不需要额外空间


算法稳定性

与直接插入排序不同,希尔排序是不稳定的。


基数排序


排序思想

基数排序是一种典型的空间换时间的排序方法。现在所有排序数字中找到最大的数字,确定它的位数,然后将所有待比较数值统一为同样的数位长度,数位较短的数前面补零。接下来,依次从最低位到最高位,将该位的数字按照从小到大分配该数位的位置,然后再将这些数字依次收集回到待排序序列中,然后再对下一个位数进行如上操作,直到最高位。


排序过程示例

现有一个待排序的序列

1725434322521361000

首先,确定最大数字位5213,位数为4
然后,先从个位数开始,将这些数字存入到0-10的容器中:

0123456789
1000
220003
5213
254
034

617

然后将这些数字再依次收集回来,得到的序列为:

1000223521325434617

经过这一轮的分配和收集之后,序列元素就按照最低位的数字从小到大排列了。
然后再根据第2位(十位)进行分配:

0123456789
1000
0003
0006
5213
0017
2234
254



然后再将这些元素收集:

1000365213172234254

重复上述步骤,直到最高位。即可完成序列的排序。


python实现

# 基数排序
def radix_sort(array):
    # 找到序列中最大的数
    max_num = max(array)
    # 最大数的位数
    bit_num = 0
    while max_num > 0:
        bit_num += 1
        max_num = max_num//10

    # 最外层循环,每次循环按照位数分配并取回一次
    for i in range(bit_num):    
    # 建一个列表(列表元素也是一个列表),存储分配过来的数字
        container = [[] for x in range(20)]
        
        # 将所有数字分配到列表中
        for item in array:
            # 获取元素相应位数的数字
            x = item % (10**(i+1))// (10**(i))
            container[x].append(item)

        array = []
        # 从0到10,依次将container列表中的元素取出来
        for j in range(10):
            array.extend(container[j])
    
    return array


算法复杂度

时间复杂度:
基数排序的最好,最好、最坏和平均时间复杂度都是O(n*r),其中n是数据大小,r是所选基数。

空间复杂度:
O(n+r)的额外空间。它是稳定的。


算法稳定性

基数排序的算法是稳定的。


堆排序


排序思想

堆排序利用的是二叉树的思想,所谓堆就是一个完全二叉树,完全二叉树的意思就是,除了叶子节点,其它所有节点都有两个子节点,这样子的话,完全二叉树就可以用一个一块连续的内存空间(数组)来存储,而不需要指针操作了。堆排序分两个流程,首先是构建大顶堆,然后是从大顶堆中获取按逆序提取元素。
首先是大顶堆,大顶堆即一个完全二叉树,的每一个节点都大于它的所有子节点。大顶堆可以按照从上到下从左到右的顺序,用数组来存储,第i个节点的父节点序号为(i-1)/2,左子节点序号为2i+1,右子节点序号为2(i+1)。构建大顶堆的过程即从后向前遍历所有非叶子节点,若它小于左右子节点,则与左右子节点中最大的交换,然后递归地对原最大节点做同样的操作。


排序过程示例

现有一个待排序的序列

548373961

首先,列表以完全二叉树的形式如下图:


548376139

然后,从最后一个根节点开始,将它的左右子节点和根节点的值作比较,将最大的值放到根节点,如下:


548673139

接下来,按照上述调整方法,从后往前依次调整各个根节点,直到调整到最后:


978643135

这样,经过一轮后,最大的就被排到了最前面。

978643531

然后将该元素交换到序列末尾,序列就变成了:

178643539

最大的元素被排到了最后。
调换顺序之后,第一个元素的最大堆特征被破坏,然后对其进行调整。
重复以上步骤,直至元素全部调整为有序。


python实现

# 堆排序
def heap_sort(array):
    def heap_adjust(array, x, length):
        '''
        调整序列中的某个节点,array为待调整序列,x为待调整节点,length为序列长度
        '''
        left_chl, right_chl = 2*x + 1, 2*x + 2 # 节点x的左右子节点
        max = x        if left_chl < length and array[left_chl] > array[max]:
            max = left_chl        if right_chl < length and array[right_chl] > array[max]:
            max = right_chl        if max != x:
            array[x], array[max] = array[max], array[x] # 将较大的节点和父节点交换
            # 交换后可能造成该节点下的子节点序列错乱,再次调整一下
            heap_adjust(array, max, length)

    def build_heap(array):
        '''
        构建一个最大堆
        '''
        # 找出序列array指定长度length的切片的子序列中的最后一个根节点
        # last_root_num = (length-1)//2
        # For循环,从最后一个根节点以此往前调整,直到根节点
        array_len = len(array)
        for i in range((array_len-1)//2, -1, -1):
            heap_adjust(array, i, array_len)
    

    array_len = len(array)
    # 构建最大堆
    build_heap(array)
    for i in range(array_len-1, 0, -1):
        # 将构建好的最大堆中的第一个元素(最大)交换到最后一个位置。
        array[i], array[0] = array[0], array[i]
        # 交换之后,调整剩下的序列为一个最大堆
        heap_adjust(array, 0, i+1)
    return array


算法复杂度

时间复杂度:
在最好,最坏和平均情况下的时间复杂度都为O(N*log2N)

空间复杂度:O(1)


算法稳定性

不稳定


各个排序算法比较

下面对这几种排序算法的特点进行总结和比较:

排序算法时间复杂度(最好)时间复杂度(最坏)时间复杂度(平均)空间复杂度稳定性复杂性
插入排序O(n)O(n2)O(n2)O(1)稳定简单
选择排序O(n2)O(n2)O(n2)O(1)不稳定简单
冒泡排序O(n2)O(n2)O(n)O(1)稳定简单
快速排序O(nlog2n)O(n2)O(nlog2n)O(1)不稳定复杂
归并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定复杂
希尔排序O(n)O(n2)O(n)~O(n2)(与步长有关)O(1)不稳定简单
基数排序O(n+r)O(n+r)O(n+r)O(n)稳定复杂
堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)不稳定复杂

下面,在序列长度不同的情况下,分别验证了各种排序算法耗时情况。
测试代码如下:

import datetime
def test_sort_time(func, num=1000):
    import random
    test_list = [x for x in random.sample([x for x in range(num)], num)]
    start_time = datetime.datetime.now()
    func(test_list)
    end_time = datetime.datetime.now()
    print("%s 排序耗时: %s" %(func.__name__, (end_time - start_time)))

    
num = 10000
test_sort_time(insert_sort, num)
test_sort_time(select_sort, num)
test_sort_time(bubble_sort, num)
# test_sort_time(quick_sort, num) # 快排的传参与其它的几个不同,我们测试快排时,需要稍微修改一下上述测试代码。
test_sort_time(merge_sort, num)
test_sort_time(shell_sort, num)
test_sort_time(radix_sort, num)
test_sort_time(heap_sort, num)

最终测试,得到如下数据:

序列长度插入排序选择排序冒泡排序快速排序归并排序希尔排序基数排序堆排序
10000.0392220.0574280.0830830.0029980.00.0156380.00.004994
100004.8453104.3779649.3594490.0392830.0632640.0560170.0282260.078919
1000007:49.4542657:36.09794116:11.9844100.3630530.7277790.9024170.3466371.036951
1000000------4.8527439.15649414.2133234.63367513.360319

从测试数据对比来看,基数排序在最终的排序耗时上表现是最好的。
既然基数排序效果这么好,为什么没有其它的排序算法(比如快排)应用更广泛呢?我觉得应该是基数排序的使用范围有限,并不是所有的排序都能使用基数排序。能用于基数排序需要序列中的元素都是有基数的(整数和浮点数)。


转载请注明:禅思 » 常见排序算法的Python实现,及其复杂度和稳定性分析?

喜欢 (12) or 分享 (0)

我的个人微信公众号,欢迎关注

扫码或搜索:Python后端开发Django

Python后端开发Django

微信公众号 扫一扫关注

结交朋友、一起学习,一起进步。

科波之主

QQ号 386046154 立即加入

添加微信,进行技术交流

专注技术交流, 一同成长进步

我的微信号

如果您喜欢我的文章,感觉我的文章对您有帮助,请狠狠点击下面

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
(2)个小伙伴在吐槽
    1. 感谢作者分享学习了,希望作者以后再接再厉,写出更好的文章 www.87la.com
      金毛囊植发 2020-10-22 23:57:05 回复
      • tadalafil pills 20mg tadalafil daily use tadalafil gel
        Wesleyviord 2021-03-05 15:08:04 回复