Java版选择排序

分析&回答

实现代码

动态演示 -> 跳转到博客查看

代码实现

/**
 * 1）第一轮逐一扫描所有数字，并取出最小那个放在第一位；
 * 2）第二轮扫描剩下的数字，并取出第二小的那个数字放在第二位；
 * 3）以此循环反复，直到所有数字都已经排序。
 *
 * @param arr
 */
public static void selectionSort(int[] arr) {
    //选择排序的优化
    for (int i = 0; i < arr.length - 1; i++) {// 做第i趟排序
        int k = i;
        for (int j = k + 1; j < arr.length; j++) {// 选最小的记录
            if (arr[j] < arr[k]) {
                k = j; //记下目前找到的最小值所在的位置
            }
        }
        //在内层循环结束，也就是找到本轮循环的最小的数以后，再进行交换
        if (i != k) {  //交换a[i]和a[k]
            int temp = arr[i];
            arr[i] = arr[k];
            arr[k] = temp;
        }
    }
}

性能分析

• 不稳定 
• 平均时间复杂度O(n²) 
• 空间复杂度O(1) 

反思&扩展

Java版常用排序算法复杂度

喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！