【Java】简单选择排序

深藏阁楼爱情的钟 2021-12-16 23:17 214阅读 0赞

简单选择排序属于选择类排序方法，它的改进是堆排序。

简单选择排序的基本思想非常简单（假设从小到大排序）：第一趟，从 n 个元素中找出关键字最小的元素与第一个元素交换；第二趟，在从第二个元素开始的 n-1 个元素中再选出关键字最小的元素与第二个元素交换；如此，第 k 趟，则从第 k 个元素开始的 n-k+1 个元素中选出关键字最小的元素与第 k 个元素交换，直到整个序列按关键字有序。

图示排序过程如下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0x1eWFuYw_size_16_color_FFFFFF_t_70]

假设从小到大排序，核心代码如下：

//假设从小到大排序
        public static void insertSort(Integer[] arr){ 
            for (int i = 1; i < arr.length; i++) { 
                int temp = arr[i];
                int position = i;
                for (int j = i-1; j >= 0 ; j--) { 
                    if(temp < arr[j]){ 
                        //记录后移
                        arr[j+1] = arr[j];
                        position = j;
                    }else { 
                        break;
                    }
                }
                //插入到正确位置
                arr[position]=temp;
            }
        }

<table> 
 <tbody> 
  <tr> 
   <td align="left"><font><b>时空复杂度<b></b></b></font></td> 
  </tr> 
 </tbody> 
</table>

来张整体图的比较吧~

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0x1eWFuYw_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0x1eWFuYw_size_16_color_FFFFFF_t_70]: /images/20211214/83608c1d618c4622805dd6d81c73ef23.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0x1eWFuYw_size_16_color_FFFFFF_t_70 1]: /images/20211214/bf1b2f4058614bc283180d61e29584bf.png