欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java排序算法总结之选择排序

程序员文章站 2024-03-03 15:30:40
本文实例讲述了java排序算法总结之选择排序。分享给大家供大家参考。具体分析如下: 选择排序的基本操作就是每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在...

本文实例讲述了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 test { 
  public static int[] a = {10,32,1,9,5,7,12,0,4,3};
  // 预设数据数组 
  public static void main(string args[]) { 
    int i; // 循环计数变量 
    int index = a.length;// 数据索引变量 
    system.out.print("排序前: "); 
    for (i = 0; i < index - 1; i++) 
      system.out.printf("%3s", a); 
    system.out.println(""); 
    selectsort(index - 1); // 选择排序 
    // 排序后结果 
    system.out.print("排序后: "); 
    for (i = 0; i < index - 1; i++) 
      system.out.printf("%3s", a); 
    system.out.println(""); 
  } 
  public static void selectsort(int index) { 
    int i, j, k; // 循环计数变量 
    int minvalue; // 最小值变量 
    int indexmin; // 最小值索引变量 
    int temp; // 暂存变量 
    for (i = 0; i < index - 1; i++) { 
      minvalue = 32767;// 目前最小数值 
      indexmin = 0; // 储存最小数值的索引值 
      for (j = i; j < index; j++) { 
        if (a[j] < minvalue) // 找到最小值 
        { 
          minvalue = a[j]; // 储存最小值 
          indexmin = j; 
        } 
        temp = a; // 交换两数值 
        a = a; 
        a = temp; 
      } 
      system.out.print("排序中: "); 
      for (k = 0; k < index; k++) 
        system.out.printf("%3s", a[k]); 
      system.out.println(""); 
    } 
  } 
}

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

希望本文所述对大家的java程序设计有所帮助。