Task 03： 數(shù)組排序

數(shù)組排序第一天打卡，附上學(xué)習(xí)鏈接

1 學(xué)習(xí)內(nèi)容

1.1 冒泡排序（Bubble Sort）

冒泡排序法通過相鄰元素之間的比較與交換，使值越小的元素位置越往前，值越大的元素越往后，類比水底的氣泡向上冒的形態(tài)。

算法步驟：

• （1）將序列中第1和2個元素進行比較，若前者大于后者，則交換位置，否則不交換；

• （2）依次類推，直到第n-1和n個元素比較交換為止。一趟排序下來，最大的元素就會位于序列的第n個位置上；

• （3）此后，對前n-1個元素同樣操作，將n-1個元素中值最大的放置在n-1的位置上；

• （4）重復(fù)，直至某一趟排序過程中不出現(xiàn)元素交換位置的動作，排序結(jié)束。

算法分析：

• 最好的情況是，初始時序列呈升序狀態(tài)，只需要n-1次元素之間的比較，并且無移動，可結(jié)束排序。此時，算法時間復(fù)雜度為O(n)；

• 最差的情況是，初始時序列是逆序狀態(tài)/最小值在尾，則需要n-1趟排序，總共進行n(n-1)/2次比較。因此，算法平均時間復(fù)雜度為O(n²)；

• 冒泡排序，需要移動次數(shù)較多，時間效率最低。適合于數(shù)據(jù)量較小/初始狀態(tài)基本有序的情況；

• 元素的比較交換是在相鄰元素之間進行，不會該表值相同元素的相對位置，因此冒泡排序是一種穩(wěn)定排序法。

代碼實現(xiàn)：

def bubbleSort(arr):
    for i in range(len(arr)):
        for j in range(len(arr)-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

1.2 選擇排序（Selection Sort）

選擇排序在每一趟排序中，從剩下未排序元素中選擇一個最小的元素，與未排好序的元素最前面的那個元素交換位置。

算法步驟：

• （1）設(shè)置整型變量i，作為排序次數(shù)的計算，也作為第i趟排序時，未排序的元素的第1個元素的位置；

• （2）設(shè)置整型變量min_i，記錄未排序的n-i+1個元素中值最小元素的位置；

• （3）每一趟排序開始，先令min_i = i（即暫定第i個元素為最小值，之后比較交換）；

• （4）第i趟排序比較結(jié)束時，其中真正的值最小元素為下標(biāo)min_i對應(yīng)的元素。此時，若min_i == i時，則不用進行交換。

算法分析：

• n個元素的序列，選擇排序需要n-1趟；

• 原始序列升序，移動次數(shù)最少，為0次；原始序列逆序，移動次數(shù)最多，為3(n-1)次【3是交換arr[i]和arr[min_i]的執(zhí)行次數(shù)】；

• 無論序列中元素的初始排列狀態(tài)如何，第i趟排序要找出值最小元素都需要進行n-i次元素之間的比較。因此，整個排序過程需要進行的元素之間的比較次數(shù)都相同，為n(n-1)/2次，算法的時間復(fù)雜度為O(n²)；

• 由于值最小元素與未排好序的元素中第1個元素的交換動作是在不相鄰的元素之間進行的，因此很有可能會改變值相同元素的前后位置，因此選擇排序法是一種不穩(wěn)定的排序方法。

代碼實現(xiàn)：

def selectionSort(arr):
    for i in range(len(arr) - 1):
        min_i = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_i]:
                min_i = j
        if i != min_i:
            arr[i], arr[min_i] = arr[min_i], arr[i]
    return arr

1.3 插入排序（Insertion Sort)

將整個序列切分為兩部分：前i-1個元素是有序序列，后n-i+1個元素是無序序列。每一次排序，將無序序列的首元素，在有序序列中找到相應(yīng)的位置并插入。

算法步驟：

• （1）將第一個元素作為一個有序序列，將2~n-1個元素作為無序序列；

• （2）從頭至尾一次掃描無序序列，將掃描到的每個元素插入到有序序列的適當(dāng)位置上。

算法分析：

• 有n個元素的序列，插入排序方法一共要進行n-1趟排序；

