六、归并排序
参考归并排序
最易于理解的白话：首先考虑下如何将将二个有序数列合并
- 1、这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。
- 2、然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。
比如，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，为了满足“两个，有序”的要求，我们分两步：
- 1、先把list分成left和right两个无序的部分
- 2、把这两个无序的部分，调用函数排成两个有序的部分
这里的两个无序的部分怎么排序成有序的部分呢。就是递归调用归并排序函数了。 - 3、对两个有序的部分，进行上面的merge操作即可。
其中递归的地方就是，上面的第二步中，上面的
代码思路
- 写一个对两个有序list进行归并的函数merge。传入两个有序list，返回一个合并好的list。
- 写一个递归调用自身的归并排序函数mergesort，传入一个无序list，调用merge，返回一个有序list。内容如下
1、把无序列表分成两个无序列表
2、对上面两个无序列表递归调用归并排序函数mergesort，能够返回两个有序的子列表。
3、对上一步返回的两个有序子列表，调用merge函数。
把一个list一路递归到每个list长度为1的时候，返回两个长度为2的有序list，合并后再返回两个长度为4的有序list，再合并。。一直到返回len(nums)的list。
具体细节图片参考归并排序
代码实现：
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：
- 有序体现在此时list分成了两个区域，左边的都比中间数小，右边的都比中间数大。
- 无序体现在，而这两个区域，又都是无序的list
3.1.2、对上述的两个区域，递归调用快速排序
我们对这两个无序的list再次调用分区函数，此时会得到四个看似有序而又无序的list，接着调用分区函数，直到最终list长度为2时，再调用一次分区函数，那么一定是左边有序并且小于右边，因此此时所有的子列表都是有序的，那么此时一整个list也就是一个有序的list了。
3.2、快速排序的细节问题
3.2.1、分区函数怎么分区
我们取index为0的元素为中间数，left指针代表其指向的元素应该在中间数左边，即小于中间数；right代表其指向的元素应该在中间数右边，大于中间数。而实际情况不会这么完美，于是我们进行下面这样的操作，如下图：
无序列表为nums，对于我们要执行分区函数的列表调用分区函数：
- 一开始我们选54作为中间节点，定义left指针指向index为1的元素，right指向列表的最后一个元素。左右指针开始汇合；
- 一开始左指针指向元素为26，小于54，说明这个元素的位置是正确的，则左指针加1向右移动，指向96时，这个元素位置是错误的，暂时停止left的移动
- 同理，我们移动右指针，直到找到错误的元素，为20
- 对这两个位置错误的元素，调换位置，然后再接着移动左右指针。
移动过程中发现位置错误的元素，继续调换位置。
直到最后这种情况：
此时左指针指向77停止，右指针指向31停止，但是此时左指针大于右指针了，说明他俩指向了两人已经工作过的区域了，此时不用再调换位置了。直接替换右指针指向元素与中间数，就能得到一个，已经分好区域的list了。左右两个区域。
3.2.2、怎么调用递归函数使得能够继续分区
上面我们其实会得到两个小的无序的区域，以什么划分这两个区域呢（注意中间数不用再掺和进去了），就是中间元素的index啊。于是：
- 左边的无序区域为nums[first:index-1]
- 右边的无序区域为nums[index+1,last]
于是对这两个区域再调用递归函数即可。
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
执行此函数后，函数会将要分区的列表区域进行分区。
- 1、递归结束条件是first小于last
- 2、函数改变条件，每次传入的需要排序的区域指针都会不断改变，直到first大于last截止
函数里面调用一次分区函数，返回中间数的index，用来改变下次调用递归函数的first与last。
其中左半部分区域为first，index-1.右半部分为index+1，last - 递归调用，上一步，得到递归调用的区域，直接递归调用两次快排函数即可。
3.3.3、定义分区函数
此函数传入三个参数，列表nums，以及用来划分要对列表进行快排操作的区域指针，first和last
1、用一个“大”while循环来执行错误元素换位的情况，循环结束的条件为左指针大于右指针。
2、里面再用“小”while循环来执行移动指针的情况，当指针指向元素相对中间数“正确”时，就继续执行循环移动指针。
需要用到两个while，一个控制左指针，一个控制右指针。3、当上述两个“小”while循环结束时，说明左右指针都指向了相对错误的元素，此时分为两种情况：
1、左指针小于右指针：说明此时分区工作还没结束，对两个元素进行换位（上面的图1跟图2），继续执行元素换位的“大”while。
2、左指针大于右指针：说明此时的分区工作已经结束了，对右指针指向的元素与中间数进行换位（上面的图3），并且结束最外面的while循环。4、循环结束，可以返回中间数的index了，留着下一次递归调用函数的时候使用。
图片理解参考 快速排序
代码实现:
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)
