【选择排序算法详解】

选择排序算法代码示例复杂度计算小结

主要思想：
对于一个长度为n的数组序列arr，在每一趟的遍历下，寻找一个最大（最小）的值，然后与数组序列终点（起点）进行交换，其次大的（小的）与排序第二的位置交换，每一趟结束后都可以确定一个值的最终位置，经过n-1次遍历后就可以得到一个排好序的数组arr。以百度百科的图作为示例：

public class SelectSort {
    public static void selectSort(int[] arr){
        //若数组为空或小于两个值，则默认有序退出
        if (arr == null || arr.length < 2){
            return;
        }
        for(int i = 0;i 
细节：
 外循环：每一次由两个数进行交换，对于一个长度为n的数组，外循环执行n-1次即可，因此i 内循环：因为每次会确定好一个值，因此内循环只需从i+1开始遍历即可，如果是从大到小排序，则内循环从arr.length-i-1开始即可。
 
复杂度计算 
分析算法逻辑，我们可以看到：
 第一次内循环比较了N-1次
 第二次内循环比较了N-2次
 第三次内循环比较了N-3次
 …
 第N-2次内循环比较了2次
 第N-1次内循环比较了1次
 共比较次数（N-1）+（N-2）+（N-3）+…+2+1次，等差数列求和，舍去低项和最高项系数，得到算法复杂度O(
    
     
      
       
        
         N
        
        
         2
        
       
      
      
       N^{2}
      
     
    N2)。
 整个过程，开辟有限个新的空间，空间复杂度O(1)
 
小结 
留下笔记，只为方便回忆，如有错误，还请纠正。陆续更新，还请关注。