【原】Python中几种常见的排序算法？

程序IT圈 2021-01-16

展开全文

公众号新增加了一个栏目，就是每天给大家解答一道Python常见的面试题，反正每天不贪多，一天一题，正好合适，只希望这个面试栏目，给那些正在准备面试的同学，提供一点点帮助！

小猿会从最基础的面试题开始，每天一题。如果参考答案不够好，或者有错误的话，麻烦大家可以在留言区给出自己的意见和讨论，大家是要一起学习的。

废话不多说，开始今天的题目：

问：说说Python中几种常见的排序算法？

答：大家都知道排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。

在算法中，排序算法分为冒泡排序，选择排序，插入排序，快速排序，归并排序，希尔排序，基数排序，堆排序，计数排序，桶排序等。

下面分别来说说几种常见的排序算法:

1、选择排序

选择排序其实就是取第一个数去跟后面的数比较，然后一轮之后得到最小的数在第一个，然后开始取第二个，重复之前的比较。

降序排列，代码实现如下：

# 选择排序
def selectionSort(nums):
for i in range(len(nums) - 1):
# 记录最小数的索引
        minIndex = i
for j in range(i + 1, len(nums)):
if nums[j] < nums[minIndex]:
                minIndex = j
# i 不是最小数时，将 i 和最小数进行交换
if i != minIndex:
            nums[i], nums[minIndex] = nums[minIndex], nums[i]
return nums
if __name__ == '__main__':
    nums = [1, 34, 2, 23, 23, 53, 24, 67, 44, 33, 19, 12]
    print(f'选择排序开始>待排序列表{nums}')
    sorted_nums = selectionSort(nums)
    print(f'选择排序完成>新列表{sorted_nums}')
运行后结果：
选择排序开始>待排序列表[1, 34, 2, 23, 23, 53, 24, 67, 44, 33, 19, 12]
选择排序完成>新列表[1, 2, 12, 19, 23, 23, 24, 33, 34, 44, 53, 67]

2、插入排序

插入排序原理应该是最容易理解的了，打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

# 插入排序
def insertionSort(nums):
for i in range(len(nums)):
        preIndex = i-1
        current = nums[i]
while preIndex >= 0 and nums[preIndex] > current:
            nums[preIndex+1] = nums[preIndex]
            preIndex-=1
        nums[preIndex+1] = current
return nums

if __name__ == '__main__':
    nums = [1, 34, 2, 23, 23, 53, 24, 67, 44, 33, 19, 12]
    print(f'选择排序开始>待排序列表{nums}')
    sorted_nums = insertionSort(nums)
    print(f'选择排序完成>新列表{sorted_nums}')

3、快速排序

在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，取序列的第一个元素，然后以这个元素为分组的基准，利用列表解析式使得它左边的值都比它小，右边的值都比它大。然后再分别对这些序列进行递归排序。

# 快速排序
def quicksort(arr):
if len(arr) <= 1:
return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)

if __name__ == '__main__':
    nums = [1, 34, 2, 23, 23, 53, 24, 67, 44, 33, 19, 12]
    print(f'选择排序开始>待排序列表{nums}')
    sorted_nums = quicksort(nums)
    print(f'选择排序完成>新列表{sorted_nums}')

4、冒泡排序

重复地走访过要排序的元素列，依次比较两个相邻的元素。如果顺序错误，就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

# 冒泡排序
nums = [1, 34, 2, 23, 23, 53, 24, 67, 44, 33, 19, 12]

print(f'冒泡排序(降序)开始>待排序列表{nums}')
for j in range(len(nums) - 1):
        for k in range(len(nums) - 1):
            if nums[k] < nums[k + 1]:
                nums[k], nums[k + 1] = nums[k + 1], nums[k]
print(f'冒泡排序(降序)完成>新列表{nums}')