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

时间:2022-02-13 01:22:17

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

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

第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后面)
三. 算法实现

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
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] + " ");
    }
  }
}

打印

?
1
2
3
4
5
6
-------排序前------
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