深入探究数据结构与算法系列——选择排序

       上两篇博客中我们已经学习了什么是冒泡排序和它的性能分析，也知道冒泡排序是算法的技术排序，那么接下来的选择排序就是在冒泡排序的基础上进一步的升级优化。其实不同算法他们的逻辑还是有相当的叙别的，这决定了算法的性能问题。但凡是学习一门语言或者算法，都不能一蹴而就，慢慢学习其原理的重要性。

      下面我们来看看什么是选择排序：

     选择排序是每一次从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

　　分为三步：

　　①、从待排序序列中，找到关键字最小的元素

　　②、如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换

　　③、从余下的 N - 1 个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束

    关于实现其实现我给出了两种，第一种是比较好理解的但是相对来说性能差了点，但是还是比冒泡排序性能好   

    代码如下：

/**
     * @param array
     */
    private static void selectSort(int[] array){
        int temp;
        for (int i = 0; i < array.length; i++) {
            boolean flag = true;
            //较少了内循环的次数来提高性能 多次比较多次交换
            for (int j = i+1; j <array.length ; j++) {
                if (array[i]>array[j]){
                    temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                    flag = false;
                }
            }
            if (flag){
                break;
            }
            System.out.print("第"+(i+1)+"论排序结果：");
            display(array);
        }
    }
           

上面这个算法跟冒泡排序算法是很接近的，不过主要区别就是内循环里面的逻辑，换句话说就是j的初始化位置随之i的增大而增大，从而改变了它的初始值来减少内循环的次数，相对来说交换的次数也会随着减少。优势就是相对来说比较好理解，不过现实开发中我们可能不会用到，如果有更好的选择的话，那么接下来我们介绍另一种更为高尚点的算法，相对性能更高的算法，代码如下：

/**
     * 效率稍微高一点的
     * @param array
     */
    private static void selectSort2(int[] array){
        int temp;
        for (int i = 0; i < array.length; i++) {
            int min = i;
            for (int j = i+1; j < array.length; j++) {
                if (array[min]>array[j]){
                    min = j;
                }
            }
            if (i!= min){
                temp = array[i];
                array[i] = array[min];
                array[min] = temp;
            }
            display(array);
        }
    }
           

上面这段代码也没有写什么注释，这里关键一点就是这个 min变量，因为选择排序每一次外层循环都会产生一个最小的值，i的值也会自动增长，所以在对之前的值进行比较久没有意义了，所以会默认把待排序的第一个标志为最小的数，以后每次比较都会找到最小的数，如果有就交换该标识，内循环玩以后，min的值有可能会改变，然后跟正处于外循环的i做数据交换，完成本次循环排序。这种排序的好处就是较少了交换次数来提高性能。