微信号:PythonPush

介绍:人生苦短,我用 Python.Python 越来越受广大程序员的喜爱.

Python 实现快速排序、冒泡排序和选择排序

2019-04-07 19:21 程序君

Linux编程
点击右侧关注,免费入门到精通!


作者|借我一生执拗

https://www.jianshu.com/p/c150fd974ce8


本节让我们来介绍三种常用的排序算法。


1. 快速排序


首先要打乱序列顺序 ,以防算法陷入最坏时间复杂度。快速排序使用“分而治之”的方法。


对于一串序列,首先从中选取一个数,凡是小于这个数的值就被放在左边一摞,凡是大于这个数的值就被放在右边一摞。然后,继续对左右两摞进行快速排序。


直到进行快速排序的序列长度小于 2 (即序列中只有一个值或者空值)。


 
           

# quicksort
import random
def quicksort(seq):
    if len(seq) < 2:
        return seq
    else:
        base = seq[0]
        left = [elem for elem in seq[1:] if elem < base]
        right = [elem for elem in seq[1:] if elem > base]
        return quicksort(left) + [base] + quicksort(right)
seq = [9876543]
random.shuffle(seq)
# seq:[6, 4, 9, 3, 8, 5, 7]
print(quicksort(seq))
# 输出:[3, 4, 5, 6, 7, 8, 9]


2.  冒泡排序


冒泡排序(顺序形式),从左向右,两两比较,如果左边元素大于右边,就交换两个元素的位置。


其中,每一轮排序,序列中最大的元素浮动到最右面。也就是说,每一轮排序,至少确保有一个元素在正确的位置。


这样接下来的循环,就不需要考虑已经排好序的元素了,每次内层循环次数都会减一。


其中,如果有一轮循环之后,次序并没有交换,这时我们就可以停止循环,得到我们想要的有序序列了。


 
           

def bouble_sort(sequence):
    seq = sequence[:]
    length = len(seq) - 1
    i = j = 0
    flag = 1
    while i < length:
        j = 0
        while j < length - i:
            if seq[j] > seq[j + 1]:
                seq[j], seq[j + 1] = seq[j + 1], seq[j]
                flag = 0
            j += 1
        if flag:
            break
        i += 1
    return seq


3. 选择排序


选择排序,每次选择当前序列的最小值,将其与当前序列的第一个元素交换位置,每迭代一次,当前序列长度减一。迭代结束,即可得到有序序列。

  
            

def find_minimal_index(seq):
    min_elem = seq[0]
    count = 0
    min_elem_index = count
    for elem in seq[1:]:
        count += 1
        if elem < min_elem:
            elem, min_elem = min_elem, elem
            min_elem_index = count
    return min_elem_index


def select_sort(sequence):
    # 选择排序
    seq = sequence[:]
    length = len(seq)
    for i in range(length):
        index = find_minimal_index(seq[i:])
        seq[index + i], seq[i] = seq[i], seq[index + i]
    return seq


 推荐↓↓↓ 

👉16个技术公众号】都在这里!

涵盖:程序员大咖、源码共读、程序员共读、数据结构与算法、黑客技术和网络安全、大数据科技、编程前端、Java、Python、Web编程开发、Android、iOS开发、Linux、数据库研发、幽默程序员等。

万水千山总是情,点个 “ 好看” 行不行
 
Python开发 更多文章 一步步用python制作游戏外挂 程序员编程十大原则 Python已经被编进小学教材了?啥时候纳入高考…… Python「八宗罪」 让你事半功倍的小众 Python 库
猜您喜欢 一致性hash算法介绍 你和世界,我想一起守护 2分钟读懂大数据框架Hadoop和Spark的异同 详解JavaScript中的原型和继承 Ubuntu 18.04 LTS即将发布:都有哪些新内容?