05 選擇排序 （Selection Sort）

原理：每一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個(gè)元素，存放在序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到全部待排序的數(shù)據(jù)元素排完。

void selection_sort(int arr[], int n) {for (int i = 0;i < n - 1;i++) {int temp = a[i];int t = i;for (int j = i + 1;j < n;j++) {if (a[j] < temp) {temp = a[j];t = j;} }a[t] = a[i];a[i] = temp;} }

空間效率：O(1)

時(shí)間效率：最好情況：O(N)? ?? ? ? ? ? 平均情況：O(N^2)? ? ??? ? ? ? ? ? ? ? ?最壞情況：O(N^2)

穩(wěn)定性（相同元素相對(duì)位置變化情況）：不穩(wěn)定

比較次數(shù)與初始狀態(tài)無(wú)關(guān)

06 堆排序（Heap Sort）

堆排序是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。

void heap_sort(int arr[], int n) {int i,temp;for (i = (n - 2) / 2; i >= 0; i--)percdown(arr, n, i);for (i = n - 1;i > 0;i--) {temp = arr[i];arr[i] = arr[0];arr[0] = temp;percdown(arr, i, 0);} }void percdown(int arr[], int n, int i) {int child;int x = arr[i];for (;i * 2 + 1 <= n - 1;i = child) {child = i * 2 + 1;if (child < n - 1 && arr[child + 1] > arr[child])child++;if (x >= arr[child]) break;else arr[i] = arr[child];}arr[i] = x; }

空間效率：O(1)

時(shí)間效率：最好情況：O(Nlog₂N)? ?? ? ? ? ? ? ?平均情況：O(Nlog₂N)? ?? ? ? ? ? ? ? ? ? ? ?最壞情況：O(Nlog₂N)? ?

穩(wěn)定性（相同元素相對(duì)位置變化情況）：不穩(wěn)定

轉(zhuǎn)載于:https://www.cnblogs.com/wanghao-boke/p/10424339.html

總結(jié)

以上是生活随笔為你收集整理的九大经典算法之选择排序、堆排序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。