数据结构(九):简单选择排序

2018-03-01 11:16:07来源:https://www.jianshu.com/p/0539d0dedf2e作者:林塬人点击

分享



通过 n-i 次元素之间的比较,从 n-i+1 个元素中选出值最小的元素,和第 i 个元素交换 (从数组中选出最小值元素与最左元素进行交换位置)
简单选择排序例子
举例:数组 int[] arr={5,2,8,4,9,1};
第一趟排序:比较 { 5 2 8 4 9 1 },1 最小,1 和 5 互换位置,排序结果 { 1 2 8 4 9 5 }
第二趟排序:比较 { 2 8 4 9 5 },2 最小,已在最后一位,位置不变
第三趟排序:比较 { 8 4 9 5 },4 最小,4 和 8 互换位置,排序结果 { 1 2 4 8 9 5 }
第四趟排序:..... { 1 2 4 5 9 8 }
第五趟排序:..... { 1 2 4 5 8 9 }

简单选择排序代码
int[] arr = new int[]{1, 3, 6, 4, 7, 8, 5, 10, 9};
// 简单选择排序
for(int i = 0; i < arr.length - 1; i++) {
int k = i;
for(int j = k + 1; j < arr.length; j++){
if(arr[j] < arr[k]){
k = j; //记下目前找到的最小值所在的位置
}
}
// 移动最小的元素至最左边
if(i != k){
int temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
}

简单选择排序时间的性能
简单选择排序的比较次数与序列的初始排序无关
假设待排序的序列有 N 个元素,则比较次数永远都是 N (N - 1) / 2
而移动次数与序列的初始排序有关,当序列正序时,移动次数最少,为 0。当序列反序时,移动次数最多,为3N (N - 1) / 2
简单排序综合的时间复杂度为 O(n²),综合来说优于冒泡排序







最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台