数据结构 排序算法

数据结构-归并排序和快速排序

归并排序，快速排序

Posted by Hzy on November 24, 2019

今天学了下两种用到了分治法的排序算法，归并排序和快速排序

1.归并排序

  • 归并排序思路：把一个数组分为两部分，让两部分有序，最终合并为一个有序数组的过程
  • 左边部分怎么有序呢？左边继续分成两部分，直到分割成的数组长度为1，就认为他是有序的。
  • 然后让两个有序的数组，两两合并，最终合并成为一个有序的数组
  • 右边同理
  • 最后就是，有序的左边部分和有序的右边的部分合并

代码

  • 代码中利用递归将数组分割成了两部分
  • 然后左边分割完，右边分割。
  • 当两边都分的长度为1时，开始两两合并
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

# 归并排序

# 排序且合并
def megre(l,start,end,index):
    newL= []
    leftList = l[start:index]
    rightList = l[index:end]
    for v1, v2 in zip(leftList, rightList):
        if v1 < v2:
            newL.append(v1)
            newL.append(v2)
        else:
            newL.append(v2)
            newL.append(v1)
    if len(leftList) < len(rightList):
        newL.append(*rightList[len(leftList):])
    elif len(leftList) > len(rightList):
        newL.append(*leftList[len(rightList):])

    l[start:end] = newL

def megreSort(l,start,end):

    if start == end:
        return
    else:
        index =(start+end)//2
        # 将数组切割，直到数组的长度为1
        megreSort(l,start,index)
        megreSort(l,index+1,end)
        # 将 分割的数组进行排序
        megre(l,start,end,index)

    return l

# 模拟一下 函数执行的过程
# 首先 [3,1],[2,4,5]
# [3],[1] ,[2,4,5]
# [3],[1], [2],[4,5]
# [3],[1],[2],[4],[5]
# 两两排序合并
# [1,3] [2],[4,5]
# [1,3] [2,4,5]
# [1,2,3,4,5]

print(megreSort([3,1,2,4,5],0,5))

2.快速排序

  • 快速排序思路:快速排序其实跟归并排序有点类似之处。
  • 白话说就是，对整个数组，拿一个数出来比较，将小于这个数的放到左边，大于这个数的放到右边。
  • 对左半边的数组，继续执行上面的操作，循环，直到数组不能在分为止，右边也是同样的操作。
  • 最后就能得到一个有序的数组。

可以看看这篇文章:

漫画：什么是快速排序？（完整版）

代码，递归和非递归版本

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
27
28
29
30
31
32
33
34
35
36
37
38
39

# 快速排序
# 按照基准值划分
def pivotPartition(l,left,right):
    index = left
    pivot = l[left] # 第一个元素为基准值
    # 右指针中找到比基准值小的数
    while left <right:
        while l[right] > pivot and left <right:  # 当右指针的元素 > 基准值,指针数减少1
            right -=1
        # 左指针中找到比基准值大的数字
        while l[left] <= pivot and left < right: # 当左指针的元素 > 基准值,指针数增加1
            left +=1
        # 交换这两个数字
        l[left],l[right] = l[right],l[left]
    # 当left == right时，交换基准值和left上的值
    l[left],l[index] = pivot,l[left]
    return left

def quickSort(l,left,right):
    if left >= right:
        return
    else:
        pivot = pivotPartition(l,left,right)
        quickSort(l,left,pivot-1)
        quickSort(l,pivot+1,right) # 这里指针指向 增量的后一位，要不然会报错栈溢出
    return l

print(quickSort([3,1,2,5,4],0,4))

# 非递归版本
def quickSort2(l,left,right):
    pivot = pivotPartition(l,left,right)
    while pivot>left:
        pivot =  pivotPartition(l,left,pivot-1)
    while pivot<right:
        pivot = pivotPartition(l,pivot+1,right)
    return l
l = [3,1,2,5,4,7,4,-1]
print(quickSort2(l,0,len(l)-1))
FEATURED TAGS
Python 数据结构