简单介绍
基本概念
- 选择排序是一种简单直观的排序算法。
- 它先从未排序的序列中找到最小的元素，放在序列的起始位置，然后再从剩余未排序元素中继续寻找最小的元素并放在已排序序列的末尾。以此类推，直到全部待排序数据元素排完。
原理讲解
- 以41 34 19 17 2这个序列为例说明选择排序的实现原理
- 未开始遍历时，效果如下图
- 第一次遍历
从该序列中找到最小元素2，将元素2和序列起始位置的数据41交换位置，效果如下图
- 第二次遍历
从序列中未排序的元素中找到最小元素17，将元素17和已排序序列末尾元素34交换位置，效果如下图
- 第三次遍历
从序列中未排序的元素中找到最小元素19，此时元素19比已排序序列末尾元素17大且元素19的位置已比元素17的位置靠后，故元素19和元素17不需要移动位置，效果如下图
- 第四次遍历
从序列中未排序的元素中找到最小元素34，此时元素34比已排序序列末尾元素19小且元素34的位置已比元素19的位置靠后，故元素34和元素19不需要移动位置，效果如下图
- 第五次遍历
从序列中未排序的元素中找到最小元素41，此时元素41已未序列最后一个元素，故不需要比较，最终效果如下图
时间复杂度
排序算法的时间复杂度是和算法中相邻两个数据的比较次数和移动次数成正比的。具体如下：
| 数据个数 | 比较次数 | 最大移动次数 | 最小移动次数 |
|---|---|---|---|
| 1 | 0 | 0 | 0 |
| 2 | 1 | 1 | 0 |
| 3 | 3 | 2 | 0 |
| 4 | 6 | 3 | 0 |
| 5 | 10 | 4 | 0 |
| 10 | 45 | 5 | 0 |
| N | 1/2N(N-1) | (N-1) | 0 |
所以根据时间复杂度的概念，冒泡算法的时间复杂度为O(N^2)
效果展示
源码下载
- 请在公众号中回复“算法源码”即可获得十大经典排序算法源码
更多算法学习请关注我的公众号
