排序算法歸檔

算法復(fù)雜度速查：http://www.reibang.com/p/2bae94d4ea9b

快速排序是二叉樹的前序遍歷介褥，歸并排序是二叉樹的后序遍歷

排序算法的穩(wěn)定性指的是在排序過程中捆等，能夠保證相等元素在排序后的相對(duì)位置與排序前一致哨毁。

一酗昼、穩(wěn)定排序算法

冒泡排序：
- 重復(fù)地走訪要排序的數(shù)列，一次比較兩個(gè)元素，如果它們的順序錯(cuò)誤就把它們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換玉吁，也就是說該數(shù)列已經(jīng)排序完成。
- 在這個(gè)過程中腻异，相等元素不會(huì)交換位置进副，所以是穩(wěn)定排序。
插入排序：
- 對(duì)于未排序數(shù)據(jù)悔常，在已排序序列中從后向前掃描影斑，找到相應(yīng)位置并插入曾沈。
- 當(dāng)遇到相等元素時(shí)，會(huì)插入到相等元素的后面鸥昏，不會(huì)改變相等元素的相對(duì)順序，所以是穩(wěn)定排序姐帚。
歸并排序：
- 采用分治的思想吏垮，將數(shù)列分成兩部分，分別排序后再進(jìn)行合并罐旗。
- 在合并過程中膳汪，如果兩個(gè)元素相等，會(huì)按照它們?cè)谠紨?shù)列中的順序依次放入結(jié)果數(shù)列中九秀，所以是穩(wěn)定排序遗嗽。

二车胡、不穩(wěn)定排序算法

選擇排序：
- 首先在未排序序列中找到最泻薮辍（大）元素，存放到排序序列的起始位置精置，然后都弹，再從剩余未排序元素中繼續(xù)尋找最薪吭ァ（大）元素，然后放到已排序序列的末尾畅厢。
- 每次選擇最小元素時(shí)冯痢，可能會(huì)改變相等元素的相對(duì)位置，所以是不穩(wěn)定排序框杜。
快速排序：
- 通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分浦楣，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序咪辱。
- 在分區(qū)過程中振劳，可能會(huì)改變相等元素的相對(duì)位置，所以是不穩(wěn)定排序油狂。
希爾排序：
- 也稱遞減增量排序算法澎迎，是插入排序的一種更高效的改進(jìn)版本。
- 由于多次插入排序选调，不同的步長可能會(huì)導(dǎo)致相等元素的相對(duì)位置發(fā)生變化夹供，所以是不穩(wěn)定排序。

遍歷順序

1仁堪、遍歷的過程中哮洽，所需的狀態(tài)必須是已經(jīng)計(jì)算出來的。
2弦聂、遍歷結(jié)束后鸟辅，存儲(chǔ)結(jié)果的那個(gè)位置必須已經(jīng)被計(jì)算出來氛什。

歸并排序

分治法

mergesort()：分，從中間分離array匪凉，分別排序（遞歸）枪眉，最后調(diào)用merge合并
merge()：治，將2個(gè)array合并為一個(gè)有序array再层，返回有序array
- 若2個(gè)array都還有贸铜，依次填入
- 若有一個(gè)遍歷結(jié)束，按序填入

def mergesort(arr):
    if len(arr)<=1:
        return arr
    mid = int(len(arr)/2)
    left = mergesort(arr[0:mid])
    right = mergesort(arr[mid:])
    return merge(left,right)

def merge(left,right):
    l = 0
    r = 0
    res = []
    while( l<len(left) and r < len(right)):
        if left[l]<= right[r]:
            res.append(left[l])
            l +=1
        else:
            res.append(right[r])
            r +=1
    if ( l<len(left) ):
        res.extend(left[l:])
    if ( r<len(right) ):
        res.extend(right[r:])
    return res

快速排序

快速排序的過程是一個(gè)構(gòu)造二叉搜索樹的過程聂受。 快排是不穩(wěn)定排序蒿秦。
為了避免最壞情況，引入隨機(jī) pivot蛋济。

更快的做法：
在 partition 過程中棍鳖，把 left 作為 pivot，左右同時(shí)交換碗旅，最終渡处，把l=r 后，r 和pivot（left）交換祟辟，返回 r骂蓖。

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int: 
        return self.quickselect(nums, 0, len(nums)-1, k-1)
    def partition(self, nums, left, right):
        pivot = nums[left]
        l = left+1
        r = right
        while (l <=r):
            if (nums[l]< pivot and nums[r]> pivot):
                nums[l], nums[r] = nums[r], nums[l]
                l += 1
                r -= 1
            if nums[l]>= pivot:
                l += 1
            if nums[r] <= pivot:
                r -= 1 
        nums[left], nums[r] = nums[r], nums[left]
        return r

    def quickselect(self, nums, left, right, k):
        index = self.partition(nums, left, right)
        if index==k:
            return nums[k]
        elif index<k:
            return self.quickselect(nums, index+1, right, k)
        elif index >k:
            return self.quickselect(nums, left, index-1, k )

~~做法：此算法較慢，無法通過leetcode~~
在l和r之間川尖，把較小的數(shù)換在前面登下，然后放置pivot，返回pivot的index叮喳。

把right定位pivot
從left到i之間被芳，為小于pivot的數(shù)
j遍歷left～right，如果違背馍悟，將j處的小數(shù)換到前邊i的位置畔濒。

def quicksort(arr,left,right):
    if left<right:
        if len(arr)<=1:
            return 
        idx = partition(arr,left, right)
        quicksort(arr,left,idx-1)
        quicksort(arr,idx+1,right)

