Python3排序算法02 - 选择排序

  • 原创
  • Madman
  • /
  • 2018-09-03 12:28
  • /
  • 0
  • 114 次阅读

Synopsis: 选择排序算法每次从 "未排序序列" 中继续寻找最小(大)元素,然后放到 "已排序序列" 的末尾。它的时间复杂度为O(n^2),当待排序序列的元素个数很多时,性能很差

代码已上传到 https://github.com/wangy8961/python3-algorithms ,欢迎star

1. 算法介绍

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

  1. 首先在未排序序列中找到最小(大)元素,存放到已排序序列的起始位置
  2. 然后,再从剩余未排序序列中继续寻找最小(大)元素,然后放到已排序序列的末尾
  3. 以此类推,直到所有元素均排序完毕

Selection Sort 01

2. Python实现

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对 n 个元素的序列进行排序总共进行至多 n-1 次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种:

Selection Sort 02

def selection_sort(L):
    '''选择排序,升序'''
    n = len(L)
    if n <= 1:
        return

    for i in range(n-1):  # 共需要n-1次选择操作
        min_index = i  # 首先假设 "未排序列表"(上图中非绿色框) 的最小元素是它的第1个元素,第1次选择操作则假设L[0]是最小的,第2次操作则假设L[1]是最小的

        for j in range(i+1, n):  # 找出 "未排序列表" 中真正的最小元素的下标
            if L[j] < L[min_index]:
                min_index = j

        if min_index != i:  # 如果 "未排序列表" 中真正的最小元素,不是之前假设的元素,则进行交换
            L[i], L[min_index] = L[min_index], L[i]


if __name__ == '__main__':
    L1 = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print('Before: ', L1)
    selection_sort(L1)
    print('After: ', L1)

    # Output:
    # Before:  [54, 26, 93, 17, 77, 31, 44, 55, 20]
    # After:  [17, 20, 26, 31, 44, 54, 55, 77, 93]

压力测试:

from timeit import timeit


def selection_sort():
    # import random
    # gen = (random.randint(1, 100) for i in range(100))  # 产生100个 1-99 范围内的随机整数
    # L = list(gen)
    L = [96, 2, 65, 23, 47, 58, 8, 48, 69, 92, 34, 83, 93, 47, 45, 55, 95, 15, 92, 24, 64, 19, 29, 55, 35, 48, 39, 29, 63, 94, 99, 38, 50, 10, 10, 93, 74, 27, 74, 44, 29, 81, 85, 86, 74, 30, 50, 50, 12, 12, 38, 75, 41, 87, 80, 97, 16, 48, 65, 69, 83, 71, 28, 9, 64, 69, 27, 74, 74, 86, 40, 69, 79, 79, 77, 100, 53, 72, 77, 16, 8, 36, 41, 58, 59, 29, 46, 79, 81, 66, 8, 35, 60, 52, 2, 82, 2, 36, 79, 66]

    n = len(L)
    for i in range(n-1):
        min_index = i
        for j in range(i+1, n):
            if L[j] < L[min_index]:
                min_index = j

        if min_index != i:
            L[i], L[min_index] = L[min_index], L[i]

    return L


print('Selection sort function run 1000 times, cost: ', timeit('selection_sort()', 'from __main__ import selection_sort', number=1000), 'seconds.')

# Output:
# Selection sort function run 1000 times, cost:  0.824085003 seconds.

3. 性能

3.1 时间复杂度

(1) 最优时间复杂度

需要O(n^2)次比较(comparisons),和O(n)次交换(swaps)

(2) 平均时间复杂度

需要O(n^2)次比较,和O(n)次交换

selection sort 03

(3) 最坏时间复杂度

需要O(n^2)次比较,和O(n)次交换。比如传入已经按 "降序" 排好序的列表,却需要按 "升序" 去排列它

selection sort 04

3.2 空间复杂度

它是in-place comparison sort,总的空间复杂度(total)为O(n);还需要一个临时变量来交换元素位置,辅助空间复杂度(auxiliary)为O(1)

3.3 稳定性

选择排序不稳定排序算法:

Selection sort 05

代码已上传到 https://github.com/wangy8961/python3-algorithms ,欢迎star

未经允许不得转载: LIFE & SHARE - 王颜公子 » Python3排序算法02 - 选择排序

分享

作者

作者头像

Madman

如果博文内容有误或其它任何问题,欢迎留言评论,我会尽快回复; 或者通过QQ、微信等联系我

0 条评论

暂时还没有评论.

发表评论前请先登录