【DS】排序算法之选择排序(Selection Sort)
2024-10-19 07:36:54
一、算法思想
选择排序是一种简单直观的排序算法。它的工作原理如下:
1)将序列分成两部分,前半部分是已经排序的序列,后半部分是未排序的序列;
2)在未排序序列中找到最小(大)元素,放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
二、算法示意图
图中阴影部分是未排序的序列,黄色部分是排序好的序列。第一行是待排序的初始序列,最后一行是排好序的序列。
从第一行中选择出最小的元素1,将其和未排序序列的第一个元素交换,从而形成第二行。第二行从阴影部分找到最小的元素2,将2和阴影部分的第一个元素8交换,形成第三行。其实这个过程和冒泡排序非常相似,只是如何将下一个元素移动到排序序列的最末端的方式不一样。如此继续下去,就可以完成序列排序。
三、Java代码
//@wiki
public class SelectionSort extends Sort{
public static void sort(int[] array) {
int temp;
int min;
for (int index = 0; index < array.length - 1; index++) {
printArray(array);
min = index;
for (int next = index + 1; next < array.length; next++) {
if (array[next] < (array[min])) {
min = next;
}
}
temp = array[index];
array[index] = array[min];
array[min] = temp;
}
}
}
算法简单,不解释。
四、算法复杂度
选择排序的算法复杂度很好分析,因为从代码来看,其算法复杂度与初始序列无关,假设初始序列元素的个数为n,则算法复杂度为O(n^2),因为第10行会执行n*(n-1)/2。因此选择排序的最优/最差/平均时间复杂度都是O(n^2)。
空间复杂度非常容易,由代码可以看出来,只需要一个位置temp用于交换即可,因此是O(1)。
最新文章
- Java 中类型转换
- The Singleton pattern
- 1055: [HAOI2008]玩具取名
- hibernate.cfg.xml 配置(摘录)
- 【转】Nginx系列(三)--管理进程、多工作进程设计
- Android开发之Handler
- 一个美国小券商的生存之道Tradestation
- 【UML九种图系列】之如何利用三层来绘制类图、时序图?
- CSS知识点:清除浮动
- mac 上面安装mysql-python
- JVM堆内存设置
- [NOI 2014]魔法森林
- Hibernate与JPA的区别是什么
- THUWC2019 游记
- javascript--实现几个简单的操作
- koa2入门使用总结
- selenium-获取一组数组进行操作(七)
- 第一章 mysql的体系结构与存储引擎
- C++与Java,C#的异同(一):值,地址,引用
- 垃圾wps弹出,现在连关闭按钮都不给了