安卓面试一

排序_选择排序之简单选择排序(直接选择排序)

2017-01-09  本文已影响203人  官先生Y

基本思想

数组分成有序区和无序区,初始时整个数组都是无序区,然后每次从无序区选一个最小的元素直接放到有序区的最后,重复这样的操作,直到整个数组变成有序区。

处理流程

设数组为a[0…n-1]。

  1. 初始时,数组全为无序区a[0..n-1]。
  2. 令i=0,从无序列a[i…n-1]中选取一个最小的元素;将其与a[i]交换。交换之后a[0...i]就形成了一个有序区
  3. i++并重复第二步直到i==n-1。排序完成。

与其它排序算法比较

冒泡排序与选择排序:

简单选择排序(直接选择排序)与直接插入排序对比理解:

简单选择排序(直接选择排序)与堆排序的关系:

代码示例

public class 简单选择排序 {

    public static void main(String[] args) {
        int[] sequence = new int[]{9, 1, 5, 8, 3, 7, 4, 6, 2};//待排序的关键字序列
        System.out.println("排序前:" + Arrays.toString(sequence));
        sortFromRear2Front(sequence);
//        sortFromFront2Rear(sequence);
        System.out.println("排序后:" + Arrays.toString(sequence));
    }

    /**
     * 从后往前搜索 从小到大排序
     */
    private static void sortFromRear2Front(int[] sequence) {

        int i, j, max;
        for (i = sequence.length - 1; i > 0; i--) {
            max = i;//将当前下标定义为最大值下标
            for (j = i - 1; j >= 0; j--) {
                if (sequence[j] > sequence[max]) {//如果有大于当前最大值的关键字
                    max = j;
                }
            }
            if (i != max) {//若min不等于i,说明找到最大值,交换
                swap(sequence, max, i);
            }
        }
    }

    /**
     * 从前往后搜索 从小到大排序
     */
    private static void sortFromFront2Rear(int[] sequence) {
        //对数组a[i...n-1]无序区间,进行排序
        for (int i = 0; i < sequence.length - 1; i++) {

            int temp = 0;
            int minIndex = i;// 用来保存最小值的索引

            //得到无序区的最小元素对应的索引
            for (int j = i + 1; j < sequence.length; j++) {
                if (sequence[minIndex] > sequence[j]) {
                    minIndex = j;
                }
            }

            //无序区最小元素与无序区第1个元素交换
            temp = sequence[minIndex];
            sequence[minIndex] = sequence[i];
            sequence[i] = temp;
        }
    }

    private static void swap(int[] sequence, int formerIndex, int latterIndex) {
        int temp;
        temp = sequence[formerIndex];
        sequence[formerIndex] = sequence[latterIndex];
        sequence[latterIndex] = temp;
    }

}

简单选择排序示例图

算法分析

简单选择排序是不稳定的排序。
时间复杂度:O(n2)。

上一篇下一篇

猜你喜欢

热点阅读