前言
本文主要介绍三种较为高级的排序算法：快速排序、希尔排序以及归并排序
一、快速排序
快速排序是冒泡排序的高级版，其基本思想是每次在未排序的序列中取一个数作为基准值，把所有小于基准值的数都放在它（基准值）的左侧，把所有大于基准值的数都放在它的右侧，再递归对基准值的左右序列进行快速排序即可。
注：不稳定、O(nlogn)
快速排序的过程：
快速排序的算法：
#快速排序 num=list(map(int,input().split(' '))) （1） def QSort(left,right): （2） if(left>=right): （3） return l,r,key=left,right,num[left] （4） while l<r: while l<r and num[r]>=key: （5） r-=1 num[l]=num[r] while l<r and num[l]<key: （6） l+=1 num[r]=num[l] num[l]=key （7） QSort(left,l-1) （8） QSort(l+1,right) （9） QSort(0,len(num)-1) print(num)
算法分析如下：
（1）输入一行整数，放入列表中，作为待排序序列
（2）快速排序算法主要是左右指针在活动，我们需要设置左右指针作为参数
（3）当左指针与右指针相遇时，该位置即为基准值的最终位置（设置递归终止条件）
（4）设置左右指针，以及基准值
（5）从右往左，找比基准值小的数，放在基准值的位置（此时该位置空出）
（6）从左往右，找比基准值大的数，放在空位（此时该比基准值大的数的位置空出）
（7）当左右指针相遇，此时空出的位置即为基准值的最终位置
（8）递归对基准值左边序列进行快速排序
（9）递归对基准值右边序列进行快速排序
二、希尔排序
希尔排序是对插入排序进行优化后产生的一种排序算法，它的基本思想是：把数组内的元素按下标增量分组，对每一组元素进行插入排序后，缩小增量并重复之前的步骤。
注：不稳定、O(n*n)
希尔排序的过程：
希尔排序的算法：
#希尔排序 lst=list(map(int,input().split(' '))) （1） def ShellSort(num): （2） step=len(num)//2 （3） while step>0: （4） for i in range(step,len(num)): （5） ind=i while ind >=step and num[ind]<num[ind-step]: （6） num[ind],num[ind-step]=num[ind-step],num[ind] ind-=step step//=2 （7） return num print(ShellSort(lst))
算法分析如下：
（1）输入一行整数，放入一个列表中，作为待排序序列
（2）希尔排序函数
（3）初始增量为列表长度的一半
（4）当增量大于0时循环
（5）遍历列表，实行插入排序
（6）当ind-step>0并且num[ind-step]大于了num[ind]时，交换两者位置
（7）缩小增量，继续循环
三、归并排序
归并排序算法的思想是：把数列拆分为子数列，对子数列进行排序后，再把有序的子数列合并为完整的有序数列。
注：稳定、O(nlogn)
归并排序的过程：
归并排序的算法：
#归并排序 lst=list(map(int,input().split(' '))) (1) def MergeSort(num): if(len(num)<=1): (2) return num mid=int(len(num)/2) (3) llist,rlist=MergeSort(num[:mid]),MergeSort(num[mid:]) (4) result=[] (5) i,j=0,0 while i<len(llist) and j<len(rlist): (6) if rlist[j]<llist[i]: result.append(rlist[j]) j+=1 else: result.append(llist[i]) i+=1 result+=llist[i:]+rlist[j:] (7) return result print(MergeSort(lst))
算法分析如下：
（1）输入一行整数，放入一个列表，作为待排序序列
（2）当序列只剩一个元素时，返回（递归结束条件）
（3）每次将列表分为两部分，再分别对两部分进行排序
（4）分别对左右部分进行归并排序
（5）结果列表
（6）将排序结果放入结果列表中
（7）将剩余元素放入结果列表中
总结
本文主要介绍三种高级排序方法：快速排序、希尔排序以及归并排序，其中归并排序是稳定的排序方法，快速排序以及希尔排序都是不稳定的排序算法。
