排序是一个经典的问题，它以一定的顺序对一个数组或列表中的元素进行重新排序。而排序算法也是各有千秋，每个都有自身的优点和局限性。虽然这些算法平常根本就不用自己去编写，但作为一个有追求的程序员，还是要了解它们从不同角度解决排序问题的思想。
学习算法是枯燥的，那怎么高效的理解它的原理呢？显然，如果以动图的方式，生动形象的把算法排序的过程展示出来，非常有助于学习。visualgo.net 就是一个可视化算法的网站，第一次访问的时候，真的是眼前一亮。本文就对常用的排序进行下总结。
1. 冒泡排序冒泡排序的基本思想就是：把小的元素往前调或者把大的元素往后调。假设数组有 N 个元素，冒泡排序过程如下：
从当前元素起，向后依次比较每一对相邻元素(a,b)
如果 a>b 则交换这两个数
重复步骤1和2，直到比较最后一对元素（第 N-2 和 N-1 元素）
此时最大的元素已位于数组最后的位置，然后将 N 减 1，并重复步骤1，直到 N=1
冒泡排序的核心代码：
public static void bubbleSort(int[] a, int n) { // 排序趟数，最后一个元素不用比较所以是 (n-1) 趟 for (int i = 0; i < n - 1; i++) { // 每趟比较的次数，第 i 趟比较 (n-1-i) 次 for (int j = 0; j < n - 1 - i; j++) { // 比较相邻元素，若逆序则交换 if (a[j] > a[j+1]) { int tmp = a[j]; a[j] = a[j+1]; a[j+1] = tmp; } } } }难点在于边界的确定，算法分析：
平均时间复杂度是 O(n^2)，最佳情况是 O(n)，最差情况是 O(n^2)
空间复杂度 O(1)
稳定的排序算法（相等元素的前后顺序排序后不变）
2. 选择排序选择排序的基本思想就是：每次从未排序的列表中找到最小(大)的元素，放到已排序序列的末尾，直到所有元素排序完毕。假设数组有 N 个元素且 L=0，选择排序过程如下：
从 [L...N-1] 范围中找到最小元素的下标 X
交换第 X 与第 L 位置的元素值
L 加 1，重复以上步骤，直到 L=N-2
选择排序的核心代码：
public static void selectionSort(int[] a, int n) { // 排序趟数，最后一个元素是最大的不用比较所以是 (n-1) 趟 for (int i = 0; i < n-1; i++) { int minIndex = i; // 无序列表中最小元素的下标 for (int j = i+1; j < n; j++) { // 在无序列表中查找最小元素的小标并记录 if (a[j] < a[minIndex]) { minIndex = j; } }// 将最小元素交换到本次循环的前端 int tmp = a[minIndex]; a[minIndex] = a[i]; a[i] = tmp; } }算法分析：
平均时间复杂度是 O(n^2)，最佳和最差情况也是一样
空间复杂度 O(1)
不稳定的排序算法（相等元素的前后顺序排序后可能改变）
3. 插入排序插入排序的基本思想是：每次将待插入的元素，按照大小插入到前面已排序序列的适当位置上。插入排序过程如下：
从第一个元素开始，该元素可认为已排序
取出下一个元素，在已排序的元素序列中从后向前扫描
如果该元素（已排序）大于待插入元素 ，把它移到下一个位置
重复步骤 3，直到找到一个小于或等于待插入元素的位置，将待插入元素插入到下一个位置
重复步骤 2~5，直到取完数组元素
插入排序的核心代码：
public static void insertionSort(int[] a, int n) { // a[0] 看做已排序 for (int i = 1; i < n; i++) { int x = a[i]; // 待插入元素 int j=i-1; // 插入的位置 while (j >= 0 && a[j] > x) { a[j+1] = a[j]; // 为待插入元素腾地 j--; } a[j+1] = x; // 插入到下一个位置 j+1 } }算法分析：
平均时间复杂度是 O(n^2)，最佳情况是 O(n)，最差情况是 O(n^2)
空间复杂度 O(1)
稳定的排序算法
4. 希尔排序希尔排序也称为增量递减排序，是对直接插入算法的改进，基于以下两点性质：
插入排序在对几乎已排好序的数据操作时，效率高，可以达到线性排序的效率
但插入排序一般来说是低效的，因为插入排序每次只能移动一位数据