本文将通过动态演示+代码的形式系统地总结十大经典排序算法。
算法分类
十种常见排序算法可以分为两大类：
算法复杂度
排序算法
空间复杂度
数据对象稳定性
冒泡排序
O(n2)
O(n2)
O(1)
稳定
选择排序
O(n2)
O(n2)
O(1)
数组不稳定、链表稳定
插入排序
O(n2)
O(n2)
O(1)
稳定
快速排序
O(n*log2n)
O(n2)
O(log2n)
不稳定
堆排序
O(n*log2n)
O(n*log2n)
O(1)
不稳定
归并排序
O(n*log2n)
O(n*log2n)
O(n)
稳定
希尔排序
O(n*log2n)
O(n2)
O(1)
不稳定
计数排序
O(n+m)
O(n+m)
O(n+m)
稳定
桶排序
O(n)
O(n)
O(m)
稳定
基数排序
O(k*n)
O(n2)
稳定
算法思想：
代码：
算法思想：
代码：
算法思想：
代码：
算法分析：
插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
快速排序的基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
算法思想：
代码：
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。
算法思想：
代码：
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
算法思想：
代码：
1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。