526互联

Data structure - Sort & quick sort 小结及leetcode相关题目

发布时间 2023-10-21 02:52:50作者: Johnson_强生仔仔

Sort 主要有以下几种常见的sort, 面试中最有可能考的是quick sort， 关于k largest or 什么相关的。

  • Bubble sort
  • Insertion sort
  • Merge sort
  • Quicksort
  • Selection sort
  • Counting sort
  • Bucket sort

 

1. Bubble sort, 可以理解为每一次找最大的值放在最后面，然后再找第二个最大的值放在倒数第二个位置上，以此类推。

T: O(n ^ 2) ; S: O(1)

def bubbleSort(self, nums):
    n = len(nums)
    for i in range(n - 1, 0, -1): # from n - 1 to 1, because j starts from 0
        swapped = False
        for j in range(0, i):
            if nums[j] > nums[j + 1]:
                swapped = True
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
        if not swapped:
            return

 

2. Merge Sort, 将array 分成两半，然后在merge两个sorted array， 每次merge是O(n)的operation, 然后总共可以分O(lgn) 次，所以

T: O(n * lgn). S: O(n) worst case

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        if n < 2: return nums
        mid = n //2
        left= self.sortArray(nums[:mid])
        right = self.sortArray(nums[mid:])
        return self.mergeTwoLists(left, right)
    

    def mergeTwoLists(self, nums1, nums2):
        n1, n2 = len(nums1), len(nums2)
        i1, i2 = 0, 0
        nums = []
        while i1 < n1 and i2 < n2:
            if nums1[i1] < nums2[i2]:
                nums.append(nums1[i1])
                i1 += 1
            else:
                nums.append(nums2[i2])
                i2 += 1
        while i1 < n1:
            nums.append(nums1[i1])
            i1 += 1
        while i2 < n2:
            nums.append(nums2[i2])
            i2 += 1
        return nums