排序算法是一种经过特定的算法因式将一组或多组数据按照既定形式进行从头排序的办法。经过排序，咱们能够得到一个新的序列，该序列遵循一定的规矩并展现出一定的规律。经过排序处理后的数据能够更方便地进行筛选和计算，然后大大提高了计算功率。因而，把握排序算法是每个程序员的基本功之一。

今日咱们将具体解说一些与冒泡排序、快速排序和刺进排序相关的leetcode真题。

冒泡排序

字如其名，冒泡排序是一种算法，它类似于水中的泡泡逐渐上升，经过逐轮比较和交流，最终使每个元素按照次序摆放。

看一下今日的标题：给定一个数组 nums，编写一个函数将一切 0 移动到数组的末尾，一起坚持非零元素的相对次序。请注意 ，必须在不复制数组的情况下原地对数组进行操作。进阶：你能尽量削减完成的操作次数吗？

示例 1:
  输入: nums = [0,1,0,3,12]
  输出: [1,3,12,0,0]

首要，这道题属于简略标题，一眼基本就能够看出来如何完成。只要遇到零就往后移动，并且冒泡排序最常见的就是双层for循环即可，然后保护两个变量随时进行数据交流。可是这种都知道的处理方案，咱们不去完成。咱们来完成一下进阶要求，即尽可能削减操作次数来完成数据的转换。

咱们能够考虑一下，因为nums数组中不一定只有一个零，所以在操作数据时，咱们将一切零都看作一个整体，只移动榜首个零即可，其他的零都不用动。下面是图解：

咱们在这里写一下相关的Python完成代码。在这段代码中，咱们运用了三元表达式的一种变种：(假，真)[条件]

from typing import List
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i = 0
        j = 0
        while j < len(nums) :
            if nums[j] == 0 :
                i = (j,i)[nums[i] == 0]
            elif  nums[i] == 0 :
                nums[i] = nums[j]
                nums[j] = 0
                i = i + 1
            j = j + 1
solution = Solution()
nums = [0,1,0,3,12]
solution.moveZeroes(nums)
print(nums)

快速排序

快速排序的重要之处在于挑选适宜的规范数字，经过将大于和小于该数字的元素分成两部分。随后，咱们不断重复这个操作。通常情况下，我倾向于运用递归办法，每次分割完后再调用以基准数字为规范的办法，直到只剩下一个元素停止。在今日的例题中，咱们将讨论快速排序的运用。

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需求找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。你必须设计并完成时刻杂乱度为 O(n) 的算法处理此问题。

通常情况下，快速排序的时刻杂乱度是无法到达O(n)的，并且在最坏情况下可能会到达O(n2)的时刻杂乱度。因而，为了满足标题要求，咱们需求对挑选排序进行一些改善。

咱们先来看下简略完成：

from typing import List
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return sorted(nums)[len(nums) - k]
solution = Solution()
nums = [3,2,3,1,2,4,5,5,6]
k = 4
print(solution.findKthLargest(nums, k))        

但是，这样的完成肯定无法满足O(n)的时刻杂乱度要求。因而，咱们需求进行进一步优化。假如我榜首反应是下降时刻杂乱度，我可能会考虑献身空间杂乱度，然后逐渐进行优化。根据这个，我写出来了递归。

from typing import List
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def quickSelect(nums,k) -> int:
            # 挑选一个作为基准
            result = nums[0]
            # 将数组分为三部分，大于、等于、小于
            big ,equal,small = [],[],[]
            # for循环不要排序，一进行排序就会添加时刻杂乱度。
            for num in nums:
                if num > result:
                    big.append(num)
                elif num < result:
                    small.append(num)
                else :
                    equal.append(num)
            # 阐明在big中
            if k <= len(big):
                return quickSelect(big,k)
            if k > len(big) + len(equal):
                return quickSelect(small,k - len(big) - len(equal))
            return result
        return quickSelect(nums,k)
solution = Solution()
nums = [3,2,3,1,2,4,5,5,6]
k = 4
print(solution.findKthLargest(nums, k))

为了更加方便大家了解，我还特意制作了一个简略的图例，以便于更直观地阐明。

