排序与查找-归并与快排

[TOC]

归并排序Merge Sort

分治策略在排序中的应用，归并排序是递归算法， 思路是将数据表持续分裂为两半， 对两半分别进行归并排序

  • 递归的基本结束条件是：数据表仅有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
def mergeSort(alist):
    print("Splitting ",alist)
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i<len(lefthalf) and j<len(righthalf):
            if lefthalf[i]<righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i<len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j<len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",alist)
    
alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)

另一个归并排序代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def mergeSort(lst):
    print("Splitting ",lst)
    if len(lst)>1:
    	return lst
        
    mid = len(lst)//2
    lefthalf = lst[:mid]
    righthalf = lst[mid:]

    merged = []
    while left and right:
    	if left[0] <= right[0]:
    		merged.append(left.pop(0))
    	else: 
    		merged.append(right.pop(0))
    merged.extend(right if right else left)
    return merged

归并排序：算法分析

  • 将归并排序分为两个过程来分析： 分裂和归并

  • 分裂的过程， 借鉴二分查找中的分析结果， 是对数复杂度， 时间复杂度为O(log n)

  • 归并的过程， 相对于分裂的每个部分， 其所有数据项都会被比较和放置一次， 所以是线性复杂度， 其时间复杂度是O(n)综合考虑，每次分裂的部分都进行一次O(n)的数据项归并，总的时间复杂度是O(nlog n)

  • 最后， 我们还是注意到两个切片操作为了时间复杂度分析精确起见，可以通过取消切片操作，改为传递两个分裂部分的起始点和终止点，也是没问题的，只是算法可读性稍微牺牲一点点。

  • 我们注意到归并排序算法使用了额外1倍的存储空间用于归并

  • 这个特性在对特大数据集进行排序的时候要考虑进去

快速排序Quick Sort

​ 快速排序的思路是依据一个“中值”数据项来把数据表分为两半：小于中值的一半和大于中值的一半， 然后每部分分别进行快速排序（递归）如果希望这两半拥有相等数量的数据项，则应该找到数据表的“中位数”，但找中位数需要计算开销！要想没有开销，只能随意找一个数来充当“中值”，比如，第1个数

快速排序的递归算法“递归三要素”如下

  • 基本结束条件：数据表仅有1个数据项，自然是排好序的

  • 缩小规模：根据“中值”， 将数据表分为两半， 最好情况是相等规模的两半

  • 调用自身：将两半分别调用自身进行排序（排序基本操作在分裂过程中）

分裂数据表的目标：找到“中值”的位置，分裂数据表的手段

  • 设置左右标（left/rightmark）

  • 左标向右移动，右标向左移动

    • 左标一直向右移动，碰到比中值大的就停止
    • 右标一直向左移动，碰到比中值小的就停止
    • 然后把左右标所指的数据项交换
  • 继续移动，直到左标移到右标的右侧，停止移动，这时右标所指位置就是“中值”应处的位置，将中值和这个位置交换，分裂完成，左半部比中值小，右半部比中值大 

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
def quickSort(alist):
   quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist,first,last):
   if first<last:

       splitpoint = partition(alist,first,last)

       quickSortHelper(alist,first,splitpoint-1)
       quickSortHelper(alist,splitpoint+1,last)


def partition(alist,first,last):
   pivotvalue = alist[first]

   leftmark = first+1
   rightmark = last

   done = False
   while not done:

       while leftmark <= rightmark and \
               alist[leftmark] <= pivotvalue:
           leftmark = leftmark + 1

       while alist[rightmark] >= pivotvalue and \
               rightmark >= leftmark:
           rightmark = rightmark -1

       if rightmark < leftmark:
           done = True
       else:
           temp = alist[leftmark]
           alist[leftmark] = alist[rightmark]
           alist[rightmark] = temp

   temp = alist[first]
   alist[first] = alist[rightmark]
   alist[rightmark] = temp


   return rightmark
   
alist = [54,26,93,17,17,77,31,44,55,20]
quickSort(alist)
print(alist)

快速排序：算法分析

  • 快速排序过程分为两部分： 分裂和移动如果分裂总能把数据表分为相等的两部分，那么就是O(log n)的复杂度；而移动需要将每项都与中值进行比对，还是O(n), 综合起来就是O(nlog n)；而且， 算法运行过程中不需要额外的存储空间。

  • 但是， 如果不那么幸运的话， 中值所在的分裂点过于偏离中部， 造成左右两部分数量不平衡

  • 极端情况， 有一部分始终没有数据， 这样时间复杂度就退化到O(n2)还要加上递归调用的开销（比冒泡排序还糟糕）

参考：

https://www.bilibili.com/video/BV1VC4y1x7uv?p=59