上一篇文章咱们已经聊过「 冒泡排序 」和「 插入排序 」了,今天我们来看一看「 选择排序 」。「 选择排序 」虽然在实际应用中没有「 插入排序 」广泛,但它也是我们学习排序算法中必不可少的一种。「 冒泡排序 」和「 插入排序 」都是在两层嵌套循环中慢慢比较元素,不停的调整元素的位置。而「 选择排序 」就比较直接了,属于不出手则已,一出手,相应的元素就必须要到位,元素的位置就不会再变了。
下面我们来详细了解下一下它的逻辑。
选择排序 也是一种很简单的排序算法,它的思路也是将一组待排序的数据,分成2段,一段是“已排序”了的数据,另一段是“未排序”的数据。当然,在最开始的时候,“已排序”区段里是没有数据的。排序开始后,每次都从“未排序”的数据中取出一个最小的元素(注意,这里是取最小的元素,这一点与「 插入排序 」是不同的),然后将这个最小的元素插入到“已排序”数据中末尾元素的后面(这里其实是将这个最小元素与“已排序”数据的末尾紧邻的下一位元素进行交换),这样保持了“已排序”中的数据永远是有序的。一直这么循环的去处理,直到所有的“未排序”的数据都已交换完,则整个排序全部完成。
下面用图示例讲解一下:
从上图可以看到,初始数组是
元素 | 29 | 72 | 98 | 13 | 87 | 66 | 52 | 51 | 36 |
---|---|---|---|---|---|---|---|---|---|
下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
要对这个数组进行从小到大排序,默认初始状态是全部无序的,因此对这个数组开始遍历找最小元素。
下面我们来看一个选择排序的代码示意:
算法题:对数组arr进行从小到大的排序,假设数组arr不为空,arr的长度为n思路:采用选择排序方法
public void selectionSort(int[] arr){ int i,j; int n = arr.length; //每一次大循环都能找出剩余元素的最小值 for(i=0; i<n; i++){ //min变量是用于存放最小值的下标的,在刚开始的时候,假设位置i是最小值,初始时将i赋值给min int min = i; //子循环是用于比较大小,从i的后面一位开始遍历,遍历后面所有元素 for(j=i+1; j<n; j++){ //如果有元素小于min位的值,则将此元素的下标赋值给min if(arr[j] < arr[min]){ min = j; } } //如果min不等于i,说明刚在在子循环里,找到了最小值,则需要交换元素位置 if(min!=i){ //swap方法是用于交换数组中2个位置的值(传入数组、下标),swap方法省略不写了。 swap(arr,min,i); } }}
我们按照之前文章中讲到的排序算法评估方法来对「 选择排序 」进行一下性能评估:
以上,就是对数据结构中「 选择排序 」的一些思考,您有什么疑问吗?