数据结构（九）：简单选择排序

不念不忘少年蓝@ 2021-08-11 22:35 288阅读 0赞

*  通过 n-i 次元素之间的比较，从 n-i+1 个元素中选出值最小的元素，和第 i 个元素交换 （从数组中选出最小值元素与最左元素进行交换位置）

### 简单选择排序例子 ###

*  举例：
    
     *  假设数组如下
    
    <table> 
     <thead> 
      <tr> 
       <th style="text-align:center">5</th> 
       <th style="text-align:center">2</th> 
       <th style="text-align:center">8</th> 
       <th style="text-align:center">4</th> 
       <th style="text-align:center">9</th> 
       <th style="text-align:center">1</th> 
      </tr> 
     </thead> 
     <tbody> 
     </tbody> 
    </table>
    
     *  第一趟排序：比较 \{ 5 2 8 4 9 1 \}，1 最小，1 和 5 互换位置
    
    <table> 
     <thead> 
      <tr> 
       <th style="text-align:center">1</th> 
       <th style="text-align:center">2</th> 
       <th style="text-align:center">8</th> 
       <th style="text-align:center">4</th> 
       <th style="text-align:center">9</th> 
       <th style="text-align:center">5</th> 
      </tr> 
     </thead> 
     <tbody> 
     </tbody> 
    </table>
    
     *  第二趟排序：比较 \{ 2 8 4 9 5 \}，2 最小，已在最后一位，位置不变
     *  第三趟排序：比较 \{ 8 4 9 5 \}，4 最小，4 和 8 互换位置
    
    <table> 
     <thead> 
      <tr> 
       <th style="text-align:center">1</th> 
       <th style="text-align:center">2</th> 
       <th style="text-align:center">4</th> 
       <th style="text-align:center">8</th> 
       <th style="text-align:center">9</th> 
       <th style="text-align:center">5</th> 
      </tr> 
     </thead> 
     <tbody> 
     </tbody> 
    </table>
    
     *  第四趟排序：.....
    
    <table> 
     <thead> 
      <tr> 
       <th style="text-align:center">1</th> 
       <th style="text-align:center">2</th> 
       <th style="text-align:center">4</th> 
       <th style="text-align:center">5</th> 
       <th style="text-align:center">9</th> 
       <th style="text-align:center">8</th> 
      </tr> 
     </thead> 
     <tbody> 
     </tbody> 
    </table>
    
     *  第五趟排序：.....
    
    <table> 
     <thead> 
      <tr> 
       <th style="text-align:center">1</th> 
       <th style="text-align:center">2</th> 
       <th style="text-align:center">4</th> 
       <th style="text-align:center">5</th> 
       <th style="text-align:center">8</th> 
       <th style="text-align:center">9</th> 
      </tr> 
     </thead> 
     <tbody> 
     </tbody> 
    </table>

### 简单选择排序代码 ###

int[] arr = new int[]{1, 3, 6, 4, 7, 8, 5, 10, 9};
    // 简单选择排序
    for(int i = 0; i < arr.length - 1; i++) {
        int k = i;
        for(int j = k + 1; j < arr.length; j++){
            if(arr[j] < arr[k]){
                k = j;      //记下目前找到的最小值所在的位置
            }
        }
        // 移动最小的元素至最左边
        if(i != k){
            int temp = arr[i];
            arr[i] = arr[k];
            arr[k] = temp;
        }
    }

### 简单选择排序时间的性能 ###

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