• 對于插入排序算法，整個排序過程只需要一個輔助空間tmp；

• 當(dāng)原始序列升序，對應(yīng)的每個i值只進行一次元素之間的比較，因而總的比較次數(shù)最少，為n-1，且不需要移動元素（記錄）；

• 當(dāng)原始序列逆序，則對應(yīng)的每個i值都要進行i-1次元素之間的比較，總的比較次數(shù)最多，為n(n-1)/2；

• 當(dāng)原始序列隨機，且參加排列的序列中元素可能出現(xiàn)的各站排列的概率相同，則取平均值作為比較次數(shù)，約為n²/4，即算法的時間復(fù)雜度為O(n²)；

• 插入排序算法屬于穩(wěn)定性排序方法。

代碼實現(xiàn)：

def insertionSort(arr):
    for i in range(1, len(arr)):
        tmp = arr[i]
        j = i
        while j > 0 and arr[j-1] > tmp:
            arr[j] = arr[j-1]
            j -= 1
        arr[j] = tmp
    return arr

2 練習(xí)題目

2.1 劍指Offer 45、把數(shù)組排成最小的數(shù) **

題目描述：輸入一個非負(fù)整數(shù)數(shù)組，將所有數(shù)字拼接起來排成一個數(shù)，打印出拼接出的所有數(shù)字中最小的一個。 樣例1：輸入為[10, 2]，輸出為"102"； 樣例2：輸入為[3, 30, 34, 5, 9]，輸出為“3033459”。

解題思路：排序判斷規(guī)則為，如果x+y > y+x，則x應(yīng)該在y的左邊，反之亦然。

class Solution:
    def minNumber(self, nums: List[int]) -> str:
        def quick_sort(left, right):
            if left >= right:
                return
            i, j = left, right
            while i < j:
                while strs[j] + strs[left] >= strs[left] + strs[j] and i < j:
                    j -= 1
                while strs[i] + strs[left] <= strs[left] + strs[i] and i < j:
                    i += 1
                strs[i], strs[left] = strs[left], strs[i]
                quick_sort(left, i-1)
                quick_sort(i+1, right)
                
        strs = [str(num) for num in nums]
        quick_sort(0, len(strs) - 1)
        return ''.join(strs)

class Solution:
    def minNumber(self, nums: List[int]) -> str:
        def sort_rule(x, y):
            a, b = x + y, y + x
            if a > b: return 1
            elif a < b: return -1
            else: return 0
        
        strs = [str(num) for num in nums]
        strs.sort(key = functools.cmp_to_key(sort_rule))  # amazing
        return ''.join(strs)

2.2 0283 移動零 *

題目描述：給定一個數(shù)組nums，編寫一個函數(shù)將所有0移動到數(shù)組的末尾，同時保持非零元素的相對順序。 樣例1：輸入為[0, 1, 0, 3, 12]，輸出為[1, 3, 12, 0, 0]。

解題思路：對0計數(shù)，刪除0，并在末尾添加滿足數(shù)量的0。

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = nums.count(0)

        for i in range(n):
            nums.remove(0)
        
        nums.extend([0] * n)

神奇的思路之雙指針，哈哈哈哈。

左指針指向當(dāng)前已經(jīng)處理好的序列的尾部，右指針指向待處理序列的頭部。右指針不斷向右移動，每次右指針指向非零數(shù)，則將左右指針對應(yīng)的數(shù)交換，同時左指針右移。

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        left = right = 0
        while right < n:
            if nums[right] != 0:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
            right += 1

2.3 0912 排序數(shù)組 **

題目描述：將一個整數(shù)數(shù)組nums，實現(xiàn)升序排列。 樣例1：輸入為nums=[5, 2, 3, 1]，輸出為[1, 2, 3, 5]； 樣例2：輸入為nums=[5, 1, 1, 2, 0, 0]，輸出為[0, 0, 1, 1, 2, 5]。

解題思路：用上述三種方法排序。

hahahaha，都超時了，偷懶用個list內(nèi)置函數(shù)吧~~

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        nums.sort()
        return nums

day2打卡: day2鏈接
day3打卡: day3鏈接
day4打卡: day4鏈接