本文實例為大家分享了C++選擇排序算法的具體代碼，供大家參考，具體內容如下
基本思想
每一趟從無序區中選出最小的元素，順序放在有序區的最后，直到全部元素排序完畢。
由于選擇排序每一趟總是從無序區中選出全局最小（或最大）的元素，所以適用于從大量元速度中選擇一部分排序元素。例如，從10000個元素中選出最小的前10位元素。
直接選擇排序
1.排序思路
從第i趟開始，從當前無序區arr[i…n-1]中選出最小元素arr[k]，將它與有序區的最后一個元素，也就是無序區的第一個元素交換。每趟排序后，有序區增加一個元素，無序區減少一個元素，且有序區中所有元素均小于等于無序區中的元素。經過n-1趟排序后，無序區只剩下arr[n-1]一個元素，它必然為整個序列的最大值，故無需再排。
2.排序算法
void SelectSort(int *arr, int size){ if (arr == NULL) return; //1.找到無序區中最小的元素和它的下標 int i, j; for (i = 0; i < size - 1; i++) { int k = i; for (j = i + 1; j < size; j++) { if (arr[j] < arr[k]) { k = j; } } //2.把最小的元素與無序區第一個元素交換 //swap(arr[i], arr[k]); if (k != i) { int tmp = arr[i]; arr[i] = arr[k]; arr[k] = tmp; } }}3.算法分析
由于要選出最小值，故無序區中的每個元素都要參與比較，所以無論初始數據序列的狀態如何，總的比較次數為：
C = n-1 +n-2+n-3+…+2+1 = n(n-1)/2
故直接選擇排序的時間復雜度為O(N^2)，空間復雜度為O(1)。直接選擇排序是一個不穩定的算法。例如，排序序列為{5，3，2，5，4，1}，第一趟排序后得到{1，3，4，5，4，5}，兩個5的相對位置發生了變化。
4.優化版本
每趟排序同時找出最大值和最小值，把最小值放在序列的左邊，最大值放在序列的右邊，然后同時縮小左右排序范圍。
//優化，每趟排序同時找出最大值和最小值void SelectSort1(int *arr, int size){ if (arr == NULL) return; int left = 0; int right = size - 1; while (left < right) { for (int i = left; i < right; i++) { if (arr[i] < arr[left]) swap(arr[i], arr[left]); if (arr[i] > arr[right]) swap(arr[i], arr[right]); } left++; right--; }}堆排序
1.排序思路
堆排序是一種樹形選擇排序方法，在排序過程中，將arr[0…n-1]看成一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親節點和孩子結點之間的內在關系，在當前無序區中選擇最大（或最小）的元素。
下標從0開始，節點i的兩個孩子節點可表示為2*i+1、2*i+2。
2.排序算法
void AdjustDown(int *arr, int size, int parent){ int child = 2 * parent + 1; while (child < size) { if (child + 1 < size && arr[child] < arr[child + 1]) { child++; } if (arr[parent] < arr[child]) { swap(arr[parent], arr[child]); parent = child; child = 2 * parent + 1; } else break; }}void HeapSort(int *arr, int size){ if (arr == NULL) return; //1.建立初始堆（此處為大堆） int root; for (root = (size / 2)-1; root >= 0; root--) { AdjustDown(arr, size, root); } //2.將arr[0]與arr[n-1]交換，然后再調整arr[0...n-1]，使其滿足大堆，如此反復操作 for (root = size-1; root >= 1; root--) { swap(arr[root], arr[0]); AdjustDown(arr, root, 0); }}3.算法分析
堆排序的時間主要由建堆和反復調整堆這兩部分的時間構成，由于可以把堆看成完全二叉樹的結構，所以堆排序的時間復雜度為O(N*lgN)，空間復雜度為O(1)，堆排序算法不穩定。
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持武林網。
新聞熱點
疑難解答
圖片精選
