当前位置: 移动技术网 > IT编程>开发语言>Java > Java对数组实现选择排序算法的实例详解

Java对数组实现选择排序算法的实例详解

2019年07月22日  | 移动技术网IT编程  | 我要评论

一. 算法描述
    选择排序:比如在一个长度为n的无序数组中,在第一趟遍历n个数据,找出其中最小的数值与第一个元素交换,第二趟遍历剩下的n-1个数据,找出其中最小的数值与第二个元素交换......第n-1趟遍历剩下的2个数据,找出其中最小的数值与第n-1个元素交换,至此选择排序完成。
以下面5个无序的数据为例:
56 12 80 91 20(文中仅细化了第一趟的选择过程)
第1趟:12 56 80 91 20

201641485158319.jpg (336×307)

第2趟:12 20 80 91 56
第3趟:12 20 56 91 80
第4趟:12 20 56 80 91
二. 算法分析
平均时间复杂度:o(n2)
空间复杂度:o(1)  (用于交换和记录索引)
稳定性:不稳定 (比如序列【5, 5, 3】第一趟就将第一个[5]与[3]交换,导致第一个5挪动到第二个5后面)
三. 算法实现

 
public class selectionsort { 
  public static void main(string[] args) { 
    int len = 15; 
    int[] ary = new int[len]; 
    random random = new random(); 
    for (int j = 0; j < len; j++) { 
      ary[j] = random.nextint(1000); 
    } 
    system.out.println("-------排序前------"); 
//   ary=new int[]{10,9,8,7,6,5,4,3,2,1}; //测试交换次数 
//   ary=new int[]{1,2,3,4,5,6,7,8,10,9}; //测试交换次数 
    for (int j = 0; j < ary.length; j++) { 
      system.out.print(ary[j] + " "); 
    } 
     
    selectdesc(ary); 
    selectasc(ary); 
  } 
  /* 
   * 选择排序:降序 
   */ 
  static void selectdesc(int[] ary) { 
    int comparecount = 0;//比较次数 
    int changecount = 0;//交换次数 
    int len = ary.length; 
    int maxvalueindex = -1; //记录一轮比较下来的最小值索引 
    for (int i = 0; i < len - 1; i++) { 
      maxvalueindex = i; //从0开始 
      for (int j = i + 1; j < len; j++) { 
        if (ary[maxvalueindex] < ary[j]) { 
          maxvalueindex = j; //记录较大的索引 
          comparecount++; 
        } 
      } 
//     system.out.println("minvalueindex==" + maxvalueindex); 
      if (maxvalueindex != i) {//如果跟左边的记录索引不同,则交换 
        ary[i] = ary[maxvalueindex] + (ary[maxvalueindex] = ary[i]) * 0;//一步交换 
        changecount++; 
      } 
    } 
     
    system.out.println("\n-------降序排序后------比较次数:" + comparecount + ",交换次数" + changecount); 
    for (int j = 0; j < ary.length; j++) { 
      system.out.print(ary[j] + " "); 
    } 
  } 
   
  /* 
   * 选择排序:升序 
   */ 
  static void selectasc(int[] ary) { 
    int comparecount = 0, changecount = 0; 
    int len = ary.length; 
    int minindex = -1; 
    for (int i = 0; i < len - 1; i++) { 
      minindex = i; 
      for (int j = i + 1; j < len; j++) { 
        if (ary[minindex] > ary[j]) { 
          minindex = j; //记录较小的索引 
          comparecount++; 
        } 
      } 
      if (minindex != i) {//如果跟左边的记录索引不同,则交换 
        ary[i] = ary[minindex] + (ary[minindex] = ary[i]) * 0; 
        changecount++; 
      } 
    } 
    system.out.println("\n-------升序排序后------比较次数:" + comparecount + ",交换次数" + changecount); 
    for (int j = 0; j < ary.length; j++) { 
      system.out.print(ary[j] + " "); 
    } 
  } 
} 

打印

-------排序前------ 
125 350 648 789 319 699 855 755 552 489 187 916 596 731 852  
-------降序排序后------比较次数:26,交换次数13 
916 855 852 789 755 731 699 648 596 552 489 350 319 187 125  
-------升序排序后------比较次数:56,交换次数7 
125 187 319 350 489 552 596 648 699 731 755 789 852 855 916  

如对本文有疑问, 点击进行留言回复!!

相关文章:

验证码:
移动技术网