排序第三记——选择排序

选择排序：Selection Sort

这次说的是最简单的——选择排序

为啥说他最简单呢？额，难度和冒泡相比的话差不多吧，思想上比冒泡还能简单点，我觉得如果让一个完全没有概念的人去想排序方法的话，那么这个人八成首先想到的就是选择排序。

原理

选择排序的原理很简单：
1.遍历整个数组，找出最小的那个数，并记下它的位置~
2.把它放在第一个位置上
3.遍历数组，这次从第二个数开始（因为第一个数已经是最小的了），选出最小的数，并记下其位置~
4.把它放在第二个位置上
......
重复上面的操作，直到最后一个数。

很简单吧~
实现起来应该也不难，想必大家都可以手敲出来：

/**
 * Created by AceCream on 2017/3/20.
 * 选择排序（SelectionSort）
 * 通过选择和交换来实现排序
 * 1.首先从原始数组中选择最小的1个数据，将其和位于第一个位置的数据交换。
 * 2.接着从剩下的n-1个数据中选择里面最小的元素，和第二个位置数据进行交换。
 * 3.不断重复
 *
 * 时间复杂度： 平均：O(n^2)   最佳：O(n^2)   最坏：O(n^2)
 * 空间复杂度： O(1)
 * 稳定性： 不稳定
 *
 */
public class selectSort {
    public static void selectSort(int value[]){
        int index; //记录位置
        int temp;
        for (int i=0;i<value.length;i++){
            index = i;
            //j=i+1 是为了不和自己比较，因为没有意义
            for (int j=i+1;j<value.length;j++){
                if (value[j]<value[index]){
                    index = j;
                }
            }

            //判断一下，如果是自己，就不要执行下面的步骤了
            if (index!=i){
                temp = value[i];
                value[i] = value[index];
                value[index] = temp;
            }
        }
    }
    
    public static void main(String[] args) {
        int value[] = {12,15,9,20,6,31,24};
        selectSort(value);
        System.out.print("最终结果 ");
        for (int result : value) {
            System.out.print(result+" ");
        }
    }
}

这个很简单，但是简单要付出简单的代价，代价就是时间复杂度实在的太高了，相比于其他排序，各项指标都被完爆，恩，除了好写。(选排：但是人家思想最简单~哼╭(╯^╰)╮)

堆排序：Heap Sort

顾名思义，是利用“堆”这种数据结构设计出来的一种排序算法。
之前一直无法理解这种排序，结果发现是因为自己对堆概念的了解不足。（堆：“我当然不是内存模型里的堆，我是数据结构里的堆，人家重名了！！！重名！而已！”）

后续更新...

后记(可跳过不看)

普通人的思维是在最短时间内，找到能最简单的思路解决问题的方式，也就是最好想的方式~但是想要成为优秀的攻城狮，就需要锻炼自己优化解决问题方式的能力，最短时间想到最优解。同时还需要具备在后续给出优化的可行方案！