排序：Java实现选择排序原理及代码注释详解

梦里梦外; 2021-12-08 17:15 260阅读 0赞

## 选择排序 ##

**1.简介：**

> 选择排序是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。它的最坏、最好、平均时间复杂度均为为O(n2)，选择排序是不稳定的排序方法。

**2.算法原理：**

*  首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
 *  再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
 *  重复第二步，直到所有元素均排序完毕。

结合动态图理解一下：  
![在这里插入图片描述][20190715200345533.gif]  
（图片来源：[十大经典排序算法（动图演示）][Link 1]）

**3.代码实现：**

选择排序大体思路就是一次循环找到最小或最大的，然后放在最前或最后面。

我是在循环中找到较小的数，记录其下标，等一次循环结束后再交换。

还有一种思路是找到较小的数两数交换，一次循环结束时，可能交换次数不止是一次，这种思路有点冒泡的感觉，并且其时间复杂度的系数较高。

public static void xuanZe(int[] a){ 
            for(int i = 0;i < a.length-1;i++) { 
                int temp=0,min = i;
                for(int j = a.length-1;j > i;j--) { 
                    if(a[j] < a[min]){ 
                        min = j;
                    }
                }
                temp = a[min];
                a[min] = a[i];
                a[i] = temp;
            }
        }

**测试一波：**

package sort;
    
    /** * @author yzh * @date 2019-07-15 17:12 */
    public class XuanZe { 
        public static void xuanZe(int[] a){ 
            for(int i = 0;i < a.length-1;i++) { 
                int temp=0,min = i;
                for(int j = a.length-1;j > i;j--) { 
                    if(a[j] < a[min]){ 
                        min = j;
                    }
                }
                temp = a[min];
                a[min] = a[i];
                a[i] = temp;
            }
        }
        public static void main(String[] args) { 
            int[] a = { 4,97,64,3,19,-7,78,0,-90};
            xuanZe(a);
            for(int i = 0;i < a.length;i++){ 
                System.out.println(a[i]);
            }
        }
    }

**测试结果：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NDgyMTkw_size_16_color_FFFFFF_t_70]  
**4.优缺点：**

*  优点：移动数据的次数已知（n-1 次）；
 *  缺点：比较的次数多，效率慢，不稳定（举个例子5，8，5，2，9 我们知道第一遍选择第一个元素5会和2交换，那么原序列中2个5的相对位置前后顺序就破坏了）。

[20190715200345533.gif]: /images/20211209/a40ababb4b67436183815453b40960ae.png
[Link 1]: https://www.cnblogs.com/onepixel/articles/7674659.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NDgyMTkw_size_16_color_FFFFFF_t_70]: /images/20211209/da5b9869012041359aa86300e0bace5c.png