【排序算法】选择排序原理及Java实现

心已赠人 2022-08-21 10:42 212阅读 0赞

## 1、基本思想： ##

选择排序是一种简单直观的排序算法，其基本原理如下：对于给定的一组记录，经过第一轮比较后得到最小的记录，然后将该记录的位置与第一个记录的位置交换；接着对不包括第一个记录以外的其他记录进行第二次比较，得到最小记录并与第二个位置记录交换；重复该过程，知道进行比较的记录只剩下一个为止。

## 2、复杂度分析： ##

从简单选择排序的过程来看，它最大的特点是交换移动数据次数相当少，这样就节约了相应的时间。分析它的时间复杂度发现，无论是最好最差情况，其比较次数都是一样多，第 *i* 趟排序需要进行 *n-i* 次关键字比较，此时需要比较次![这里写图片描述][20160427091425501]，对于交换次数而言，当最好的时候，交换*0*次，最差的时候，也就是初始降时，交换次数为 *n-1* 次，基于最终的时间排序与交换次数总和，因此，总的时间复杂度依然为![这里写图片描述][20160427091455826]。  
尽管与冒泡排序同为![这里写图片描述][20160427091455826]，但简单选择排序的性能要优于冒泡排序。

## 3、排序过程如下： ##

以数组\{49,38,65,97,76,13,27,49\}为例，  
![这里写图片描述][20160426212751938]

## 4、Java实现如下： ##

public class SelectSort {
    
        public static void selectSort(int[] a) {
            if (a == null || a.length <= 0) {
                return;
            }
            for (int i = 0; i < a.length; i++) {
                int temp = a[i];
                int flag = i; // 将当前下标定义为最小值下标
                for (int j = i + 1; j < a.length; j++) {
                    if (a[j] < temp) {
       // a[j] < temp 从小到大排序；a[j] > temp 从大到小排序
                        temp = a[j];
                        flag = j; // 如果有小于当前最小值的关键字将此关键字的下标赋值给flag
                    }
                }
                if (flag != i) {
                    a[flag] = a[i];
                    a[i] = temp;
                }
            }
        }
    
        public static void main(String[] args) {
            int a[] = { 49,38,65,97,76,13,27,49 };
            selectSort(a);
            System.out.println(Arrays.toString(a));
        }
    }

[20160427091425501]: https://img-blog.csdn.net/20160427091425501
[20160427091455826]: /images/20220724/9ed86593f1fd4016a04924aae957d01d.png
[20160426212751938]: /images/20220724/14eb2107919747cd934675454278c279.png