简单排序---选择排序（常见经典排序算法）

Bertha 。 2023-10-14 12:25 37阅读 0赞

>  **基本思路：** 
> 
> 1.   **首先在未排序序列中**   **找到最小（大）元素**   **，存放到排序序列的起始位置（第一趟）** 
> 2.   **再从**   **剩余未排序元素中继续寻找最小（大）元素**   **，然后放到已排序序列的末尾（第二趟）** 
> 3.   **重复第二步，直到所有元素均排序完毕** 
> 
> 编程步骤：
> 
> 用嵌套循环进行排序，先在外层循环中设置两个变量（最小值和最小值索引位置），再在内层循环中遍历数组并交换位置，最后在外层循环判断是否交换值。
> 
>  **平均时间复杂度：O（ ![n^\{^\{2\}\}][n_2] ）**

> 例:设有关键字序列为:7,4,-2,19,13,6，直接选择排序的过程如下图所示。  
> 初始记录的关键字:7 4 -2 19 13 6  
> 第一趟排序:-2 4 7 19 13 6  
> 第二趟排序:-2 4 7 19 13 6
> 
> 第三趟排序:-2 4 6 19 13 7  
> 第四趟排序:-2 4 6 7 13 19
> 
> 第五趟排序:-2 4 6 7 13 19
> 
> 第六趟排序:-2 4 6 7 13 19

![21205834_uvmC.gif][]

import java.util.Arrays;
    
    public class SelectSort {
        public static void main(String[] args) {
            int[] arr = {3, 45, 78, 99, 45, 11, 64, 55, 52, 11, 18, 66, 17, 37, 199, 120, 54, 49};
            System.out.println("未排序数组："+ Arrays.toString(arr));
            selectSort(arr);
            System.out.println("已排序数组："+Arrays.toString(arr));
        }
    
        public static void selectSort(int[] arr){
            for (int i =0;i<arr.length-1;i++){//选择排序的次数
                int min = arr[i];//min：最小值
                int mindex = i;//mindex：最小值所在的索引
                for (int j =i+1;j< arr.length;j++){//每趟排序遍历一次未排序的元素
                    if (min > arr[j]){//如果min大于被比较的这个元素，就交换一下min和mindex
                        min = arr[j];
                        mindex = j;
                    }
                }
                if (i != mindex){//如果i不等于mindex，说明arr【i】不是最小值，就得将arr【i】和最小值交换位置
                    arr[mindex] = arr[i];
                    arr[i] = min;
                }
            }
        }
    }

[n_2]: https://static.oschina.net/uploads/img/202206/21205833_l8iZ.jpg
[21205834_uvmC.gif]: https://static.oschina.net/uploads/img/202206/21205834_uvmC.gif