2. 图解-选择排序

忘是亡心i 2022-04-15 01:05 80阅读 0赞

### 1. 思想 ###

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置

### 2. 图解过程 ###

每一趟选最小的。

例1：

![070957462543455.png][]

例2：

![timg_image_quality_80_size_b9999_10000_sec_1542639924701_di_2ee6ff35e85ca0e3d6f124b964c71df0_imgtype_0_src_http_3A_2F_2Fs1.knowsky.com_2F20170227_2Ftfyxqkboyet58.jpg][]

### 3.CODE in JAVA ###

public class SelectionSort {
 	 
 public static void selectionSort(int[] a) {
 int n = a.length;
 for (int i = 0; i < n; i++) {
 int k = i;
 // 找出最小值的下标
 for (int j = i + 1; j < n; j++) {
 if (a[j] < a[k]) {
 k = j;
 }
 }
 // 将最小值放到未排序记录的第一个位置
 if (k > i) {
 int tmp = a[i];
 a[i] = a[k];
 a[k] = tmp;
 }
 }
 }
 
 public static void main(String[] args) {
 int[] b = { 49, 38, 65, 97, 76, 13, 27, 50 };
 selectionSort(b);
 for (int i : b)
 System.out.print(i + " ");
 }
 }

### 4.算法分析 ###

<table> 
 <tbody> 
 <tr> 
 <td style="background-color:#4f81bd;vertical-align:bottom;"> 排序类别 </td> 
 <td style="background-color:#4f81bd;border-color:#c0c0c0;vertical-align:bottom;"> 排序方法 </td> 
 <td colspan="3" style="background-color:#4f81bd;border-color:#c0c0c0;vertical-align:bottom;"> 时间复杂度 </td> 
 <td style="background-color:#4f81bd;border-color:#c0c0c0;vertical-align:bottom;"> 空间复杂度 </td> 
 <td style="background-color:#4f81bd;border-color:#c0c0c0;vertical-align:bottom;"> 稳定性 </td> 
 <td style="background-color:#4f81bd;border-color:#c0c0c0;vertical-align:bottom;"> 复杂性 </td> 
 </tr> 
 <tr> 
 <td style="background-color:#4f81bd;border-color:#c0c0c0 #c0c0c0;vertical-align:bottom;"> 平均情况 </td> 
 <td style="background-color:#4f81bd;border-color:#c0c0c0 #c0c0c0;vertical-align:bottom;"> 最坏情况 </td> 
 <td style="background-color:#4f81bd;border-color:#c0c0c0 #c0c0c0;vertical-align:bottom;"> 最好情况 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#c0c0c0;vertical-align:bottom;"> 选择排序 </td> 
 <td style="border-color:#c0c0c0 #c0c0c0;vertical-align:bottom;"> 简单选择排序 </td> 
 <td style="border-color:#c0c0c0 #c0c0c0;vertical-align:bottom;"> O(N²) </td> 
 <td style="border-color:#c0c0c0 #c0c0c0;vertical-align:bottom;"> O(N²) </td> 
 <td style="border-color:#c0c0c0 #c0c0c0;vertical-align:bottom;"> O(N²) </td> 
 <td style="border-color:#c0c0c0 #c0c0c0;vertical-align:bottom;"> O(1) </td> 
 <td style="border-color:#c0c0c0 #c0c0c0;vertical-align:bottom;"> 不稳定 </td> 
 <td style="border-color:#c0c0c0 #c0c0c0;vertical-align:bottom;"> 简单 </td> 
 </tr> 
 </tbody> 
</table>

### 5.参考 ###

[https://www.cnblogs.com/jingmoxukong/p/4303289.html][https_www.cnblogs.com_jingmoxukong_p_4303289.html]

[http://www.cnblogs.com/xwz0528/p/4557743.html][http_www.cnblogs.com_xwz0528_p_4557743.html]

[https://www.cnblogs.com/zengzhihua/p/4456741.html][https_www.cnblogs.com_zengzhihua_p_4456741.html]

[070957462543455.png]: /images/20220415/b6fc47dc690440c79ab62511064e636d.png
[timg_image_quality_80_size_b9999_10000_sec_1542639924701_di_2ee6ff35e85ca0e3d6f124b964c71df0_imgtype_0_src_http_3A_2F_2Fs1.knowsky.com_2F20170227_2Ftfyxqkboyet58.jpg]: https://timgsa.baidu.com/timg?image&quality=80&size=b9999_10000&sec=1542639924701&di=2ee6ff35e85ca0e3d6f124b964c71df0&imgtype=0&src=http%3A%2F%2Fs1.knowsky.com%2F20170227%2Ftfyxqkboyet58.jpg
[https_www.cnblogs.com_jingmoxukong_p_4303289.html]: https://www.cnblogs.com/jingmoxukong/p/4303289.html
[http_www.cnblogs.com_xwz0528_p_4557743.html]: http://www.cnblogs.com/xwz0528/p/4557743.html
[https_www.cnblogs.com_zengzhihua_p_4456741.html]: https://www.cnblogs.com/zengzhihua/p/4456741.html