排序笔记2----归并，快排

2018-08-04  本文已影响0人  小碧小琳

六、归并排序

参考归并排序

最易于理解的白话：首先考虑下如何将将二个有序数列合并

比如，13跟24678合并。
1跟2比较，1小于2，那么list.append(1)。
3跟2比较，2小于3，那么list.append(2)
3跟4比较，3小于4，那么list.append(3)
left数列已经为空，那么就把right的数列都append到list中。

那么归并排序呢，一样的道理。但是不一样的地方就是，一开始不是两个有序list，而是是一整个无序list，为了满足“两个，有序”的要求，我们分两步：

其中递归的地方就是，上面的第二步中，上面的

代码思路

把一个list一路递归到每个list长度为1的时候，返回两个长度为2的有序list，合并后再返回两个长度为4的有序list，再合并。。一直到返回len(nums)的list。

代码来自知乎A2N
运行过程

具体细节图片参考归并排序

代码实现：

def MergeSort(lists):
    #递归结束条件，list小于等于1
    if len(lists) <= 1:
        return lists
    #把无序list分成两个部分
    num = int( len(lists)/2 )
    #对这两个无序list，递归调用归并排序函数
    left = MergeSort(lists[:num])
    right = MergeSort(lists[num:])
    #对于返回的两个有序list，调用merge函数
    return Merge(left, right)


#按照合并两个有序list的论述，定义一个合并函数
def Merge(left,right):
    r, l=0, 0
    result=[]
    while l<len(left) and r<len(right):
        if left[l] < right[r]:
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1
    result += right[r:]
    result += left[l:]
    return result
print(MergeSort([1, 2, 3, 4, 5, 6, 7, 90, 21, 23, 45]))

七、堆排序

对于堆的理解，参考树4，二叉树的特例——堆

三、快速排序

3.1、大致理解快速排序的方针

3.1.1、以中间数为基准，先把一个list分成两个大小两个区域

对于一个无序list，取index为0的元素作为中间数，然后执行分区函数，让比中间数小的点都在中间数左边，比中间数大的点都在中间数右边。此时得到了一个看似有序其实无序的list：

3.1.2、对上述的两个区域，递归调用快速排序

我们对这两个无序的list再次调用分区函数，此时会得到四个看似有序而又无序的list，接着调用分区函数，直到最终list长度为2时，再调用一次分区函数，那么一定是左边有序并且小于右边，因此此时所有的子列表都是有序的，那么此时一整个list也就是一个有序的list了。

3.2、快速排序的细节问题

3.2.1、分区函数怎么分区

我们取index为0的元素为中间数，left指针代表其指向的元素应该在中间数左边，即小于中间数；right代表其指向的元素应该在中间数右边，大于中间数。而实际情况不会这么完美，于是我们进行下面这样的操作，如下图：

图1

无序列表为nums，对于我们要执行分区函数的列表调用分区函数：

图2

移动过程中发现位置错误的元素，继续调换位置。
直到最后这种情况：

图3

此时左指针指向77停止，右指针指向31停止，但是此时左指针大于右指针了，说明他俩指向了两人已经工作过的区域了，此时不用再调换位置了。直接替换右指针指向元素与中间数，就能得到一个，已经分好区域的list了。左右两个区域。

3.2.2、怎么调用递归函数使得能够继续分区

上面我们其实会得到两个小的无序的区域，以什么划分这两个区域呢（注意中间数不用再掺和进去了），就是中间元素的index啊。于是：

3.3、代码思路：

3.3.1、定义快排函数quickSort()

根据上面所说，递归调用的函数，需要传入三个参数，一个是列表nums，还有两个是用来划分需要快排区域的参数first和last。
而一开始我们只能传入一个参数就是列表nums。
因此我们定义一个辅助函数quickSortHelper()，既能用来递归调用快排操作，又能传入三个参数。
初始化中，传入的三个参数分别是nums，first = 0，last = len(nums) - 1

3.3.2、定义递归调用函数partition()

此函数传入三个参数，列表nums，以及用来划分要对列表进行快排操作的区域指针，first和last
执行此函数后，函数会将要分区的列表区域进行分区。

3.3.3、定义分区函数

此函数传入三个参数，列表nums，以及用来划分要对列表进行快排操作的区域指针，first和last

图片理解参考 快速排序

代码实现:


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 rightmark >= leftmark and alist[rightmark] >= pivotvalue:
            rightmark = rightmark -1

        #左指针大于右指针时，done为True，结束循环
        if rightmark < leftmark:
            done = True
        #经过上面的指针操作以后，如果左指针还是小于右指针，则替换二者指向元素
        else:
            temp = alist[leftmark]
            alist[leftmark] = alist[rightmark]
            alist[rightmark] = temp

    #done为True，结束循环，替换中间元素与右指针指向元素的位置
    temp = alist[first]
    alist[first] = alist[rightmark]
    alist[rightmark] = temp
    ##返回此时中点的位置，用于下次递归分类划分左右部分
    return rightmark

alist = [54,26,93,17,77,31,44,55,20]
quickSort(alist)
print(alist)
上一篇 下一篇

猜你喜欢

热点阅读