排序算法之选择排序

原理：每一趟从待排序的记录中选出最小或者最大的元素，按顺序放在已排好序的序列最后，直到全部记录排序完毕。

import java.util.Scanner;
public class Solution {
   public static void main(String args[]){
       int []arr=new int[5000];
       int n;
       Scanner in=new Scanner(System.in);
       System.out.print("输入数组大小:");
       n=in.nextInt();
       System.out.print("输入数组:");
       for(int i=0;i<n;i++){
           arr[i]=in.nextInt();
       }
       System.out.println("选择排序前数组顺序:");
       for(int i=0;i<n;i++){
           System.out.print(arr[i]+" ");
       }
       System.out.println();
       int min;
       for(int i=0;i<n;i++){
           min=i;
           for(int j=i;j<n;j++){
               if(arr[min]>arr[j]){
                   min=j;
               }
           }
           if(i!=min){
               int temp=arr[i];
               arr[i]=arr[min];
               arr[min]=temp;
           }
       }
       System.out.println("选择排序后的结果为:");
       for(int i=0;i<n;i++){
           System.out.print(arr[i]+" ");
       }
   }
}

选择排序的时间复杂度：简单选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有 N 个元素，则比较次数永远都是N (N - 1) / 2。而移动次数与序列的初始排序有关。当序列正序时，移动次数最少，为 0。当序列反序时，移动次数最多，为3N (N - 1) / 2。
所以，综上，简单排序的时间复杂度为 O(N²)。