（python）排序算法

一、冒泡排序

1、冒泡排序实现思路

需要两层循环，外层循环控制总共循环几次，内层循环控制交换的次数（注意索引超界的问题）。
外层第一次循环，内层第一次循环，将第一个元素（y）与第二个元素（y+1）进行比较，如果第一个数比第二个数大，就交换两个数的位置，内层第二次循环，然后将大的数（也就是交换后的第二个元素）与第三个元素进行比较，将大数往后交换，依次类推...内层循环结束，这时最大数就跑到了最后面；开始外层第二次循环，依次类推...
需要注意的是索引超界的问题，当外层第一次循环结束后，最大数已经排到了最后面，下次循环最大数就不需要做比较了，那么下次循环内层循环就要减掉1，以免索引超界，以此类推...也就是随着x的增加，内层循环减掉x就行了。

2、代码实现

 def sort_nums(nums):

     length_nums = len(nums)

     for x in range(length_nums):

         for y in range(length_nums - x - ):

             if nums[y] > nums[y + ]:

                 nums[y], nums[y + ] = nums[y + ], nums[y]

     return nums

 print(sort_nums([, , , , , , , ]))

优化的地方：

是否有这样一种情况，每次比较后，都没有交换位置，也就是说这组数据正好是一组有序的数据？那我们可以加一个开关来进行标记，如果内层循环一次都没有交换，那么说明这组数据是有序的，也就没有必要进行循环耗费资源了。

 def sort_nums(nums):

     length_nums = len(nums)

     for x in range(length_nums):

         flag = False

         for y in range(length_nums - x - 1):

             if nums[y] > nums[y + 1]:

                 nums[y], nums[y + 1] = nums[y + 1], nums[y]

                 flag = True

         if not flag:

             break

     return nums

 print(sort_nums([3, 1, 56, 632, 13, 51, 123, 3]))

二、简单选择排序

1、简单选择排序实现思路

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

2、代码实现

 def sort_nums(nums):

     length = len(nums)

     for x in range(length):

         maxindex = x

         for y in range(x+1, length):

             if nums[maxindex] < nums[y]:

                 maxindex = y

         if x != maxindex:

             nums[maxindex], nums[x] = nums[x], nums[maxindex]

     return nums

 nums = [234, 2, 41, 5, 346, 347, 5367, 3, 24]

 print(sort_nums(nums))

优化的地方：

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

 def sort_nums(nums):

     length = len(nums)

     for x in range(length//2):

         maxindex = x

         minindex = -x -1

         minorigin = minindex

         for y in range(x+1, length-x):

             if nums[maxindex] < nums[y]:

                 maxindex = y

             if nums[minindex] > nums[-y-1]:

                 minindex = -y-1

         if x != maxindex:

             nums[maxindex], nums[x] = nums[x], nums[maxindex]

             if x == minindex or x == length+minindex:  # 如果最小值的索引交换过了，就要更新最小值的索引

                 minindex = maxindex

         if minorigin != minindex and nums[minorigin] != nums[minindex]:

             nums[minindex], nums[minorigin] = nums[minorigin], nums[minindex]

     return nums

 nums = [234, 2, 41, 5, 346, 347, 5367, 3, 24]

 print(sort_nums(nums))

三、插入排序

1、插入排序实现思路

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

2、代码实现

 def sort_nums(nums):

     nums = [0] + nums

     length = len(nums)

     for x in range(2, length):

         nums[0] = nums[x]

         j = x - 1

         if nums[j] > nums[0]:

             while nums[j] > nums[0]:

                 nums[j + 1] = nums[j]

                 j -= 1

             nums[j + 1] = nums[0]

     return nums[1:]

 nums = [214, 35, 1, 51, 35, 13, 41, 5, 4365, 32]

 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、代码实现

 def quick_sort(arr, low, high):

     if low < high:

         # 传入参数，通过Partitions函数，获取k下标值

         k = partitions(arr, low, high)

         # 递归排序列表k下标左侧的列表

         quick_sort(arr, low, k - 1)

         # 递归排序列表k下标右侧的列表

         quick_sort(arr, k + 1, high)

 def partitions(arr, low, high):

     left = low

     right = high

     # 将最左侧的值赋值给参考值k

     k = arr[left]

     # 当left下标小于right下标的情况下，此时判断二者移动是否相交，若未相交，则一直循环

     while left < right:

         # 当left对应的值小于k参考值，就一直向右移动

         while arr[left] <= k:

             left += 1

         # 当right对应的值大于k参考值，就一直向左移动

         while arr[right] > k:

             right -= 1

         # 若移动完，二者仍未相遇则交换下标对应的值

         if left < right:

             arr[left], arr[right] = arr[right], arr[left]

     # 若移动完，已经相遇，则交换right对应的值和参考值

     arr[low] = arr[right]

     arr[right] = k

     # 返回k值

     return right

 arr = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8]

 quick_sort(arr, 0, len(arr) - 1)

 print(arr)

巴特西

（python）排序算法

一、冒泡排序

1、冒泡排序实现思路

2、代码实现

二、简单选择排序

1、简单选择排序实现思路

2、代码实现

三、插入排序

1、插入排序实现思路

2、代码实现

四、快速排序

1、快四排序实现思路

2、代码实现

最新文章

热门文章