排序

(52条消息) 排序算法时间复杂度、空间复杂度、稳定性比较_潘建南的博客-CSDN博客_排序算法的时间复杂度

• 时间复杂度记忆-

1. 冒泡、选择、直接 排序需要两个for循环，每次只关注一个元素，平均时间复杂度为O(n²)）（一遍找元素O(n)，一遍找位置O(n)）
2. 快速、归并、希尔、堆基于二分思想，log以2为底，平均时间复杂度为O(nlogn)（一遍找元素O(n)，一遍找位置O(logn)）

• 稳定性记忆-“快希选堆”（快牺牲稳定性）

1. 排序算法的稳定性：排序前后相同元素的相对位置不变，则称排序算法是稳定的；否则排序算法是不稳定的。

常规排序

插入排序

数列前面部分看为有序，依次将后面的无序数列元素插入到前面的有序数列中，初始状态有序数列仅有一个元素，即首元素。在将无序数列元素插入有序数列的过程中，采用了逆序遍历有序数列，相较于顺序遍历会稍显繁琐，但当数列本身已近排序状态效率会更高。

时间复杂度：$O(N^2)$ ，空间复杂度：$O(1)$，稳定

折半插入排序

选择排序

选择排序从小到大排序：一开始从0n-1区间上选择一个最小值，将其放在位置0上，然后在1n-1范围上选取最小值放在位置1上。重复过程直到剩下最后一个元素，数组即为有序。

时间复杂度：$O(N^2)$，空间复杂度：$O(1)$，不稳定

希尔排序

希尔排序是插入排序改良的算法，希尔排序步长从大到小调整，第一次循环后面元素逐个和前面元素按间隔步长进行比较并交换，直至步长为1，步长选择是关键。

时间复杂度：$O(nlog n)$，空间复杂度：$O(1)$，不稳定

快速排序

快速排序从小到大排序：在数组中随机选一个数（默认数组首个元素），数组中小于等于此数的放在左边部分，大于此数的放在右边部分，这个操作确保了这个数是处于正确位置的，再对左边部分数组和右边部分数组递归调用快速排序，重复这个过程。

时间复杂度：$O(nlog n)$，空间复杂度：$O(nlogn)$ 不稳定​

归并排序

归并排序，采用是分治法，先将数组分成子序列，让子序列有序，再将子序列间有序，合并成有序数组。

算法描述：

1. 把长度为n的输入序列分成长度 n/2的子序列；
2. 对两个子序列采用归并排序；
3. 合并所有子序列。

时间复杂度：$O(nlog n)$，空间复杂度：$O(n)$， 稳定

插入排序实现

def insertSort(self,nums):
    n = len(nums)
    for i in range(n):
        temp = nums[i]
        j = i-1 
        # 向前搜索比当前位置大的值，并腾出个位置给当前的值
        while j>-1 and nums[j]>temp:
            nums[j+1] = nums[j]
            j -= 1
        nums[j+1] = temp
    return nums

折半插入排序实现

def halfInsetSort(self,nums):
    '''
    折半插入
    '''
    n = len(nums)
    for i in range(n):
        temp = nums[i]
        low = 0
        high = i - 1

        while low <= high:
            mid = low+(high-low) // 2
            print(nums[low],nums[mid],nums[high])
            # 如果中间值比temp大，说明temp应该在低区间
            # 这样可以找到右边界的位置
            if nums[mid] > temp:
                high = mid - 1
            else:
                low = mid + 1
        j = i - 1
        while j > high:
            nums[j+1] = nums[j]
            j -= 1
        nums[high+1] = temp
    return nums

希尔排序实现

def shellSort(self,nums):
    n = len(nums)
    dk = n // 2
    while dk > 0:
        for i in range(dk,n):
            # 如果当前组比前面的组小，则交换
            if nums[i] < nums[i-dk]:
                temp = nums[i]
                j = i - dk
                # 向前找交换的位置
                while j > -1 and temp < nums[j]:
                    nums[j+dk] = nums[j]
                    j -= dk
                nums[j+dk] = temp
        dk = dk // 2
    return nums

快速排序实现

def quickSort(self,nums,l,r):
    low,high = l,r

    if low < high:
        temp = nums[low]

        while low < high:
            # 从后向前找到比标识变量小的值
            while low < high and nums[high] >= temp:
                high -= 1
            nums[low] = nums[high]

            # 从前向后找到比标识变量大的值
            while low < high and nums[low] < temp:
                low += 1
            nums[high] = nums[low]

        nums[low] = temp
        self.quickSort(nums,l,low)
        self.quickSort(nums,low+1,r)
        
    return nums

选择排序实现

def selectSort(self,nums):
    n = len(nums)
    for i in range(n-1):
        min = i
        # 在剩下的找出比当前的还小的值
        for j in range(i,n):
            if nums[j] < nums[min]:
                min = j
        if min != i:
            nums[i],nums[min] = nums[min],nums[i]
    return nums

归并排序实现

def mergeSortInOrder(self,left:list,right:list):
    res = []

    i = 0
    j = 0 
    while i < len(left) and j < len(right):
        if left[i] < right[i]:
            res.append(left[i])
            i += 1
        else:
            res.append(right[j])
            j += 1
    res += left[i:]
    res += right[j:]
    return res

def mergeSort(self,nums):
    if len(nums)<=1:
        return nums
    mid = len(nums) >> 1 # 右移运算符

    left = self.mergeSort(nums[:mid])
    right = self.mergeSort(nums[mid:])
    return self.mergeSortInOrder(left,right)

15. 三数之和

参考题解：(51条消息) Leetcode: 15. 三数之和_starflyyy的博客-CSDN博客

1.将数组排序 2.定义三个指针，i，j，k。遍历i，那么这个问题就可以转化为在i之后的数组中寻找nums[j]+nums[k]=-nums[i]这个问题，也就将三数之和问题转变为二数之和—（可以使用双指针）

class Solution:
    def threeSum(self, nums: list):
        nums = sorted(nums)
        n = len(nums)
        res = []

        for i in range(n-2):
            if nums[i] > 0 : break
            # 去重
            if i > 0 and nums[i] == nums[i-1]:
                continue

            target = -nums[i] # a
            left = i+1        # b
            right = n - 1     # c

            while left < right:
                if nums[left] + nums[right] == target:
                    res.append([nums[i],nums[left],nums[right]])

                    # left += 1 这里可以不用加
                    right -= 1 # 考虑到边界情况先减1
                    while left < right and nums[left] == nums[left-1]:
                        left += 1
                    while left < right and nums[right] == nums[right+1]:
                        right -= 1
                elif nums[left] + nums[right] < target:
                    left += 1
                else:
                    right -= 1
        return res

16. 最接近的三数之和

参考自评论区

class Solution:
    def threeSumClosest(self, nums: list, target: int) -> int:
        nums = sorted(nums)
        n = len(nums)
        res = []
        span = 0 # 最大的间隔，间隔是绝对值
        print(span)
        for i in range(n):
            
            # if i > 0 and nums[i-1]== nums[i]:continue
            
            left = i+1
            right = n-1

            while left<right:
                t =  target - nums[i] - nums[left] - nums[right]
                if span == 0:
                    res.append(target-t)
                    span = abs(t)
                if abs(t) <= span: # 说明当前的间隔比现在的间隔小
                    # print("--")
                    span = abs(t)
                    res.append(target-t)
                
                # 向最接近的地方靠近
                if nums[i]+nums[left]+nums[right] == target:    
                    return target
                elif nums[i]+nums[left]+nums[right] < target:
                    left += 1
                else:
                    right -= 1
        # print("--",res)
        return res[-1]