手记

使用 Python 实现几种常见的排序算法

排序是非常常见的算法,今天就来分享几种常见排序算法的 Python 实现

冒泡排序

冒泡排序是最为基础的排序算法,其核心思想就是相邻元素两两比较,把较大的元素放到后面,在一轮比较完成之后,最大的元素就位于最后一个位置了,就好像是气泡,慢慢的浮出了水面一样。

def bubble_sort(data, reverse=False):
    """
    :param data: list type data
    :param reverse:
    :return: list type data
    """
    if not reverse:
        for i in range(len(data) - 1):
            for j in range(len(data) - 1 -i):
                if data[j] > data[j+1]:
                    data[j], data[j+1] = data[j+1], data[j]
        return data
    else:
        for i in range(len(data) - 1):
            for j in range(len(data) - 1 -i):
                if data[j] < data[j+1]:
                    data[j], data[j + 1] = data[j + 1], data[j]
        return data

其实冒泡排序算法还是比较好理解的,只需要进行两次循环,最外层的循环代表排序元素的个数,内部循环则进行两两比较,时间复杂度为 O(n^2)。

选择排序

选择排序,是逐个确定元素位置的思想。同样是 n 遍循环,第一轮时,每一个元素都与第一个元素比较,如果比第一个元素大,则与之交换,这样一轮过后,第一个元素就是最小的了,第二轮开始每个元素与第二个位置的元素比较,如果大,则与第二位置的元素交换,以此类推,达到排序的目的

def selection_sort(data, reverse=False):
    """
    :param data: list type data
    :param reverse:
    :return: list type data
    """
    if not reverse:
        for i in range(len(data)-1):
            min_index = i
            for j in range(i+1, len(data)):
                if data[j] < data[min_index]:
                    min_index = j
            data[i], data[min_index] = data[min_index], data[i]
        return data
    else:
        for i in range(len(data) - 1):
            min_index = i
            for j in range(i+1, len(data)):
                if data[j] > data[min_index]:
                    min_index = j
            data[i], data[min_index] = data[min_index], data[i]
        return data

选择排序和冒泡排序还是很相似的,但是选择排序会比冒泡排序少一次交换的过程,但是同样时两层循环,所有时间复杂度也是 O(n^2)

插入排序

插入排序的思想是把一个数据插入到一个有序序列中,从而得到一个新的序列加一的有序序列,可以通过下图来进一步加深理解

def insert_sort(data, reverse=False):
    if not reverse:
        for i in range(1, len(data)):
            key = data[i]
            j = i - 1
            while j >= 0:
                if data[j] > key:
                    data[j+1] = data[j]
                    data[j] = key
                j -= 1
        return data
    else:
        for i in range(1, len(data)):
            key = data[i]
            j = i - 1
            while j >= 0:
                if data[j] < key:
                    data[j+1] = data[j]
                    data[j] = key
                j -= 1
        return data

由于每次遍历有序序列时,都会有序列中所有的数据做对比,故而时间复杂度为O(n^2)

快速排序

快排的思想为首先任意选取一个数据(通常选用数组的第一个数)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序,之后再递归排序两边的数据。

def quick_sort(data):
    if not data:
        return data
    first = data[0]
    left = quick_sort([l for l in data[1:] if l < first])
    right = quick_sort([r for r in data[1:] if r >= first])
    return left + [first] + right

好了,今天的分享就到这里了。

1人推荐
随时随地看视频
慕课网APP

热门评论

正在学python,老是坚持不下去

查看全部评论