选择排序算法

一、选择排序算法

选择排序（Selection sort）是一种简单直观的排序算法。

二、算法思想

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

三、代码实现

/**
 * 选择排序算法
 * @author xzg
 */
public class SelectionSort {


    public static void main(String[] args) {
        int[] arr = {6, 1, 3, 9, 2, 15, 4, 12, 8, 14};

        int[] sortArr = selectionSort(arr);

        System.out.println("排序结果如下：");
        for (int num : sortArr) {
            System.out.print(num + " ");
        }
    }

    /**
     * 算法描述：<br/>
     * 对于给定的一组记录，经过第一轮比较后得到最小的记录；<br/>
     * 然后将该记录与第一个记录的位置进行交换；<br/>
     * 接着对不包括第一个记录以外的其他记录进行第二轮比较，得到最小的记录并与第二个记录进行位置交换；<br/>
     * 重复该过程，直到进行比较的记录只有一个时为止。
     * @param arr
     * @return
     */
    public static int[] selectionSort(int[] arr) {

        int n = arr.length;
        for (int i = 0; i < n; i++) {//第i趟排序
            int k = i;
            for (int j = k + 1; j < n; j++) {
                if (arr[j] < arr[k]) {//找出最小数字
                    k = j;//记录下目前最小值所在的位置
                }
            }
            if (k != i) {//最小数字不是在最前面，则交换位置
                int temp = arr[i];
                arr[i] = arr[k];
                arr[k] = temp;
            }
            System.out.println("第 " + (i + 1) + " 趟排序结果如下：");
            for (int num : arr) {
                System.out.print(num + " ");
            }
            System.out.println();
        }

        return arr;
    }
}

输出结果如下：

第 1 趟排序结果如下：
1 6 3 9 2 15 4 12 8 14 
第 2 趟排序结果如下：
1 2 3 9 6 15 4 12 8 14 
第 3 趟排序结果如下：
1 2 3 9 6 15 4 12 8 14 
第 4 趟排序结果如下：
1 2 3 4 6 15 9 12 8 14 
第 5 趟排序结果如下：
1 2 3 4 6 15 9 12 8 14 
第 6 趟排序结果如下：
1 2 3 4 6 8 9 12 15 14 
第 7 趟排序结果如下：
1 2 3 4 6 8 9 12 15 14 
第 8 趟排序结果如下：
1 2 3 4 6 8 9 12 15 14 
第 9 趟排序结果如下：
1 2 3 4 6 8 9 12 14 15 
第 10 趟排序结果如下：
1 2 3 4 6 8 9 12 14 15 
排序结果如下：
1 2 3 4 6 8 9 12 14 15 
Process finished with exit code 0

四、算法分析

时间复杂度是O(n^2)