Python快速排序和归并排序

　　快速排序（Quicksort）
　　快速排序，是每次找一个数字（一般是列表的第一个元素）作为中间值，将小于这个中间值的元素都放在左边，比这个中间值大的放在右边。然后，对左边和右边的子序列进行递归操作，即可实现排序。只有一个元素的序列是有序的。
　　将列表中第一个元素设定为基准数字，赋值给mid变量，然后将整个列表中比基准小的数值放在基准的左侧，比基准到的数字放在基准右侧。然后将基准数字左右两侧的序列在根据此方法进行排放。定义两个指针，low指向最左侧，high指向最右侧。然后对最右侧指针进行向左移动，移动法则是，如果指针指向的数值比基准小，则将指针指向的数字移动到基准数字原始的位置，否则继续移动指针。如果最右侧指针指向的数值移动到基准位置时，开始移动最左侧指针，将其向右移动，如果该指针指向的数值大于基准则将该数值移动到最右侧指针指向的位置，然后停止移动。如果左右侧指针重复则，将基准放入左右指针重复的位置，则基准左侧为比其小的数值，右侧为比其大的数值。
　　首先，对于第一个元素进行操作。调整后的列表中，该元素左边的元素都比它小，右边的元素都比它大：alist〔3，8，5，7，6，9，2，1，4，6，3，3，2〕使用重复值更严谨defquicksort（alist）：left0第一个元素下标rightlen（alist）1最后一个元素下标循环过后的序列中，要确保小于等于基准值的数字在基准值右侧，大于基准值的数在其左侧whileleftright：先偏移right，此时基准值3位于left对应的位置whileleftright：ifalist〔right〕alist〔left〕：right1如果right对应的值比基准值大，不需要操作，比较下一个数字else：如果right对应的值比基准值小（或等于），则将其与基准值交换位置alist〔right〕，alist〔left〕alist〔left〕，alist〔right〕left1因为原来基准值的位置left的元素已经检查过了，不需要重复检查，所以直接去下一个元素即可breakwhileleftright：先偏移left，此时基准值3位于right对应的位置ifalist〔right〕alist〔left〕：left1如果left对应的值比基准值小或者相等，不需要操作，比较下一个数字else：如果left对应的值比基准值大，将其于基准值交换位置alist〔right〕，alist〔left〕alist〔left〕，alist〔right〕right1因为原来基准值的位置right的元素已经检查过了，不需要重复检查，所以直接去下一个元素即可breakprint（left，right）55returnalistprint（quicksort（alist））〔2，3，3，1，2，3，9，6，4，6，7，5，8〕
　　经一次操作后，左右两侧的索引都到了5的位置。接下来，我们对左右两部分的列表进行递归，即可实现快速排序：alist〔3，8，5，7，6，9，2，1，4，6，3，3，2〕defquicksort（alist，start，end）：leftstartrightendwhileleftright：whileleftright：ifalist〔left〕alist〔right〕：right1else：alist〔left〕，alist〔right〕alist〔right〕，alist〔left〕left1breakwhileleftright：ifalist〔left〕alist〔right〕：left1else：alist〔left〕，alist〔right〕alist〔right〕，alist〔left〕right1break上述为核心操作，需要将核心操作递归左右到左右子序列中ifstartleft1：结束递归条件：当左侧只剩一个元素或没有元素时quicksort（alist，start，left1）将sort作用到左侧序列中ifright1end：结束递归条件：当右侧只剩一个元素或没有元素时quicksort（alist，right1，end）将sort作用到右侧序列中returnalistquicksort（alist，0，len（alist）1）〔1，2，2，3，3，3，4，5，6，6，7，8，9〕归并排序（Mergesort）
　　归并排序采用分而治之的原理：将一个序列从中间位置分成两个序列；在将这两个子序列按照第一步继续二分下去；直到所有子序列的长度都为1，也就是不可以再二分截止。这时候再两两合并成一个有序序列即可。
　　如何合并？
　　下图中的倒数第三行表示为第一次合并后的数据。其中一组数据为48，57。该两组数据合并方式为：每一小组数据中指定一个指针，指针指向每小组数据的第一个元素，通过指针的偏移指定数据进行有序排列。排列情况如下：p1指向4，p2指向5，p1和p2指向的元素4和5进行比较，较小的数据归并到一个新的列表中。经过比较p1指向的4会被添加到新的列表中，则p1向后偏移一位，指向了8，p2不变。p1和p2指向的元素8，5继续比较，则p2指向的5较小，添加到新列表中，p2向后偏移一位，指向了7。p1和p2指向的元素8，7继续比较，7添加到新列表中，p2偏移指向NULL，比较结束。最后剩下的指针指向的数据（包含该指针指向数据后面所有的数据）直接添加到新列表中即可。
　　归并排序使用Python代码实现：alist〔3，8，5，7，6，9，2，1，4，6，3，3，2〕defmergesort（alist）：nlen（alist）递归结束条件ifn1：returnalist将序列分成左右两部分，递归排序midn2leftmergesort（alist〔：mid〕）rightmergesort（alist〔mid：〕）将指针归零leftpointerrightpointer0result〔〕用于存放排序好的结果比较指针位置的数字，较小的放到结果中，并依次移动指针whileleftpointerlen（left）andrightpointerlen（right）：ifleft〔leftpointer〕right〔rightpointer〕：result。append（left〔leftpointer〕）leftpointer1else：result。append（right〔rightpointer〕）rightpointer1将左右两边剩余的元素直接放到结果中result。extend（left〔leftpointer：〕）result。extend（right〔rightpointer：〕）将结果返回returnresultprint（mergesort（alist））〔1，2，2，3，3，3，4，5，6，6，7，8，9〕