1。冒泡排序冒泡排序（BubbleSort）是一种稳定排序。它的基本思想是：遍历待排序的列，依次比较，顺序不对则交换。如果从头遍历，把大的交换到后面，结果是数据越大下沉，也可以叫“下沉排序”；如果从末尾向前遍历，将较小的交换到前面，结果是越小的数据往上浮，这就是“冒泡排序”这个名字的由来。冒泡排序比较简单，python实现如下：defbubble_sort(array):length=len(array)foriinrange(0,length):#这一轮遍历只是意味着整个排序需要一个最大值轮数j=length-1#本例从后面遍历，演示“浮泡排序”whilej>=i:#每轮遍历只需要剩下的未排序序列，前i个元素已经有序（也就是说整个下标小于i的元素已经有序）ifarray[j]=i:#每轮遍历只需要剩余的相对未排序的序列，而第一个i个元素已经有序（也就是说整个序列中下标小于i的元素都已经有序）ifarray[j]0andarray[j-1]>temp_value:array[j]=array[j-1]#是把第j-1个元素往回插入一个位置j-=1#最后第j个位置是需要插入temp_value的位置array[j]=temp_value4.归并排序归并排序（MergeSort）是一种稳定排序。归并排序采用D&C（分而治之）策略。首先将待排序序列分解为有序序列（空序列或者只包含一个元素的序列都可以看作有序序列），然后将各个有序序列合并，最后得到一个完整的有序序列。defmerge_sort(array):iflen(array)<=1:#基线条件，此时序列为有序序列，分解停止条件returnarray#分解待排序序列mid=len(array)//2left=merge_sort(array[:mid])#递归调用自身，直到子序列有序，即达到上面的基线条件right=merge_sort(array[mid:])#合并有序子序列returnmerge(left,right)defmerge(left,right):"""合并左、右、左、右为有序序列"""result=[]#结果集left_pointer=0#指向左的指针，初始指向的第一个元素leftright_pointer=0#指向右的指针，初始指向右首元素#开始比较左首元素和右首元素，#哪边元素小，放哪边结果的元素，移动当left_pointer=hi:returnpivot=partition(array,lo,hi)_quick_sort(array,lo,pivot-1)#左半排序_quick_sort(array,pivot+1,hi)#对右半部分排序defpartition(array,lo,hi):pivot=array[lo]#随机选择一个标准值left=lo+1right=hiwhileTrue:whilearray[left]=hi:breakwhilearray[right]>pivot:right-=1ifright<=lo:breakifleft>=right:#当左右指针重合时，退出breakarray[left],array[right]=array[right],array[left]array[lo],array[right]=array[right],array[lo]#将引用值放在相应位置returnright
