算法介紹

算法分類

內部排序：數據在內存里排序
外部排序：數據處理在硬盤上的排序（如數據太多沒法都讀到內存）

• 交換排序：比較兩個記錄鍵值的大小，如果這兩個記錄鍵值的大小出現逆序，則交換這兩個記錄，這樣將鍵值較小的記錄向序列前部移動，鍵值較大的記錄向序列后部移動。
• 插入排序：依次將每個記錄插入到一個已排好序的有序表中去
• 選擇排序：依次在未排序序列中找到最小元素，存放到排好序列的起始位置。

相關概念

1. 穩定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
2. 不穩定：如果a原本在b的前面，而a=b，排序之后 a 可能會出現在 b 的后面。
3. 時間復雜度：對排序數據的總的操作次數。反映當n變化時，操作次數呈現什么規律。
4. 空間復雜度：是指算法在計算機內執行時所需存儲空間的度量，它也是數據規模n的函數。

1. 冒泡排序（Bubble Sort）

1.1 思想

1. 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
2. 對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最后一對。在這一點，最后的元素應該會是最大的數。 
3. 針對所有的元素重復以上的步驟，除了最后一個。 
4. 重復步驟1～3，直至排序完成。

begin BubbleSort(list)for all elements of listif list[i] > list[i+1]swap(list[i], list[i+1])end if...

• 冒泡排序只對n個數據操作n-1輪，每輪找出最大（小）值
• 通過比較與交換相鄰兩個數，每輪將未排序序列中最大（小）值“冒泡”至列首（尾）。

1.2 python實現

def BubbleSort(lst):n = len(lst)if n < = 1:return lstfor i in range(n - 1): # 循環次數，每一輪確定一個最值for j in range(n - i - 1): # 待比較與交換的數if lst[j] > lst[j+1]: # 比較兩個相鄰的數，如果后者<前者，交換lst[j], lst[j+1] = lst[j+1], lst[j] return lst
arr = list(map(int, input().split()))
arr = BubbleSort(arr)
for i in arr:print(i, end =' ')

1.3 復雜度

• 時間復雜度：O(n²)，每輪操作O(n)，共O(n)輪。
• 空間復雜度：O(1)，額外空間開銷出在交換數據時的一個過渡空間。

1.4 穩定性

• 穩定

2. 快速排序（Quick Sort）

2.1 思想（偽代碼）

1. 從數列中挑出一個元素，稱為 “基準”（pivot）；
2. 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個分區退出之后，該基準就處于數列的中間位置。這個稱為分區（partition）操作；
3. 遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。

• 快速排序基于選擇劃分，是簡單選擇排序的優化。
• 每次劃分將數據選到基準值兩邊，循環對兩邊的數據進行劃分，類似于二分法。
• 算法的整體性能取決于劃分的平均程度，即基準值的選擇，此處衍生出快速排序的許多優化方案，甚至可以劃分為多塊。

#分區操作#
function partitionFunc(left, right, pivot)leftPointer = leftrightPointer = right - 1while True dowhile A[++leftPointer] < pivot do//do-nothing            end whilewhile rightPointer > 0 && A[--rightPointer] > pivot do//do-nothing         end whileif leftPointer >= rightPointerbreakelse                swap leftPointer,rightPointerend ifend while swap leftPointer,rightreturn leftPointerend function

#遞歸快排#
procedure quickSort(left, right)if right-left <= 0returnelse     pivot = A[right]partition = partitionFunc(left, right, pivot)quickSort(left,partition-1)quickSort(partition+1,right)    end if		end procedure

2.2 python實現

參考link

def QuickSort(lst):def partition(arr,left,right):pivot = arr[left] # 劃分參考數索引,默認為第一個數為基準數，可優化while left < right:# 如果列表后邊的數,比基準數大或相等,則前移一位直到有比基準數小的數出現while left < right and arr[right] >= pivot:right-=1# 此時right指向一個比基準數小的數,將right指向的數放去left的位置上,此時right指向的位置空著,接下來移動left找到符合條件的數放在此處arr[left] = arr[right]# 如果列表前邊的數,比基準數小或相等,則后移一位直到有比基準數小的數出現while left < right and arr[left] <= pivot:left+=1# 此時left指向一個比基準數大的數,將left指向的數放去right的位置上,此時left指向的位置空著,接下來進入下一次循環，將right找到符合條件的數放在此處arr[right] = arr[left]# 推出循環后，left和right重合，此時所致位置即為基準元素正確的位置，此時，左邊的元素都比pivot小，右邊的都比pivot大arr[left] = pivot # 將基準元素放到該位置return left # 返回基準元素位置def quicksort(arr, left, right):if left >= right:  # 遞歸退出條件return  mid = partition(arr,left,right) # 分區，得到基準元素位置# 遞歸調用快排quicksort(arr,left,mid-1) # 對基準元素左邊的子序列快排quicksort(arr,mid+1,right) # 對基準元素右邊的子序列快排# 主函數n=len(lst)if n<=1:return lstquicksort(lst,0,n-1) # 調用快排return lstif __name__ == "__main__":arr = list(map(int, input().split()))arr = QuickSort(arr)for i in arr:print(i, end =' ')

2.3 復雜度

• 時間復雜度：O(nlogn)，劃分次數O(logn)，每次劃分遍歷比較O(n)
• 空間復雜度：O(logn)，額外空間開銷出在暫存基準值，O(logn)劃分需要O(logn)個。

