经典排序算法总结

排序算法是离散数学和数据结构学科最基本的算法，虽然知道这些排序算法的名字，但是一直没有研究过它们的实现原理。现在把它们收集起来，并一一亲自实现，来加深对排序算法的理解。

1，冒泡排序：最简单的排序算法，从第一个元素开始比较相邻元素大小，如果前边元素大于后边元素则交换位置，否则将下标移到下一个元素，一直到最后一个元素为止；然后进行其他轮次的比较，直到没有元素交换结束。http://blog.csdn.net/aitazhixin/article/details/62040803

另外一种改进的冒泡排序算法为，将上一轮次比较中，最后一次元素交换的位置标记，作为下面一轮次比较的终点。http://blog.csdn.net/aitazhixin/article/details/62043245

2，插入排序：假设元素m之前的所有元素已排好顺序，则在排好序的子序中查找m的位置，然后插入m，得到一个增量的子序，循环下标到最后一个元素为止。http://blog.csdn.net/aitazhixin/article/details/62042293

3，选择排序：从未排序的序列中选择最小的元素，与第一个元素交换位置，然后对剩余的未排序子序进行相同的操作。

http://blog.csdn.net/aitazhixin/article/details/62043950

4，快速排序：快速排序采用分治递归的思想，首先选取一个参考元素（比如第一个元素），然后将剩余的元素分成两部分：一部分所有元素都小于参考元素，一部分所有元素都大于参考元素，然后将参考元素插入到分界点；对于分开的两部分，递归采用同样的方法获取分类，最终将获取到完整排序的数列。http://blog.csdn.net/aitazhixin/article/details/62045826

5，归并排序：基本原理是将两个已排序的数列归并成一个排序的数列，我采用了三元体的方式，在合并时做到整体插入。http://blog.csdn.net/aitazhixin/article/details/62053785

6，二叉排序树：基本思想是将序列中的数读入一个二叉树，在读入时遵循一定的规则：比如，如果二叉树的一个节点有左子节点，那么左子节点一定比父节点的值小；如果一个节点有右子节点，那么右子节点一定比父节点的值大。在二叉排序树制造完成后，通过采用中序遍历的方法读取二叉树节点的值到序列中，就可以得到一个升序序列。http://blog.csdn.net/aitazhixin/article/details/62229996

7，堆排序：基本原理是每次构造一个小顶堆，那么堆的根节点就是序列的最小值，然后利用剩余的元素再构造一个小顶堆，获得第二个较小的元素，递归运行直到剩余1个元素返回，最终将得到升序排列的序列。http://blog.csdn.net/aitazhixin/article/details/62416238