刺进排序

刺进排序（Insertion Sort）是一种简略直观的排序算法。其基本思想是将待排序序列分为已排序和未排序两部分。每次从未排序部分取出一个元素，将其刺进到已排序部分的适宜方位，直到一切元素都被刺进到已排序部分停止。这种排序办法相对其他杂乱的排序算法而言，完成简略、简单了解，适用于小规模数据的排序。

咱们来看下正题：

给你一个整数数组 nums，请你将该数组升序摆放。

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

咱们先来简略完成一个刺进排序：

from typing import List
class Solution:
    def insertSort(self,index: int,nums: List[int]):
        temp = nums[index]
        while index > 0 and temp < nums[index-1] :
            nums[index] =  nums[index-1]
            index = index - 1
        nums[index] = temp
    def sortArray(self, nums: List[int]) -> List[int]:
        for i in range(1,len(nums)):
            self.insertSort(i,nums)
        return nums
insert = Solution();
nums = [5,1,1,2,0,0]
print(insert.sortArray(nums))

为了更好地阐明，我简略地绘制了一个图例。请注意，数字的次序应根据实际情况而定，而不是根据图中的显现次序来确认。图中主要展示了交流和比较的过程。

但是，刺进排序明显不是最优的算法，因为它的运行时刻超过了约束。主要原因是刺进排序的时刻杂乱度仍然偏高。那么，我来提出一种简略的优化办法，主要是削减比较和交流操作的消耗。咱们知道，假如数组的前面部分已经是有序的，那么咱们能够首要考虑运用二分查找来削减比较次数。咱们来完成一下：

from typing import List
class Solution:
    def findIndex(self,begin:int, end: int,temp: int,nums: List[int]):
        if begin <= end :
            return begin
        mid = (begin + end ) / 2
        if nums[mid] > temp:
            findIndex(begin,mid,temp,nums)
        else :
            findIndex(mid,end,temp,nums)   
    def insertSort2(self,index: int,nums: List[int]):
        temp = nums[index]
        small = self.findIndex(0,index,temp,nums)
        while index > small and temp < nums[index-1] :
            nums[index] =  nums[index-1]
            index = index - 1
        nums[index] = temp
    def sortArray(self, nums: List[int]) -> List[int]:
        for i in range(1,len(nums)):
            self.insertSort2(i,nums)
        return nums
insert = Solution();
nums = [5,1,1,2,0,0]
print(insert.sortArray(nums))

原本我觉得这次的使命应该能够顺利经过，可是却没能满足时刻约束要求，结果仍是超时了。接下来，为了优化交流次数，我需求考虑运用刺进排序的高级变体——希尔排序。

希尔排序

希尔排序是一种优化的刺进排序算法，它的重点是经过添加距离来削减元素之间的比较次数。比较于传统的刺进排序一次比较一个元素，希尔排序经过距离的设定，能够一次比较多个元素。为了更好地了解这个过程，我简略地画了一张图。

假如选用之前的刺进排序算法，将数字0移动到前面将需求进行屡次比较和交流操作，这将导致功率较低。而假如运用希尔排序并添加距离，能够防止对中间数字进行比较和交流操作，然后有效削减了所需的比较和交流次数。

咱们来简略完成一下算法：

from typing import List
class Solution:
    def insertSort3(self,index: int,nums: List[int],gap: int):
        temp = nums[index]
        while index-gap >= 0 and temp < nums[index-gap] :
            nums[index] =  nums[index-gap]
            index = index - gap
        nums[index] = temp
    def sortArray(self, nums: List[int]) -> List[int]:
        gap = len(nums) // 2
        while gap > 1 :
            for i in range(gap,len(nums)):
                self.insertSort3(i,nums,gap)
            gap = gap // 2
        return nums
insert = Solution();
nums = [5,1,1,2,0,0]
print(insert.sortArray(nums))

总算经过了这道标题，从代码完成上来看，与刺进排序比较，它多了一些变量，但仍然很简单了解。但是，由于数组前面不再是肯定有序的，咱们需求放弃运用二分查找。