2.4 穩定性

• 不穩定

3.直接插入排序（Insert Sort）

3.1 思想

基本思想：依次將每個記錄插入到一個已排好序的有序表中去，從而得到一個新的、記錄數增加1的有序表

• 步驟：

1. 從第一個元素開始，該元素可以被認為已經被排好序；
2. 取出下一個元素，在已經排好序的元素序列中從后向前掃描；
3. 如果該元素（已排序）大于新元素，將該元素移到下一位置；
4. 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置；
5. 將新元素插入到該位置后；
6. 重復步驟2～5，直至最后一個元素被插入到合適的位置。

3.2 python實現

def InsertSort(lst):n = len(lst)if n <=1:return lstfor i in range(1,n):j = inum = lst[i] # 每次循環的等待插入的數while j > 0 and num < lst[j-1]: # 比較、后移，給待插入數num騰位lst[j] = lst[j-1]j = j-1lst[j] = num # 把待插入數num插到空位return lstif __name__ == "__main__":arr = list(map(int, input().split()))arr = InsertSort(arr)for i in arr:print(i, end =' ')

3.3 復雜度

• 時間復雜度：O(n²)，每輪操作O(n)次，共O(n)輪。
• 空間復雜度：O(1)，額外空間開銷出在數據移位時那一個過渡空間

3.4 穩定性

• 穩定

4. 希爾排序（Shell Sort）

4.1 思想

基本思想：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序

• 步驟

1. 選擇一個增量序列t1，t2，…，tk，其中ti>tk，tk=1
2. 按增量序列個數k，對序列進行k趟排序
3. 每趟排序，根據對應的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。
   
   圖源：link

• 希爾排序是插入排序的高效實現，減少直接插入排序移動次數。由于簡單插入排序每次插入都要移動大量數據，前后插入時的許多移動都是重復操作，若一步到位移動效率會高很多。
• 若序列基本有序，簡單插入排序只需要比較，不必做很多移動操作，效率很高。
• 希爾排序將序列按固定間隔劃分為多個子序列，在子序列中簡單插入排序，先做遠距離移動使序列基本有序；逐漸縮小間隔重復操作，最后間隔為1時即簡單插入排序。

4.2 python實現

def ShellSort(lst):def shellinsert(arr, d):n = len(arr)for i in range(d,n):j = i - dnum = arr[i]  # 記錄要插入的數while (j >= 0 and arr[j] > num):  # 從后向前，找到比其小的數的位置arr[j + d] = arr[j]  # 向后挪動j -= dif j != i - d:arr[j + d] = numn = len(lst)if n <= 1:return lstd = n // 2while d >= 1:shellinsert(lst, d)d = d // 2return lstif __name__ == "__main__":arr = list(map(int, input().split()))arr = ShellSort(arr)for i in arr:print(i, end =' ')

4.3 復雜度

• 時間復雜度：O(nlogn)，對序列劃分O(n)次，每次簡單插入排序O(logn)
• 空間復雜度：O(1)，額外空間開銷出在插入過程數據移動需要的一個暫存

4.4 穩定性

• 不穩定

5. 直接選擇排序

5.1 思想

核心思想：簡單選擇排序同樣對數據操作n-1輪，每輪找出一個最大（小）值。

• 步驟

1. 初始狀態：無序區為R[1…n]，有序區為空；
2. 第i趟排序(i=1,2,3…n-1)開始時，當前有序區和無序區分別為R[1…i-1]和R(i…n）。該趟排序從當前無序區中-選出關鍵字最小的記錄 R[k]，將它與無序區的第1個記錄R交換，使R[1…i]和R[i+1…n)分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區；
3. n-1趟結束，數組有序化了。

5.2 python實現

def SelectSort(lst):n = len(lst)if n<=1:return lstfor i in range(n-1):minIndex = ifor j in range(i+1,n): #比較一遍，記錄索引不交換if lst[j]<lst[minIndex]:minIndex = jif minIndex!=i: #按索引交換lst[minIndex],lst[i] = lst[i], lst[minIndex]return lstif __name__ == "__main__":arr = list(map(int, input().split()))arr = SelectSort(arr)for i in arr:print(i, end =' ')

5.3 復雜度

• 時間復雜度：O(²)，比較O(n)輪，每輪操作O(n)次
• 空間復雜度：O(1)

5.4 穩定性

• 穩定

6. 堆排序（Heap Sort）

6.1 思想

核心思想：堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。

• 步驟

1. 將初始待排序關鍵字序列(R1,R2….Rn)構建成大頂堆，此堆為初始的無序區；
2. 將堆頂元素R[1]與最后一個元素R[n]交換，此時得到新的無序區(R1,R2,……Rn-1)和新的有序區(Rn),且滿足R[1,2…n-1]<=R[n]；
3. 由于交換后新的堆頂R[1]可能違反堆的性質，因此需要對當前無序區(R1,R2,……Rn-1)調整為新堆，然后再次將R[1]與無序區最后一個元素交換，得到新的無序區(R1,R2….Rn-2)和新的有序區(Rn-1,Rn)。不斷重復此過程直到有序區的元素個數為n-1，則整個排序過程完成。

6.2 python實現

7. 歸并排序

7.1 思想

7.2 python實現

8. 基數排序

8.1 思想

8.2 python實現

未完待續…