排序算法(二) 选择排序及改进

选择排序

基本思想

冒泡排序中有一个缺点，比如，我们比较第一个数a1与第二个数a2的时候，只要a1比a2大就会交换位置，但是我们并不能确定a2是最小的元素，假如后面还有比它更小的，该元素还会与a2再次进行交换，而且这种交换有可能发生多次才能确定a2的最终位置。

选择排序可以避免这种耗费时间的交换操作，从第一个元素开始，扫描整个待排数组，找到最小的元素放之后再与第一个元素交换位置，然后再从第二个元素开始，继续寻找最小的元素与第二个元素交换位置，依次类推。

java实现:

public void xuanZe(int[] array){
        if(null == array)
            return;
        for (int i=0; i<array.length; i++){
            //System.out.println(this.toString(array));
            for(int j=i+1; j<array.length; j++){
                if(array[i]>array[j]){
                    int temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                }
            }
        }

        display(array);
    }

算法分析

选择排序与冒泡排序一样，需要进行N*(N-1)/2次比较，但是只需要N次交换，当N很大时，交换次数的时间影响力更大，所以选择排序的时间复杂度为O(N²)。 

虽然选择排序与冒泡排序在时间复杂度属于同一量级，但是毫无疑问选择排序的效率更高，因为它的交换操作次数更少，而且在交换操作比比较操作的时间级大得多时，选择排序的速度是相当快的。 

选择排序的改进

传统的选择排序每次只确定最小值，根据改进冒泡算法的经验，我们可以对排序算法进行如下改进：每趟排序确定两个最值——最大值与最小值，这样就可以将排序趟数缩减一半。  

改进后的代码如下：

    public void xuanZe2(int[] array){
        if(null == array)
            return;

        int low = 0;
        int high = array.length - 1;
        int temp;
        while (low < high){
            //正向选出最小的
            for (int i=high; i>low; i--){
                if (array[i] < array[low]){ //如果比低位小  交换位置
                    temp = array[low];
                    array[low] = array[i];
                    array[i] = temp;
                }
            }
            low++;
            //反向选出最大的
            for (int i=low; i<high; i++){
                if(array[i] > array[high]){   //如果比高位大 交换位置
                    temp = array[high];
                    array[high] = array[i];
                    array[i] = temp;
                }
            }
            high--;

        }

        display(array);
    }

运行代码及结果:

public static void  main(String[] args){
        PaiXu paiXu = new PaiXu();
        int[] array = paiXu.newArr();
        System.out.println("排序前");
        paiXu.display(array);
  
        long start3 = System.currentTimeMillis();
        paiXu.xuanZe(array.clone());
        long end3 = System.currentTimeMillis();
        System.out.println("********xuanZe排序完成************用时:" + (end3 - start3));

        long start4 = System.currentTimeMillis();
        paiXu.xuanZe2(array.clone());
        long end4 = System.currentTimeMillis();
        System.out.println("********xuanZe排序完成************用时:" + (end4 - start4));
    }

排序前
11557 22454 45454 50034 9350 53520 2114 21991 83107 40298 68205 95242 56729 49019 61917 21325 5923 54646 35818 85341 57252 3607 81555 95431 55778 19753 35785 74473 63877 49503

排序后  
2 2 3 3 4 4 4 5 6 9 10 10 11 11 12 12 12 13 13 16 16 17 17 18 18 19 19 20 21 21
********xuanZe排序完成************用时:18075
2 2 3 3 4 4 4 5 6 9 10 10 11 11 12 12 12 13 13 16 16 17 17 18 18 19 19 20 21 21
********xuanZe排序完成************用时:9962