Java实现：八大排序之选择排序(心得体会)

选择排序：

算法思想：

选择排序的实现思路有点儿类似于插入排序，也是划分为已排序区间和未排序区间，但是选择排序每次是从未排序区找到最小的元素，然后放到已排序区间的末尾，仅此而已；

下面是我根据自己的理解画的示意图：

下面是代码实现：

/**
     * 选择排序；
     * 无序的一组数，每次从无序的数集中选择最小的一个数字，
     * 添加到有序数组的最后一位；直到无序数组为空
     * @param data
     */
    public static void selectionSort(int[] data){
        long start = System.currentTimeMillis();
        int n = data.length;
        //老规矩，一上来先判断数组元素个数；如果是1或者是0，就之间返回；
        if (n <= 1){
            return;
        }else{
            for (int i = 0;i < n-1;i++){
                int minIndex = i;
                for (int j = i+1;j < n;j++){
                    if (data[minIndex] > data[j]){
                        minIndex = j;
                    }
                }
                int temp = data[i];
                data[i] = data[minIndex];
                data[minIndex] = temp;
            }
        }
        long end = System.currentTimeMillis();
        System.out.println("选择排序的耗时为"+(end - start)+"毫秒");
    }

简单解释一下代码：

• 外层循环，下标i循环到倒数第二个元素就停止了，是因为，当待排序区间只剩下一个元素的时候，它就是最后一个元素，无需再次比较；
• 里层循环，下标i每次指向的都是已排序区间的下一个元素（就是未排序区间的第一个元素），这个元素跟后面的元素比较，如果有比它小的，就将mixIndex这个下标指向它，这层循环结束后交换未排序区间第一个元素跟mixIndex这个元素，此时已排序区间末尾又增加一个元素；然后外层循环增加，继续寻找后面的待排序区间的最小值，依次循环，直到未排序区间仅剩下一个元素；

下面小结一下：

1. 首先，选择排序是原地排序，空间复杂度为O(1);
2. 由选择排序的实现代码可以看出，不论数据集合是否有序，都要每次从未排序区间找到最小的元素然后插入到已排序区间；所以选择排序的最好情况时间复杂度、最坏情况和平均时间复杂度等都是O(n^2);
3. 稳定性：不稳定；举个例子，有一列数据，5 3 7 5 2 6，第一次之间交换了第一个元素5和2，然后第一个5就跟原来数据中第四个5的相对位置发生了变化，所以说不稳定；