算法学习笔记之选择排序算法

素颜马尾好姑娘i 2022-08-21 07:56 107阅读 0赞

接下来我们学习第二种排序算法：

## 选择排序 ##

--------------------

选择排序算法通过**选择和交换**来排序，其排序流程如下：  
1）首先从原始数组中选择最小的一个数据，将其和第一个位置的数据交换  
2）接着从剩下的n-1个数据选择出最小的数据，将其和第二个位置的数据交换  
3）这样不断重复，直到最后两个数据完成交换，即排好了  
示意图如下，有点丑别怪：  
![这里写图片描述][20160424073842100]红色的表示每次排序要交换数据的位置。  
代码：

public static void selectSort(int a[]) {
            for (int i = 0; i < a.length - 1; i++) {
                    int index = i;
                for (int j = i+1; j < a.length; j++) {
                    if (a[j] < a[index]) {
                        index = j;
                    }
                }
                //如果找最小的数据时候，该位置上的数据不是最小，才需要交换
                if (index != i) {
                    int temp;
                    temp = a[index];
                    a[index] = a[i];
                    a[i] = temp;
                }
                //输出每一步排序的结果
                System.out.printf("第" + (i+1) + "次排序结果:");
                for (int i2 = 0; i2 < a.length; i2++) {
                    System.out.printf(a[i2] + " ");
                }
                System.out.println();
            }
        }

结果：  
![20160424074341435][]

时间复杂度：O(N^2)，和其他排序算法的比较请见《算法学习笔记之冒泡排序算法》中的排序算法的比较表。

[20160424073842100]: /images/20220724/c5c528ae298c48e788eb71114020708d.png
[20160424074341435]: /images/20220724/691189c69a184cae96578c989de543c6.png