def partition(arr,left,right):
    pivot = arr[right]
    index = left
    for j in range(left,right):
        if arr[j]<pivot:
            arr[i], arr[j] = arr[j], arr[i]
            index+=1
    arr[index], arr[right] = arr[right], arr[index]
    return i+1


arr = [12,1,7,3,5,6]
quicksort(arr,0,len(arr)-1)
print(arr)

quickselect算法

class Solution:
    def smallestK(self, arr: List[int], k: int) -> List[int]:
        if len(arr)==0 or k==0:
            return list()
        return self.quicksort(arr, 0, len(arr)-1, k)

    def partition(self, arr, left, right, k):
        pivot_value = arr[right]
        index = left
        for j in range(left, right):
            if arr[j] < pivot_value:
                arr[index], arr[j] = arr[j], arr[index]
                index +=1
        arr[index], arr[right] = arr[right], arr[index]
        return  index

    def quickselect(self,arr, left,right, k):
        if left==right:
            return arr[:k]
        index = self.partition(arr, left, right, k)
        if index ==k:
            return arr[:k]
        elif index<k:
            return self.quicksort(arr, index+1, right, k)
        elif index>k:
            return self.quicksort(arr, left, index-1, k)

堆排序

步驟（以升序排序?yàn)槔?/p>

構(gòu)造一個(gè)大頂堆
再將大頂堆的的頭尾元素互換（此步驟是為了模擬逐個(gè)出隊(duì)的過程）

def max_heapify(heap,heapSize,root):  # 調(diào)整列表中的元素并保證以root為根的堆是一個(gè)大根堆
    '''
    給定某個(gè)節(jié)點(diǎn)的下標(biāo)root，這個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)锣咒、左子節(jié)點(diǎn)侵状、右子節(jié)點(diǎn)的下標(biāo)都可以被計(jì)算出來。
    父節(jié)點(diǎn)：(root-1)//2
    左子節(jié)點(diǎn)：2*root + 1
    右子節(jié)點(diǎn)：2*root + 2  即：左子節(jié)點(diǎn) + 1
    '''
    left = 2*root + 1
    right = left + 1
    larger = root
    if left < heapSize and heap[larger] < heap[left]:
        larger = left
    if right < heapSize and heap[larger] < heap[right]:
        larger = right
    if larger != root:  # 如果做了堆調(diào)整則larger的值等于左節(jié)點(diǎn)或者右節(jié)點(diǎn)的值毅整，這個(gè)時(shí)候做堆調(diào)整操作
        heap[larger], heap[root] = heap[root], heap[larger]
        # 遞歸的對(duì)子樹做調(diào)整
        max_heapify(heap, heapSize, larger)


def build_max_heap(heap):  # 構(gòu)造一個(gè)堆趣兄，將堆中所有數(shù)據(jù)重新排序
    heapSize = len(heap)
    for i in range((heapSize -2)//2,-1,-1):  # 自底向上建堆
        max_heapify(heap, heapSize, i)

import random

def heap_sort(heap):  # 將根節(jié)點(diǎn)取出與最后一位做對(duì)調(diào)，對(duì)前面len-1個(gè)節(jié)點(diǎn)繼續(xù)進(jìn)行堆調(diào)整過程悼嫉。
    build_max_heap(heap)
    # 調(diào)整后列表的第一個(gè)元素就是這個(gè)列表中最大的元素艇潭，將其與最后一個(gè)元素交換，然后將剩余的列表再遞歸的調(diào)整為最大堆
    for i in range(len(heap)-1, -1, -1):
        heap[0], heap[i] = heap[i], heap[0]
        max_heapify(heap, i, 0)

# 測(cè)試
if __name__ == '__main__':
    a = [30, 50, 57, 77, 62, 78, 94, 80, 84]
    print(a)
    heap_sort(a)
    print(a)
    b = [random.randint(1,1000) for i in range(1000)]
    print(b)
    heap_sort(b)
    print(b)

python中 heapq 的使用

注意默認(rèn)為小頂堆，如果需要大頂堆蹋凝，需要用負(fù)值鲁纠。

import heapq

# 創(chuàng)建一個(gè)列表
data = [5, 7, 9, 1, 3]

# 將列表轉(zhuǎn)換為堆
heapq.heapify(data)
print("Heapified data:", data)  # 輸出: [1, 3, 9, 7, 5]

# 向堆中添加元素
heapq.heappush(data, 4)
print("After heappush(4):", data)  # 輸出: [1, 3, 4, 7, 5, 9]

# 從堆中刪除并返回最小元素
smallest = heapq.heappop(data)
print("Popped smallest element:", smallest)  # 輸出: 1
print("After heappop():", data)  # 輸出: [3, 5, 4, 7, 9]

# 獲取堆中的最小元素，但不刪除
smallest_peek = data[0]
print("Peek smallest element:", smallest_peek)  # 輸出: 3

# 從堆中刪除并返回最小元素鳍寂，推入新的元素
smallest_replaced = heapq.heapreplace(data, 2)
print("Replaced smallest element:", smallest_replaced)  # 輸出: 3
print("After heapreplace(2):", data)  # 輸出: [2, 5, 4, 7, 9]

# 獲取前 n 個(gè)最小的元素
three_smallest = heapq.nsmallest(3, data)
print("Three smallest elements:", three_smallest)  # 輸出: [2, 4, 5]

# 獲取前 n 個(gè)最大的元素
three_largest = heapq.nlargest(3, data)
print("Three largest elements:", three_largest)  # 輸出: [9, 7, 5]