十大排序算法Python实现-LeetCode题解（全面精简附解释）

十大排序算法-Python实现一、LeetCode题目二、十大排序算法实现1. 冒泡排序法-优化2. 选择排序3. 插入排序4. 快速排序5. 归并排序6. 桶排序7. 计数排序8. 希尔排序9. 堆排序10. 基数排序
一、LeetCode题目

排序数组

给你一个整数数组 nums，请你将该数组升序排列。

示例 1：

输入：nums = [5,2,3,1]输出：[1,2,3,5] 示例 2：

示例 2：
输入：nums = [5,1,1,2,0,0]输出：[0,0,1,1,2,5]

提示：

1 <= nums.length <= 50000
-50000 <= nums[i] <= 50000

二、十大排序算法实现
1. 冒泡排序法-优化

class Solution:
    def bubble_sort(nums):
        for i in range(len(nums) - 1):
            flag = False  # 改进后的冒泡，设置一个交换标志位
            for j in range(len(nums) - i - 1):
                if nums[j] > nums[j + 1]:
                    nums[j], nums[j + 1] = nums[j + 1], nums[j]                    flag = True
            if not flag:
                return nums  # 这里代表计算机偷懒成功。

class Solution:
    def selection_sort(nums):
        for i in range(len(nums)):
            min_idx = i
            for j in range(i+1, len(nums)):
                if nums[min_idx] > nums[j]:
                    min_idx = j 
            nums[i], nums[min_idx] = nums[min_idx], nums[i]        return nums

从第二个元素开始和前面的元素进行比较，如果前面的元素比当前元素大，则将前面元素 后移，当前元素依次往前，直到找到比它小或等于它的元素插入在其后面。

class Solution:
    def insertion_sort(nums):
        # 第一层for表示循环插入的遍数
        for i in range(1, len(nums)):
            for j in range(i, 0,  -1):
                if nums[j] < nums[j-1]:
                    nums[j], nums[j-1] = nums[j-1], nums[j]                else:
                    break
        return nums

任意选取一个数据（通常选用数组的第一个数或最后一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。

class Solution:
    def partition(arr,low,high):
        i = (low-1)         # 最小元素索引
        pivot = arr[high]        for j in range(low,high):
        # 当前元素小于或等于 pivot
            if   arr[j] <= pivot:
                i = i+1
                arr[i], arr[j] = arr[j], arr[i]        arr[i+1], arr[high] = arr[high], arr[i+1]        return i+1
 1/3    1 2 3 下一页 尾页