小饶学编程之JAVA SE第一部分——选择排序算法

柔光的暖阳◎ 2022-12-19 01:21 143阅读 0赞

### 选择排序算法 ###

*  一、算法描述
 *  二、算法原理
 *  三、时间复杂度
 *  四、算法实现
 *  五、总结

# 一、算法描述 #

第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

# 二、算法原理 #

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

# 三、时间复杂度 #

选择排序的交换操作介于 0 和 (n - 1)次之间。选择排序的比较操作为 n (n - 1） / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1） 次之间。比较次数O(n^2），比较次数与关键字的初始状态无关，总的比较次数N=(n-1）+(n-2）+…+1=n\*(n-1）/2。交换次数O(n），最好情况是，已经有序，交换0次；最坏情况交换n-1次，逆序交换n/2次。交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。

# 四、算法实现 #

public static void main(String[] args) {
        
            int[] arr ={
        8,9,5,4,-9,99,0,68,51,44};
            for (int i = 0; i <arr.length-1 ; i++) {
        //外层循环轮数：0->len-1（不取）
                int index = i;//最小值的下标，内层循环每轮要找到最小值的下标
                for (int j = i+1; j <arr.length ; j++) {
        //i+1->len(i=0,不取)
                    if(arr[j]<arr[index]){
        
                        index=j;//比较之后得到当前这轮最小值所在位置的下标
                    }
                }
                //交换方法
                int num=arr[i];
                arr[i]=arr[index];
                arr[index]=num;
            }
            //输出排序后数组的所有元素
            for (int a:arr
                 ) {
        
                System.out.print(a+"\t");//-9	0	4	5	8	9	44	51	68	99	
            }
        }

# 五、总结 #

选择排序：外层循环每轮找最小值的下标，把最下值交换到最前面，直到排序完成。  
int\[\] Arr=\[5,4,3,2,1\];  
i=0；

<table> 
 <thead> 
  <tr> 
   <th>外层循环轮数</th> 
   <th>数组元素变化</th> 
   <th>前数下标范围</th> 
   <th>后数（index）下标范围</th> 
   <th>比较次数</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>外层第一轮</td> 
   <td>1，4，3，2，5</td> 
   <td>0，len-2</td> 
   <td>1,len-1</td> 
   <td>3</td> 
  </tr> 
  <tr> 
   <td>外层第二轮</td> 
   <td>1，2，3，4，5</td> 
   <td>1，len-2</td> 
   <td>2,len-1</td> 
   <td>2</td> 
  </tr> 
  <tr> 
   <td>外层第三轮</td> 
   <td>1，2，3，4，5</td> 
   <td>2，len-2</td> 
   <td>3,len-1</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>外层第四轮</td> 
   <td>1，2，3，4，5</td> 
   <td>len-2</td> 
   <td>4</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>len-1趟</td> 
   <td></td> 
   <td>i+1</td> 
   <td>i+1，len-2</td> 
   <td>len-i-2</td> 
  </tr> 
 </tbody> 
</table>

当i=0时，  
外层循环轮数：从0到len-1（不取此值）（0到3，共4次）  
内层循环比较次数：从i+1到len（不取此值）