排序算法---选择算法
程序员文章站
2022-07-10 21:14:05
基本介绍:选择排序也属于内部排序,是从待排序的数据中,按照指定规则选出某一元素,再按规定交换位置后达到排序的目的。排序思想:第一次从 arr[0]~arr[n-1]中选取最小值,与 arr[0]交换。第二次从 arr[1]~arr[n-1]中选取最小值,与 arr[1]交换。第三次从 arr[2]~arr[n-1]中选取最小值,与 arr[2] 交换,…。第 i 次从 arr[i-1]~arr[n-1]中选取最小值,与 arr[i-1]交换,…。第 n-1 次从 arr[n-2]~arr[n...
基本介绍:
选择排序也属于内部排序,是从待排序的数据中,按照指定规则选出某一元素,再按规定交换位置后达到排序的目的。
排序思想:
- 第一次从 arr[0]~arr[n-1]中选取最小值,与 arr[0]交换。
- 第二次从 arr[1]~arr[n-1]中选取最小值,与 arr[1]交换。
- 第三次从 arr[2]~arr[n-1]中选取最小值,与 arr[2] 交换,…。
- 第 i 次从 arr[i-1]~arr[n-1]中选取最小值,与 arr[i-1]交换,…。
- 第 n-1 次从 arr[n-2]~arr[n-1]中选取最小值, 与 arr[n-2]交换。
- 总共通过 n-1次,得到一个按排序码从小到大排列的有序序列。
思路分析:
- 初始状态 [8 3 2 1 7 4 6 5]
- 第一次交换完成后:[1 3 2 8 7 4 6 5]
- 第二次交换完成后:[1 23 8 7 4 6 5]
- 第三次交换完成后:[1 2 3 8 7 4 6 5]
- 第四次交换完成后:[1 2 3 4 7 8 6 5]
- 第五次交换完成后:[1 2 3 4 5 8 6 7]
- 第六次交换完成后:[1 2 3 4 5 68 7]
- 第七次交换完成后:[1 2 3 4 5 6 78]
说明:
- 选择排序一共有arr.lenth()-1轮排序
- 每一轮排序,又是一个循环,循环的规则:
先假定当前这个数是最小的数;
然后和后边的每个数进行比较,如果有发现有比当前更小的数,就重新确定最小的数,并得到下标;
当遍历到数组最后时,就得到本轮的最小数和下标。 - 最后进行交换
代码实现:
package DataStructures.com.test.Sort;
import java.text.SimpleDateFormat;
import java.util.Date;
/**
*
*/
public class SelectSort {
public static void main(String[] args) {
int[] arr = {101, 34, 119, 1};
System.out.println("排序前的数组~~:");
System.out.println(Arrays.toString(arr));
SelectSort(arr);
System.out.println("排序后的数组~~:");
System.out.println(Arrays.toString(arr));
}
public static void SelectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++){ //假定:最小数的下标是0,最小的数是arr[0]
int minIndex = i;
int min = arr[i];
for (int j = i+1; j <arr.length;j++){
if (min > arr[j]) {//说明我们假定的最小值不是真正的最小值
minIndex=j;//重置最小值的下标
min = arr[j];//重置最小值
}
}
//如果最小值的下标不等于i,说明最小值被重置过,进行交换
if (minIndex!=i) {
arr[minIndex] = arr[i];
arr[i] = min;
}
}
}
}
本文地址:https://blog.csdn.net/weixin_43217222/article/details/107353666
上一篇: 荐 第四章 常用API(下)
下一篇: Date日期类的使用