算法-选择法排序

2022-3-31 diaba 算法

package com.jiucaiyuan.net.algrithm.sort;

/**
 * 选择法排序
 *  循环待排序数组,i~N-1位置,每次循环找到最小值放到i位置上,然后i++,再次找最小值
 * 排序结果是升序数组
 * 时间复杂度O(N^2)    空间复杂度O(1)
 *
 * @Author jiucaiyuan  2022/3/25 21:48
 * @mail services@jiucaiyuan.net
 */

public class SelectSort {

    public static void selectionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            //每次循环记录最小数值的index
            int minIndex = i;
            //从i~N-1个数中找到最下值的下标
            for (int j = i; j < arr.length; j++) {
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;
            }
            //找到最小的数值,和当前i位置对调
            swap(arr, minIndex, i);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {1,2,8,3,5,7,2,7,8,12,4};
        selectionSort(arr);
        print(arr);
    }

    private static void print(int[] arr) {
        if(arr == null ){
            return;
        }
        for(int a : arr){
            System.out.print(a+"\t");
        }
        System.out.println();
    }
}

发表评论:

Powered by emlog 京ICP备15045175号-1 Copyright © 2022