【面试：基础篇03：选择排序】

如果有任何问题还请指出，感谢。

选择排序是基础排序的一种，它的思路是，原数列分为有序和无序部分，每次从无序部分中 挑出极值放入有序数列部分

对于数列{5,3,7,2,1,9,8,4}进行从小到大选择排序

初始 有序部分为空 无序部分为 5 3 7 2 1 9 8 4

第一趟：1 3 7 2 5 9 8 4，有序部分为1 无序部分为3 7 2 5 9 8 4，元素1的位置与元素5的位置对换

第二趟：1 2 7 3 5 9 8 4 ，有序部分为1 2 无序部分为 7 3 5 9 8 4 ，元素2的位置与元素3的位置对换

第三趟：1 2 3 7 5 9 8 4，有序部分为1 2 3 无序部分为7 5 9 8 4，元素3的位置与元素5的位置对换

第四趟：1 2 3 4 5 9 8 7 ，有序部分为1 2 3 4 无序部分为5 9 8 7 ，元素4的位置与元素7的位置对换

第五趟：1 2 3 4 5 9 8 7，有序部分为1 2 3 4 5 无序部分为7 9 8，元素5的位置与元素5的位置对换

第六躺：1 2 3 4 5 7 8 9，有序部分为1 2 3 4 5 7 无序部分为 8 9，元素7的位置与元素9的位置对换

第七趟：1 2 3 4 5 7 8 9，有序部分为1 2 3 4 5 7 8 无序部分为9，元素8的位置与元素8的位置对换，但因为现在只有一个元素无序 所以其实以及排序完了

可以看出几个问题

1.可以看出8个元素排序7趟

2.选择排序是选择无序部分的第一个元素与剩下元素的极值进行交换，最后吧无序部分的第一个元素加入有序部分

3.可以看出第五趟与第七趟都进行 与自身的交换，这里是优化点

public static void main(String[] args) {
    int[] a = {5,3,7,2,1,9,8,4};
    int len = a.length;
    for (int i=0;i
        int pos=i;
        for (int j=pos+1;j
            if (a[j]
                pos = j;
            }
        }
        if (pos!=i){// 如果交换元素不是自身
            System.out.println("第"+(i+1)+"趟");
            int t=a[pos];
            a[pos]=a[i];
            a[i]=t;
            for (int k=0;k 
结果 
 
 
第1趟
 1 3 7 2 5 9 8 4
 第2趟
 1 2 7 3 5 9 8 4
 第3趟
 1 2 3 7 5 9 8 4
 第4趟
 1 2 3 4 5 9 8 7
 第6趟
 1 2 3 4 5 7 8 9
 
 
可以看出优化后少了第五趟与第七趟的的交换
 
04.选择排序与冒泡排序的对比 
相同点: 
 
 
1.它俩都是基础排序 时间复杂度都是O(
     
      
       
        
         
          n
         
         
          2
         
        
       
       
        n^2
       
      
     n2)
 
 
2.它俩都是基于交换来进行排序
 
 
不同点: 
 
 
1.选择排序是不稳定排序1，冒泡排序是稳定排序
 
 
2.选择排序在顺序度乱的情况下时间复杂度优于冒泡排序，因为选择排序每一趟只是记录下标值最终只是交换了一次，而冒泡排序每趟需要交换很多次。
 
 
3.优化后的冒泡排序在顺序度顺的情况下时间复杂度优于选择排序，因为优化后的冒泡排序 趟数与交换的次数会大幅度减少，但选择排序则不行
 
 
 
 
 
不稳定排序是指，排序后元素的相对前后位置发生了变化，例如5 8 5 2 9，选择排序后是 2 5 5 8 9，但此时的 5 5 与原数列的相对前后位置是发生变化的。而冒泡排序是不变的，所以冒泡排序是稳定排序。 ↩︎