系列文章目錄

?第一篇：【排序算法】①直接插入排序-CSDN博客

第二篇：【排序算法】②希爾排序-CSDN博客

第三篇：【排序算法】③直接選擇排序-CSDN博客

第四篇：【排序算法】④堆排序-CSDN博客

第五篇：【排序算法】⑤冒泡排序-CSDN博客

第六篇：【排序算法】⑥快速排序：Hoare、挖坑法、前后指針法-CSDN博客

第七篇：【排序算法】⑦歸并排序-CSDN博客

---

目錄

系列文章目錄

前言

一、直接選擇排序是什么？

算法思想

二、實現直接選擇排序

三、分析直接選擇排序

直接選擇排序的特征

與直接插入排序的區別

總結

---

---

前言

直接選擇排序比較簡單，實現起來較容易，但是直接選擇排序與直接插入排序的區別難以理清，筆者下方整理一個表格供參考。

---

一、直接選擇排序是什么？

算法思想

直接選擇排序的思想是：

每次從未排序部分選擇最小（或最大）元素，放到已排序部分的末尾。 通過不斷選擇剩余元素中的最小者來實現排序。

直接選擇排序為什么能實現排序？
很好理解，假設i=0是數組下標，n是數據個數。直接選擇排序就是簡單粗暴的從未排序的數據集中挑出最小/最大，放在第i個位置處，i++，未排序的數據個數就變成n-i個，重復直到i==n-1（數組下標）。

二、實現直接選擇排序

博主這里以升序為例：

void SelectionSort(int* a, int n)
{if (!a)return;for (int i = 0; i < n; ++i){int _min = i;for (int j = i + 1; j < n; j++){if (a[j] < a[_min])_min = j;}swap(&a[i], &a[_min]);}
}void swap(int* a, int* b)
{int temp = *a;*a = *b;*b = temp;
}

依據算法，從數據集中，挑選處特征碼最小/最大的數據放在已排序的末尾。

①_min變量用于存儲合適數據的下標。從第i號，到之后的未排數據中選擇最小或最大的數據，_min保存其下標，等內循環結束交換數據值；

②外循環，每一次循環的目的是在未排數據中尋找最小/最大的值；內循環，作用是依次拿未排數據與a[i]比較大小。

三、分析直接選擇排序

直接選擇排序的特征

1. 直接選擇排序非常好理解，但是效率不是很好，故實際中很少使用；
2. 時間復雜度：O(N^2)
3. 空間復雜度：O(1)
4. 穩定性：不穩定。

與直接插入排序的區別

直接選擇排序與直接插入排序的區別是什么？

直接選擇排序： 每次從未排序部分選擇最小（或最大）元素，放到已排序部分的末尾。 通過不斷選擇剩余元素中的最小者來實現排序。

直接插入排序： 將未排序部分的元素逐個插入到已排序部分的適當位置。 即，將元素插入到已排序序列中的正確位置，從而逐步構建有序序列。

特性	直接選擇排序	直接插入排序
基本思想	在未排序序列中選擇最小元素放入已排序序列末尾	將未排序元素插入已排序序列的合適位置
操作核心	選擇 + 交換	比較 + 移位
時間復雜度	永遠 O(n2)（任何情況）	平均 O(n2)，但有序時最優 O(n)
空間復雜度	O(1)（原地）	O(1)（原地）
穩定性	?不穩定（交換破壞順序）	穩定（保持相同元素順序）
數據敏感性	無關數據分布（固定比較次數）	強相關（有序數據效率飆升）
交換/移動次數	交換次數少（n-1次）	移動次數多（需整體移位）

---

總結

本文是【排序算法】系類第三篇，直接選擇排序較為簡單故篇幅較短。

來不及懷念直接選擇排序了，接下來登場的是常用且效率高、結構較復雜的另一種選擇排序算法：堆排序！