六大排序算法图解以及python实现

六大排序算法图解以及python实现

[TOC]

冒泡排序——名字好听的排序

  • 大学最先接触的一种排序算法,听名字就很萌的感觉,也是比较简单的一种,算法图示如下:

    这里写图片描述

    上图为第一次进行比较的图示:

    • 从第一个开始每次都比较相邻的两个数,如果发现顺序不对,就把两个数交换一下,直到最后一个。这个时候,最大的数自然而然就跑到最后一位上面去了。

    • 第二次的时候,也从第一个开始,不过只需要循环到n-2处就行了(因为n-1处经过第一次洗礼已经时最大了嘛。)

      。。。。。。依此类推,循环n次,整个数组就会变成有序的了。

  • 实现代码如下:

    1
    2
    3
    4
    5
    def bubble(nums):
    for i in range(len(nums)):
    for j in range(len(nums)-i-1):
    if nums[j+1] > nums[j]:
    nums[j+1], nums[j] = nums[j], nums[j+1]

选择排序——简单粗暴的排序

  • 选择排序大概是所有排序中最好理解,最简单粗暴的排序了。算法图示如下:

    这里写图片描述

    如图所示:

    1. 在第一次遍历中,从最开始到最后。找到最大的数,并于最后一个交换。

    2. 在第二次中,从最开始到倒数第二个。找到最大的数,并于倒数第二个交换。

      。。。。以此类推,循环n次。完成没有任何技术含量,所以效率几乎也是所有排序中最低的,强烈不推荐。

  • 算法实现

    1
    2
    3
    4
    5
    6
    7
    def select_sort(nums):
    for i in range(len(nums)):
    flag = i
    for j in range(i, len(nums)):
    if nums[j] > nums[flag]:
    flag = j
    nums[i], nums[flag] = nums[flag], nums[i]

插入排序——优雅不要污

  • 也是很简单的一种算法,同时也是后面的希尔排序的基础。如下图流程所示:

    这里写图片描述

    基本思想:

    1. 首先明确,第一个数肯定是有序的呀(一个数难道还能无序吗?),然后从第二个开始,从后往前扫描,把这个数插入到合适的位置,比第二个数大的一次往后面移动。
    2. 第二个数移动正确的位置之后,前两个数就是有序的,依次把后面的数按照刚才的方法插入到合适的位置,整个数组就变成有序的了。
  • 代码实现:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    def insert_sort(nums):
    for i in range(1, len(nums)):
    temp = nums[i]
    last = 0
    for j in range(i-1, -1, -1):
    if nums[j] > temp:
    nums[j + 1] = nums[j]
    else:
    last = j + 1
    break
    nums[last] = temp

希尔排序——插入排序的升级版

  • 希尔排序是插入排序的优化版,虽然表面上看起来并没有什么优化,相对于插入排序引入了步长的概念

    这里写图片描述

    如图所示:上图就表示step为4的场景。这时候整数数组的数据按照步长分为如上四组,对每一组都分别进行插入排序。

    • 当完成第一轮插入排序之后,step的步长减半,进行第二轮插入排序。

      。。。。以此类推,直到步长step=1的那一轮排序完成,整个数组就可以变为有序了。

    不过问题来了:这最后一轮不和插入排序一毛一样么?这能提高效率:

    这里写图片描述

    回答是:当然可以!其实每一次我们排序的时候整体都在逐渐趋于有序,都在不断的降低最后一步时的时间复杂度。在step合适的情况下,时间复杂度可以达到O(n^1.3),虽然我也不知道怎么算出来的,估计得问问数学家了。

快速排序——名字最牛逼的排序

  • 大名鼎鼎的快排,听名字就无意中透漏着我是最屌的感觉。

    这里写图片描述

  • 快排的基本思想就是先找到一个数作为patition,将数组中比patition小的数放在其左边,比patition大的数放在其右边,然后对其每一边再分别进行相同的操作(递归实现)。

    这里写图片描述

    上图是具体实现的思路:

    1. 我们一般已第一个数为partition,然后由两个标兵分别指向开始和结尾。
    2. 由最右边的橙色箭头开始往前扫描,直到扫描到比partition小的数字停下来,然后再由蓝色箭头向后扫描,直到遇见比partition大的数字停下来。然后交换停下来的两个数字。
    3. 就这样按照顺序,一直扫描。知道橙蓝两个箭头相遇,将相遇时的数字与partition交换就行了。
  • 编程实现:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    def quick_sort(nums, start, end):
    if end < start:
    return 0
    flag = nums[start]
    left = start
    right = end
    while start < end:
    while nums[end] > flag and end > start:
    end -= 1
    while nums[start] <= flag and end > start:
    start += 1
    nums[end], nums[start] = nums[start], nums[end]
    nums[left], nums[end] = nums[end], nums[left]
    quick_sort(nums, left, end - 1)
    quick_sort(nums, end + 1, right)
    def main():
    nums = [6, 3, 10, 5, 1, 9, 2, 7, 23, 4, 14]
    quick_sort(nums, 0, len(nums) - 1)
    print(nums)

归并排序——分治法的完美践行者

  • 归并排序是一种利用分治思想实现的排序,也是一种效率很高的排序。其排序流程具体如下:

    这里写图片描述

    如图所示:

    • 在归并排序的时候,我们将数组不断的拆分为两半,直到数据只剩一个的时候,然后再按照大小顺序把他们拼装起来。
  • 编码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def merge_sort(nums):
if len(nums) == 1:
return nums
mid = len(nums) // 2
left = merge_sort(nums[:mid])
right = merge_sort(nums[mid:])
return merge(left, right)
def merge(left, right):
temp = []
left_p, right_p = 0, 0
while left_p < len(left) and right_p < len(right):
if left[left_p] < right[right_p]:
temp.append(left[left_p])
left_p += 1
else:
temp.append(right[right_p])
right_p += 1
temp += (left[left_p:])
temp += (right[right_p:])
return temp
def main():
numbers = [6, 3, 10, 5, 45, 9, 2, 7, 23, 4, 14]
numbers = merge_sort(numbers)
print(numbers)

代码好像比之前的都要多一点,不过思路还是很简单的。主要是多了一个merge的过程:

  • 对于分别有序的两个数组,通过每次取出一个数据比较,将较小的那个放到新的数组中,较大的那个等待下次继续比较,就这样一直取,比较,取,比较,直到两个数组的数都放在了新的数组中。返回新的数组。
  • 大体的流程还是通过递归实现的,其实大部分分治的算法都是通过递归搞定的,方便理解。
    • 就效率而言,归并排序是六种排序中时间复杂度最好的,即使是最差情况,都是O(nlogn),不过由于归并排序需要额外的空间,所以也是一种拿空间换时间的策略。

六大算法的效率比较

  • 排序

    | 排序法 | 平均时间复杂度 | 最差情形 | 稳定度 | 额外空间 | 备注 |
    | ——- | ——– | ———– | —- | ——– | ——— |
    | 冒泡排序 | O(n2) | O(n2) | 稳定 | O(1) | n小时较好 |
    | 选择排序 | O(n2) | O(n2) | 不稳定 | O(1) | n小时较好 |
    | 插入排序 | O(n2) | O(n2) | 稳定 | O(1) | 大部分已排序时较好 |
    | Shell排序 | O(nlogn) | O(ns) 1<s<2 | 不稳定 | O(1) | s是所选分组 |
    | 快速排序 | O(nlogn) | O(n2) | 不稳定 | O(nlogn) | n大时较好 |
    | 归并排序 | O(nlogn) | O(nlogn) | 稳定 | O(1) | n大时较好 |