python常见的五种排序方法_python常见的几种排序算法

一、冒泡排序

1、冒泡排序实现思路需要两层循环，外层循环控制总共循环几次，内层循环控制交换的次数(注意索引超界的问题)。

外层第一次循环，内层第一次循环，将第一个元素(y)与第二个元素(y+1)进行比较，如果第一个数比第二个数大，就交换两个数的位置，内层第二次循环，然后将大的数(也就是交换后的第二个元素)与第三个元素进行比较，将大数往后交换，依次类推...内层循环结束，这时最大数就跑到了最后面；开始外层第二次循环，依次类推...

需要注意的是索引超界的问题，当外层第一次循环结束后，最大数已经排到了最后面，下次循环最大数就不需要做比较了，那么下次循环内层循环就要减掉1，以免索引超界，以此类推...也就是随着x的增加，内层循环减掉x就行了。

2、代码实现1 def sort_nums(nums): 2     length_nums = len(nums) 3  4     for x in range(length_nums): 5         for y in range(length_nums - x - 1): 6             if nums[y] > nums[y + 1]: 7                 nums[y], nums[y + 1] = nums[y + 1], nums[y] 8  9     return nums10 11 12 print(sort_nums([3, 1, 56, 632, 13, 51, 123, 3]))

优化的地方：是否有这样一种情况，每次比较后，都没有交换位置，也就是说这组数据正好是一组有序的数据？那我们可以加一个开关来进行标记，如果内层循环一次都没有交换，那么说明这组数据是有序的，也就没有必要进行循环耗费资源了。1 def sort_nums(nums): 2     length_nums = len(nums) 3  4     for x in range(length_nums): 5         flag = False 6         for y in range(length_nums - x - 1): 7             if nums[y] > nums[y + 1]: 8                 nums[y], nums[y + 1] = nums[y + 1], nums[y] 9                 flag = True10 11         if not flag:12             break13 14     return nums15 16 17 print(sort_nums([3, 1, 56, 632, 13, 51, 123, 3]))

二、简单选择排序

1、简单选择排序实现思路需要两层循环，外层循环控制循环的总次数，内层循环控制确定最大值需要循环的次数。

外层第一次循环，首先确定一个最大数的索引位置，先假设索引0的数最大，然后内层循环对后面的数依次进行比较，每次比较都将最大的索引位置更新，最后内层循环结束，第一个最大数的索引就找出来了，然后将原来记录最大数的索引位置(maxindex)与索引0的数进行交换，第一个大数就已经排序完成，然后开始第二次外层循环，一次类推...

2、代码实现1 def sort_nums(nums): 2     length = len(nums) 3  4     for x in range(length): 5         maxindex = x 6         for y in range(x+1, length): 7             if nums[maxindex] 

优化的地方：既然每次循环确定了一个最大数，那么是否可以在一次循环中同时找到一个最大数和一个最小数呢？当然可以，这样循环的总次数就减少了一半，效率大大提高。1 def sort_nums(nums): 2     length = len(nums) 3  4     for x in range(length//2): 5         maxindex = x 6         minindex = -x -1 7         minorigin = minindex 8         for y in range(x+1, length-x): 9             if nums[maxindex]  nums[-y-1]:12                 minindex = -y-113 14         if x != maxindex:15             nums[maxindex], nums[x] = nums[x], nums[maxindex]16             if x == minindex or x == length+minindex:  # 如果最小值的索引交换过了，就要更新最小值的索引17                 minindex = maxindex18         if minorigin != minindex and nums[minorigin] != nums[minindex]:19             nums[minindex], nums[minorigin] = nums[minorigin], nums[minindex]20 21     return nums22 23 nums = [234, 2, 41, 5, 346, 347, 5367, 3, 24]24 print(sort_nums(nums))

三、插入排序

1、插入排序实现思路确定一个哨兵位置，将待比较的数插入到哨兵的位置，然后从索引为2的数开始比较，每次比较后将最大数插入到合适的位置。

2、代码实现1 def sort_nums(nums): 2     nums = [0] + nums 3     length = len(nums) 4  5     for x in range(2, length): 6         nums[0] = nums[x] 7         j = x - 1 8         if nums[j] > nums[0]: 9             while nums[j] > nums[0]:10                 nums[j + 1] = nums[j]11                 j -= 112 13             nums[j + 1] = nums[0]14 15     return nums[1:]16 17 18 nums = [214, 35, 1, 51, 35, 13, 41, 5, 4365, 32]19 print(sort_nums(nums))

四、快速排序

1、快四排序实现思路有两个指针left和right分别指向列表的第一个元素和最后一个元素，取列表中第一个元素作为参考值k。

然后left指向的元素和k进行比较，如果小于或者等于k，left就一直向右移动，直到移动到大于k的地方停下。

然后right指向的元素和k进行比较，如果大于k，right就一直向左移动，直到移动到小于k的地方停下。

此时，如果left和right还没有相遇的话(left

如果已经相遇，则说明第一次排序结束，将arr[right]和arr[0]的值进行交换，进行后面的递归。

2、代码实现1 def quick_sort(arr, low, high): 2     if low  k:23             right -= 124         # 若移动完，二者仍未相遇则交换下标对应的值25         if left