（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 nums
10 
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 = True
10 
11         if not flag:
12             break
13 
14     return nums
15 
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] < nums[y]:
 8                 maxindex = y
 9 
10         if x != maxindex:
11             nums[maxindex], nums[x] = nums[x], nums[maxindex]
12 
13     return nums
14 
15 nums = [234, 2, 41, 5, 346, 347, 5367, 3, 24]
16 print(sort_nums(nums))

优化的地方：

既然每次循环确定了一个最大数，那么是否可以在一次循环中同时找到一个最大数和一个最小数呢？当然可以，这样循环的总次数就减少了一半，效率大大提高。

 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]:
10                 maxindex = y
11             if nums[minindex] > nums[-y-1]:
12                 minindex = -y-1
13 
14         if x != maxindex:
15             nums[maxindex], nums[x] = nums[x], nums[maxindex]
16             if x == minindex or x == length+minindex:  # 如果最小值的索引交换过了，就要更新最小值的索引
17                 minindex = maxindex
18         if minorigin != minindex and nums[minorigin] != nums[minindex]:
19             nums[minindex], nums[minorigin] = nums[minorigin], nums[minindex]
20 
21     return nums
22 
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 -= 1
12 
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<right），则二者指向的值进行交换。
如果已经相遇，则说明第一次排序结束，将arr[right]和arr[0]的值进行交换，进行后面的递归。

2、代码实现

 1 def quick_sort(arr, low, high):
 2     if low < high:
 3         # 传入参数，通过Partitions函数，获取k下标值
 4         k = partitions(arr, low, high)
 5         # 递归排序列表k下标左侧的列表
 6         quick_sort(arr, low, k - 1)
 7         # 递归排序列表k下标右侧的列表
 8         quick_sort(arr, k + 1, high)
 9 
10 
11 def partitions(arr, low, high):
12     left = low
13     right = high
14     # 将最左侧的值赋值给参考值k
15     k = arr[left]
16     # 当left下标小于right下标的情况下，此时判断二者移动是否相交，若未相交，则一直循环
17     while left < right:
18         # 当left对应的值小于k参考值，就一直向右移动
19         while arr[left] <= k:
20             left += 1
21         # 当right对应的值大于k参考值，就一直向左移动
22         while arr[right] > k:
23             right -= 1
24         # 若移动完，二者仍未相遇则交换下标对应的值
25         if left < right:
26             arr[left], arr[right] = arr[right], arr[left]
27     # 若移动完，已经相遇，则交换right对应的值和参考值
28     arr[low] = arr[right]
29     arr[right] = k
30     # 返回k值
31     return right
32 
33 
34 arr = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8]
35 quick_sort(arr, 0, len(arr) - 1)
36 print(arr)