排序算法可以说是计算机专业学生要学习的最基础的算法，但其实也是最重要的，现在大部分互联网公司笔试面试也都会涉及到排序算法的知识。除了了解思想之外，还应该动手写一写，分析一些具体思路、时间复杂度、空间复杂度和稳定性等。

我们面试讨论小分队也简单讨论了一下排序算法，为了加深记忆，我自己也动手写了一些代码（Linux平台写的，自己测试是通过了），并做一些分析（由于水平较水，代码可能有误！）。

9种排序算法分别为：选择排序、冒泡排序、插入排序、希尔排序、归并排序、堆排序、快速排序、计数排序、基数排序！

1. 选择排序

基本思想：从第一个位置开始依次选择该位置的元素，第i次扫描就可以选出第i小的元素，思想很简单，现在用的较少。

特点：平均时间复杂度O(n^2)，最坏时间复杂度O(n^2)，额外空间O(1)，不稳定排序（举例：序列5 8 5 2 9， 第一遍选择第1个元素5会和2交换，原序列中2个5的相对前后顺序就被破坏了），n较小时较好！

代码：