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

痛定思痛。 2023-09-28 08:02 17阅读 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

![f0d3850aca8234fcf9e4e206312f9b64.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://latex.csdn.net/eq?n%5E%7B%5E%7B2%7D%7D
[f0d3850aca8234fcf9e4e206312f9b64.gif]: https://img-blog.csdnimg.cn/img_convert/f0d3850aca8234fcf9e4e206312f9b64.gif