首页 > 代码库 > 算法一之简单选择排序
算法一之简单选择排序
一、 选择排序的思想
选择排序的基本思想是:每一趟在n-i+1(i=1,2,…n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。
简单选择排序的基本思想:第1趟,在待排序记录r[1]~r[n]中选出最小的记录,将它与r[1]交换;第2趟,在待排序记录r[2]~r[n]中选出最小的记录,将它与r[2]交换;以此类推,第i趟在待排序记录r[i]~r[n]中选出最小的记录,将它与r[i]交换,使有序序列不断增长直到全部排序完毕。
二、算法实现
public void selectionSort(int[] data){ int minIndex; //最小记录下标 int temp; //临时空间 //data.length-1趟 for(int i=0;i<data.length-1;i++){ //在i到data.length-1中匹配最小记录 minIndex=i; //默认最小值为第一个记录 for(int j=i+1;j<data.length;j++){ //保存最小记录的下标 if(data[minIndex]>data[j]){ minIndex=j; } }
//最小记录不在下标i处,互交换数据 if(minIndex!=i){ temp =data[i]; data[i]=data[minIndex]; data[minIndex]=temp; } } }
三、复杂度
简单选择排序中,所需进行记录移动的操作次数较少,其最小值为“0”,最大值为3(n-1)。
然而,无论记录的初始序列如何,所需进行的关键字间的比较次数相同,均为n(n-1)/2,因此,总的时间复杂度为O(n2)。
算法一之简单选择排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。