欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

选择排序原理及代码实现

程序员文章站 2022-03-24 15:33:00
...

选择排序基本思想:

第一轮从arr[0]~arr[n-1]中找到最小的元素,与arr[0]进行交换;
第二轮从arr[1]~arr[n-1]中找到最小的元素,与arr[1]进行交换;

依次类推,经过n-1轮之后,就形成了有序序列

选择排序java代码实现:

public class SelectSort {
    public static void selectSort(int[] nums) {//3,1,4,2,5
        for (int i = 0; i < nums.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[min]) {
                    min = j;
                }
            }
            if (min != i) {
                int temp = nums[min];
                nums[min] = nums[i];
                nums[i] = temp;
            }
        }
    }
}

选择排序时间复杂度:

选择排序无论在何种情况下都需要进行 (n-1) + (n-2) + (n-3) + … + 1 = n*(n-1)/2次,所以复杂度是O(n2).