排序算法---简单选择排序

青旅半醒 2023-10-09 13:58 20阅读 0赞

#### 基本思想 ####

每一轮都从待排序的数据元素中选择一个最小（或最大）的元素作为排序后的新元素，新元素依次向后排列，直到所有元素都排完为止。

#### 算法分析 ####

首先要控制排序的轮数，即数据元素的长度大小n，然后是对数据元素进行遍历，每一轮选出一个最小（或最大）元素作为新元素，依次向后排列。每一轮需要比较的次数依次为n-1、n-2、...、2、1，一共（n-1)\*n/2次，比较完成后，判断所选择元素索引是否与遍历比较后结果相同，若相同则不交换，若不同需要则进行交换操作。**时间复杂度为O(n^2)。**

**举例**：对数组2,4,6,8,0,1,3,5,7进行选择排序，每次取出一个最小的元素放在前面

第1轮：从2,4,6,8,0,1,3,5,7选出0，0和2交换后得**0**,4,6,8,2,1,3,5,7

第2轮：从**0**,4,6,8,2,1,3,5,7选出1,1和4交换后得**0,1**,6,8,2,4,3,5,7

第3轮：从**0,1**,6,8,2,4,3,5,7选出2，2和6交换后得**0,1,2**,8,6,4,3,5,7,

第4轮：从**0,1,2**,8,6,4,3,5,7选出3，3和8交换后得**0,1,2,3**,6,4,8,5,7

第5轮：从**0,1,2,3**,6,4,8,5,7选出4，4和6交换后得**0,1,2,3,4**,6,8,5,7

第6轮：从**0,1,2,3,4**,6,8,5,7选出5，5和6交换后得**0,1,2,3,4,5**,8,6,7

第7轮：从**0,1,2,3,4,5**,8,6,7选出6，6和8交换后得**0,1,2,3,4,5,6**,8,7

第8轮：从**0,1,2,3,4,5,6**,8,7选出7，7和8交换后得**0,1,2,3,4,5,6,7**,8

第9轮：从**0,1,2,3,4,5,6,7**,8选出8，此时不用交换仍为**0,1,2,3,4,5,6,7,8**

即：排序结果为0,1,2,3,4,5,6,7,8

#### Java实现 ####

package sort;
      
      public class SelectionSort {
          public static void main(String[] args) {
              //测试数据
              int[] arr = {2,4,6,8,0,1,3,5,7};
              System.out.println("原始数组：");
              for (int i : arr) {
                  System.out.print(i + " ");
              }
              System.out.println();
              selectionSort(arr);//对数组进行选择排序
              System.out.println("排序后新数组为：");
              for (int i : arr) {
                  System.out.print(i + " ");
              }
          }
      
          /**
           * @MethodName selectionSort
           * @Description 选择排序
           * @param: arr
           * @Author Jiangnan Cui
           * @Date 2022/4/4 15:31
           */
          private static void selectionSort(int[] arr) {
              //外层循环控制选择排序的轮数，一共arr.length轮
              for (int i = 0; i < arr.length - 1; i++) {
                  //定义初始最小元素的下标索引，后续将此轮选出的最小元素放在该索引处
                  int min_index = i;
                  //内层循环表示在每一轮循环中进行比较，选出最小的那个元素下标，从其实索引下一个位置开始比较
                  for (int j = i + 1; j < arr.length; j++) {
                      if(arr[j] < arr[min_index]){
                          min_index = j;
                      }
                  }
                  //初始定义的最小索引与比较出的最小索引不同时，进行交换；相同时不做处理
                  if(min_index != i){
                      swap(arr,i,min_index);
                  }
              }
          }
      
      
          /**
           * @MethodName swap
           * @Description 用于对数组中的两个元素进行交换
           * @param: arr 数组
           * @param: i 待交换数组元素索引下标
           * @param: min_index 待交换数组元素索引下标
           * @Author Jiangnan Cui
           * @Date 2022/4/4 14:34
           */
          private static void swap(int[] arr, int i, int min_index) {
              int temp = arr[i];
              arr[i] = arr[min_index];
              arr[min_index] = temp;
          }
      }

**输出结果：**

原始数组：
      2 4 6 8 0 1 3 5 7
      排序后新数组为：
      0 1 2 3 4 5 6 7 8