Java排序算法_选择排序

选择排序的基本操作就是每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。算法不稳定,O(1)的额外的空间,比较的时间复杂度为O(n^2),交换的时间复杂度为O(n),并不是自适应的。在大多数情况下都不推荐使用。只有在希望减少交换次数的情况下可以用。

基本思想

n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果:

①初始状态:无序区为R[1..n],有序区为空。

②第1趟排序

在无序区R[1..n]中选出关键字最小的记录R[k],将它与无序区的第1个记录R[1]交换,使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

……

③第i趟排序

第i趟排序开始时,当前有序区和无序区分别为R[1..i-1]和R(1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

这样,n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。

代码实现

public class chooseSort {


public static void main(String[] args) {

 int[] a = {25,89,42,16,12,36};

 int min = 0;

 int tmp = 0;

 for(int i=0;i<a.length;i++){

  min = i;//

       System.out.println("第一组设定下标min为:"+min);

 

  for(int j=i+1;j<a.length;j++){

   if(a[min]>a[j]) {

    System.out.print(a[min]+"比"+a[j]+"要大     ");

    min = j;//记下较大数位置,再次比较,直到最大

   }

       System.out.println("现在较小数为"+a[min]+",下标为min:"+min+"     ");

  }

 

  if(i!=min){

   tmp = a[i];

   a[i] = a[min];

   a[min] = tmp;

   System.out.print(a[i]+"与"+a[min]+"进行了交换,现在较大值为:a[min]:"+a[min]+" 要换的值的下标为:"+min+"     ");

  }

  System.out.println(Arrays.toString(a));

 }

 for(int i=0;i<a.length;i++)

  System.out.print(a[i]+" ");

}

}


代码二:按顺序排序

public static void main(String args[]) {
 int[] array = { 14, 5, 86, 4, 12, 3, 51, 13, 11, 2, 32, 6 };  // 创建一个初始化的一维数组array
 int keyValue;      // 表示最小的元素值
 int index;       // 表示最小的元素值的下标
 int temp;       // 中间变量
 System.out.println("未排序的数组:");
 for (int i = 0; i < array.length; i++) {  // 遍历array数组中的元素
  System.out.print(" " + array[i]);  // 输出数组元素
  if ((i + 1) % 5 == 0)    // 每5个元素一行
   System.out.println();
 }
 for (int i = 0; i < array.length; i++) {  // 使用选择排序法的核心
  index = i;
  keyValue = array[i];
  for (int j = i; j < array.length; j++)
   if (array[j] < keyValue) {
    index = j;
    keyValue = array[j];
   }
  temp = array[i];
  array[i] = array[index];
  array[index] = temp;
 }
 System.out.println("\n使用选择排序法后的数组:");
 for (int i = 0; i < array.length; i++) {   // 遍历排好序的array数组中的元素
  System.out.print(" " + array[i]);   // 输出数组元素
  if ((i + 1) % 5 == 0)
   System.out.println();    // 每5个元素一行
 }
}
}


选择排序法与冒泡排序法一样,最外层循环仍然要执行n-1次,其效率仍然较差

上一篇:Andrew Ng机器学习公开课笔记 -- 支持向量机


下一篇:普林斯顿大学算法公开课笔记——插入排序