選擇排序的基本思想為：每一趟（例如第i趟）在后面的n-i+1（i=1,2,3，…...，n-1）個待排序元素中選取關鍵字最小的元素，作為有序序列的第i個元素，直到n-1趟做完，待排序元素只剩下一個，就不用選了，序列也排序完畢。選擇排序主要有簡單選擇排序和堆排序，下面分別就這兩種排序算法進行討論。

1.簡單選擇排序

???????? 從上面選擇排序的思想中可以很直觀的得出簡單選擇排序的算法思想：假設排序列表為L[1……n]，第i趟排序從L[i……n]中選擇關鍵字最小的元素與L(i)交換，每一趟排序可以確定一個元素的最終位置，這樣經過n-1排序就可以使得整個列表有序。

具體實現的代碼如下：

1 #include<iostream> 2 using namespace std; 3 4 //聲明打印輔助函數 5 void printArray(int array[], int length); 6 //聲明簡單選擇排序函數 7 void SimpleSelectSort(int array[], int length); 8 9 int main() 10 { 11 int array[] = { 12, 3, 6, 4, 27, 9 }; 12 int length = sizeof(array) / sizeof(*array); 13 14 cout << "排序前序列為：" << endl; 15 printArray(array, length); 16 17 SimpleSelectSort(array, length); 18 cout << endl << "簡單選擇排序后序列為：" << endl; 19 printArray(array, length); 20 cout << endl; 21 system("pause"); 22 return 0; 23 } 24 25 void printArray(int array[], int length) 26 { 27 for (int i = 0; i < length; i++) 28 { 29 if (i == length - 1) 30 cout << array[i]; 31 else 32 cout << array[i] << ","; 33 } 34 } 35 36 //簡單選擇排序函數 37 void SimpleSelectSort(int array[], int length) 38 { 39 for (int i = 0; i < length - 1;i++) 40 { 41 int min = i; 42 for (int j = i + 1; j < length;j++) 43 { 44 if (array[min] > array[j]) 45 { 46 min = j; 47 } 48 } 49 if (min != i) 50 { 51 int tmp = array[min]; 52 array[min] = array[i]; 53 array[i] = tmp; 54 } 55 } 56 }

2.堆排序

堆排序中的幾個操作而是解釋如下：

（1）建堆

???????? 堆排序的關鍵是建堆，對初始序列建堆，就是一個反復篩選的過程。n個結點的完全二叉樹，最后一個結點是n/2個結點的孩子。對n/2個結點為根的子樹篩選（對于大根堆：若根結點的關鍵字小于左右子女中的較大者，則對其進行交換），使該子樹成為堆，最后依次對各結點（n/2-1~1）為根的子樹進行篩選，看該結點是否大于其左右子結點的值，若不是，則將左右子結點中較大值與之交換，交換后可能破壞下一級的堆，于是繼續采用上述方法構造下一級的堆，直到已該結點為根的子樹構成堆為止。反復利用上述篩選策略，直到根結點。建議大家動手操作一下，加深理解。

（2）插入：先將新結點放在堆的末端，再對這個新結點執行向上調整操作。

（3）刪除：先將堆的最后一個元素和堆頂元素進行交換，此時對根結點進行向下調整操作。

堆排序具體實現代碼如下：

1 #include<iostream> 2 using namespace std; 3 4 /************************************************************************/ 5 /* 本文的array中的物理位置與邏輯位置一致，0號位置留出供后序操作使用 */ 6 /************************************************************************/ 7 8 //聲明打印輔助函數 9 void printHeapArray(int array[], int length); 10 11 //聲明堆排序函數及相關輔助函數 12 //向上調整函數 13 void AdjustUp(int array[], int k); 14 //向下調整函數 15 void AdjustDown(int array[], int k, int length); 16 //建立大根堆函數 17 void BuildMaxHeap(int array[], int length); 18 //堆排序函數 19 void HeapSort(int array[], int length); 20 21 int main() 22 { 23 int array[] = { 0, 12, 3, 6, 4, 27, 9 }; 24 int length = sizeof(array) / sizeof(*array) - 1; 25 cout << "排序前序列為：" << endl; 26 printHeapArray(array, length); 27 28 HeapSort(array, length); 29 cout << endl << "堆排序后序列為：" << endl; 30 printHeapArray(array, length); 31 cout << endl; 32 system("pause"); 33 return 0; 34 } 35 36 void printHeapArray(int array[], int length) 37 { 38 for (int i = 1; i <= length; i++) 39 { 40 if (i == length ) 41 cout << array[i]; 42 else 43 cout << array[i] << ","; 44 } 45 } 46 47 //向上調整函數 48 void AdjustUp(int array[], int k) 49 { 50 //k為向上調整的結點，在這里也是堆的元素個數 51 //1.array[0]存儲帶調整結點 52 array[0] = array[k]; 53 int i = k / 2; 54 while ((i > 0) && (array[i] < array[0])) 55 { 56 //2.開始交換元素 57 array[k] = array[i]; 58 k = i; 59 i = k / 2; 60 } 61 //3.完成元素交換 62 array[k] = array[0]; 63 } 64 65 //向下調整函數，用于插入元素 66 void AdjustDown(int array[], int k, int length) 67 { 68 array[0] = array[k]; 69 for (int i = 2 * k; i <= length; i = i * 2) 70 { 71 //取k的孩子結點中key較大的元素，特別需要注意的是 72 //這里if語句中一定要有i<length的判斷，因為若i=length，則array[i + 1]不存在 73 if (i<length && array[i] < array[i + 1]) 74 i++; 75 if (array[0]>array[i]) break; 76 else 77 { 78 array[k] = array[i]; 79 k = i; 80 } 81 } 82 array[k] = array[0]; 83 } 84 //建立大根堆函數 85 void BuildMaxHeap(int array[], int length) 86 { 87 for (int i = length / 2; i > 0; i--) 88 { 89 AdjustDown(array, i, length); 90 } 91 } 92 //堆排序函數 93 void HeapSort(int array[], int length) 94 { 95 BuildMaxHeap(array, length); 96 for (int i = length; i > 1; i--) 97 { 98 int tmp = array[i]; 99 array[i] = array[1]; 100 array[1] = tmp; 101 AdjustDown(array, 1, i - 1); 102 } 103 }

3.雜論

（1）通常如果我們需要在一大堆元素中取k個最大或最小元素時，都優先采用堆排序。

轉載于:https://www.cnblogs.com/zhiyinglky/p/4805620.html

總結

以上是生活随笔為你收集整理的数据结构之——选择排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。