数据结构与常见排序算法之算法篇（基于Python）

GitHub：https://github.com/Pgrammerybj （进去的动动小手点个赞哈）

什么是算法？

我们举一个可能不太恰当的例子：

如果将最终写好运行的程序比作战场，我们码农便是指挥作战的将军，而我们所写的代码便是士兵和武器。

那么数据结构和算法是什么？答曰：兵法！

我们可以不看兵法在战场上肉搏，如此，可能会胜利，可能会失败。即使胜利，可能也会付出巨大的代价。我们写程序亦然：没有看过数据结构和算法，有时面对问题可能会没有任何思路，不知如何下手去解决；大部分时间可能解决了问题，可是对程序运行的效率和开销没有意识，性能低下；有时会借助别人开发的利器暂时解决了问题，可是遇到性能瓶颈的时候，又不知该如何进行针对性的优化。

如果我们常看兵法，便可做到胸有成竹，有时会事半功倍！同样，如果我们常看数据结构与算法，我们写程序时也能游刃有余、明察秋毫，遇到问题时亦能入木三分、迎刃而解。

故，数据结构和算法是一名程序开发人员的必备基本功，不是一朝一夕就能练成绝世高手的。冰冻三尺非一日之寒，需要我们平时不断的主动去学习积累。

在这里将通过以下几个排序算法来演示：
* 冒泡排序
* 选择排序
* 插入排序
* 希尔排序
* 快速排序
* 归并排序

分类演说

一、冒泡排序

1.冒泡排序算法的运作如下:

• 比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
• 针对所有的元素重复以上的步骤，除了最后一个。
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

2.交换过程图解:

冒泡排序

3.时间复杂度

• 最优时间复杂度：O(n) （表示遍历一次发现没有任何可以交换的元素，排序结束。）
• 最坏时间复杂度：O(n2)
• 稳定性：稳定

4.代码演示：

def bubble_sort1(numList):
    """冒泡排序(正向，从前到后排,时间复杂度O(n2))"""
    length = len(numList)
    for i in range(0, length - 1):

        for j in range(0, length - 1 - i):

            if numList[j] > numList[j + 1]:
                numList[j], numList[j + 1] = numList[j + 1], numList[j]


def bubble_sort2(numList):
    """冒泡排序(反向，从后往前排，时间复杂度O(n2))"""
    length = len(numList)
    for i in range(length - 1, 0, -1):

        for j in range(i):

            if numList[j] > numList[j + 1]:
                numList[j], numList[j + 1] = numList[j + 1], numList[j]


def bubble_sort3(numList):
    """冒泡排序(如果给出的列表就是有序的序列，那么可以这样优化,时间复杂度O(n2)，最优为O(n))"""
    length = len(numList)
    for i in range(length - 1, 0, -1):
        is_change = False
        for j in range(i):
            if numList[j] > numList[j + 1]:
                numList[j], numList[j + 1] = numList[j + 1], numList[j]
                is_change = True

        if not is_change:
            return


if __name__ == '__main__':
    li = [23, 23, 97, 1, 45, 775, 9, 12]
    li2 = [2, 1, 97, 324, 45, 775, 0, 12]
    li3 = [1, 2, 3, 4, 5, 6, 7, 8]
    li4 = [2, 1, 97, 324, 45, 775, 0, 12]

    print("排序前：" + str(li))
    bubble_sort1(li)
    print("正向排序" + str(li))

    print("排序前：" + str(li2))
    bubble_sort2(li2)
    print("反向排序" + str(li2))

    print("排序前：" + str(li3))
    bubble_sort3(li3)
    print("优化排序" + str(li3))

    print("排序前：" + str(li4))
    bubble_sort3(li4)
    print("优化排序" + str(li4))

二、选择排序

1.选择排序的原理

• 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
• 再从剩余未排序元素中继续寻找最小（大）元素， 然后放到已排序序列的末尾。
• 以此类推，直到所有元素均排序完毕。

2.排序过程图解:

选择排序

3.时间复杂度

• 最优时间复杂度：O(n2)
• 最坏时间复杂度：O(n2)
• 稳定性：不稳定（考虑升序每次选择最大的情况）

4.代码演示：

def select_sort(numList):
    length = len(numList)

    for i in range(length - 1):

        minIndex = i

        for j in range(i + 1, length):

            if numList[minIndex] > numList[j]:
                minIndex = j

        numList[i], numList[minIndex] = numList[minIndex], numList[i]
        print("排序过程中：" + str(li))


if __name__ == '__main__':
    li = [23, 23, 97, 1, 45, 775, 9, 12]
    print("排序前：" + str(li))
    select_sort(li)
    print("排序后：" + str(li)

三、插入排序

1.插入排序算法的运作如下:

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

2.排序过程图解:

插入排序

3.时间复杂度

• 最优时间复杂度：O(n) （升序排列，序列已经处于升序状态）
• 最坏时间复杂度：O(n2)
• 稳定性：稳定

4.代码演示：

def insert_sort(numList):
length = len(numList)

for i in range(1, length):

    # for j in range(0, i):
    #
    #     if numList[i] < numList[j]:
    #         numList[i], numList[j] = numList[j], numList[i]

    for j in range(i, 0, -1):

        if numList[j] < numList[j - 1]:
            numList[j], numList[j - 1] = numList[j - 1], numList[j]
        else:
            break


if __name__ == '__main__':

li = [23, 23, 97, 1, 45, 775, 9, 12]
print("插入排序：")
print("排序前：" + str(li))
insert_sort(li)
print("排序后：" + str(li))

四、归并排序

1.归并排序的原理

归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。
将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。

2.排序过程图解

归并排序

3.时间复杂度

• 最优时间复杂度：O(nlogn)
• 最坏时间复杂度：O(nlogn)
• 稳定性：稳定

4.代码演示

def merge_sort(numlist):
    # 1.获取到需要排序的队列

    length = len(numlist)

    # 2.判断列表的长度，如果为1则不需排序直接返回

    if length <= 1:
        return numlist

    # 3.获取中间点，将队列的元素分成两个部分，递归继续拆分

    center_point = length // 2

    # 拆分的左边的部分
    left_list = merge_sort(numlist[:center_point])

    # 拆分的右边的部分，继续递归，直至队列的元素为1
    right_list = merge_sort(numlist[center_point:])

    # 4.初始化两个控制点,和存放排序后的队列
    left_point, right_point = 0, 0
    result = []

    # 5.循环比较左右两侧对应角标的元素大小
    while left_point < len(left_list) and right_point < len(right_list):

        # 左边的元素和右边的元素相比较，将小的元素添加栋队列中
        if left_list[left_point] <= right_list[right_point]:
            result.append(left_list[left_point])
            left_point += 1
        else:
            result.append(right_list[right_point])
            right_point += 1

    # 当退出上面的while循环就说明左侧或者右侧有一方的元素已经全部取完了，此时如果另一方如果还有元素那么就将剩余的元素添加到result中
    result += left_list[left_point:]
    result += right_list[right_point:]

    # 6.返回排序后的队列给用户
    return result


if __name__ == '__main__':
    num_list = [12, 87, 9, 6, 2, 876, 12, 0, 4]

    print("排序前：" + str(num_list))

    sortList = merge_sort(num_list)

    print("排序后：" + str(sortList))

持续更新....

喜欢的朋友动动小手点个赞咯，我会继续更新相关的内容，还望多多支持。

GitHub：https://github.com/Pgrammerybj （进去的动动小手点个赞哈）