选择排序

2017-02-11  本文已影响35人  FTOLsXD

思想

还是先来看看选择排序的思想。选择排序的思想非常直接,不是要排序么?那好,我就从所有序列中先找到最小的,然后放到第一个位置。之后再看剩余元素中最小的,放到第二个位置……以此类推,就可以完成整个的排序工作了。可以很清楚的发现,选择排序是固定位置,找元素。相比于插入排序的固定元素找位置,是两种思维方式。不过条条大路通罗马,两者的目的是一样的。

代码:

private static void selectSort(int[] sortArray) {
        long bs = Calendar.getInstance().getTimeInMillis();
        for(int i = 0; i < sortArray.length;i++){
            for(int j = i+1 ; j < sortArray.length;j++){
                if(sortArray[i] > sortArray[j]){
                    swap(sortArray,i,j);
                }
            }
        }
        System.out.println(" sort cost time: "+ (Calendar.getInstance().getTimeInMillis() - bs)+"毫秒");
    }

private static void swap(int[] array,int i, int j) {
        array[i] = array[i]^array[j];
        array[j] = array[j]^array[i];
        array[i] = array[i]^array[j];
    }

分析

从选择排序的思想或者是上面的代码中,我们都不难看出,寻找最小的元素需要一个循环的过程,而排序又是需要一个循环的过程。因此显而易见,这个算法的时间复杂度也是O(n*n)的。这就意味值在n比较小的情况下,算法可以保证一定的速度,当n足够大时,算法的效率会降低。并且随着n的增大,算法的时间增长很快。因此使用时需要特别注意。

上一篇 下一篇

猜你喜欢

热点阅读