2020資料結構-排序算法之選擇排序（簡單選擇、堆排序）

一、選擇排序（簡單選擇、堆排序）

1.簡單選擇

• 基本思想

  假設排序表為L[1…n]，在第一次取min=i,L[i]為最小元素，之後設定一個标志位j循環與L[min]進行比較，若發現L[j]<L[min]，則令

  min=j，如果min != i，就交換L[min]與L[i]的位置。

• 效率分析

  空間效率：O(1)

  時間效率：O(n·n)

  穩定性：不穩定。

  2.堆排序

• 基本思想

  是一種樹型選擇排序方法。在排序過程中，将L[1…n]視為一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的内在關系，在目前無序區中選擇關鍵字最大（最小）的元素。

• 堆的性質

  結構性：堆是一個完全二叉樹，完全二叉樹要求樹的節點從左到右排列，除最後一層外，每層節點個數都是滿的。

  堆序性：堆中每一個節點的值必須大于等于（或小于等于）其子樹中每個節點的值。對于大于等于的堆稱為大頂堆，對于小于等于的節點稱為小頂堆。

• 堆的存儲

  比較适合用數組來存儲，除根結點外，節點i的左子樹節點的下标為i2，右子節點的下标為i2+1。

• 堆的操作

  插入、删除

  

  

• 堆排序

  堆排序的過程分為兩步：1.鍵堆；2.排序

  

  排序

  

  

  

  

  （以上圖來自網絡，侵删。）

• 效率分析

  空間：O(1)

  時間：建堆時間為O(n),之後有n-1次向下調整操作，每次調整時間複雜度O(h)，在最壞和最好的情況下平均時間複雜度為O(nlog2n)。

  穩定性：不穩定。