排序算法

排序算法

1 . 插入排序：

直接插入排序：将一个记录插入到已排序好的有序表中，从而得到一个新的、记录数增1的有序表。即：先将序列的第一个记录看成是一个有序的子序列，然后从第二个记录逐个进行插入，直至整个序列有序为止。 要点: 设立哨兵，作为临时存储和判断数组边界之用。 如果碰见一个和插入元素相等的，那个把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

希尔排序： 把记录按步长gap分组，对每组记录采用直接插入排序方法进行排序。 随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到1，整个数据合成为一组，构成一组有序记录，则完成排序。

2 . 选择排序：

简单选择排序：在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换;然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换; 依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

二元选择排序 : 是简单选择排序的改进. 简单选择排序，每趟循环只能确定一个元素排序后的定位; 我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置, 从而减少排序所需的循环次数. 改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可。

堆排序 : 堆，是一棵完全二叉树，根的值大于左右子树中所有结点的值。 左右子树也是堆，除此之外，对其它元素之间的大小关系（如左右子树之间元素大小关系）没有要求。这是大根堆，如果把“大于”换成“小于”，就是小根堆。可以用数组来模拟堆。 堆排序(大根堆)实现原理 ： 将数组建立为一个堆，使得其满足所有的非叶节点的值都大于等于（或小于等于）其左右 孩子节点的值，这样的效果使得第一个节点，即根节点总是最大的元素。 从最后一个数组元素开始与数组第一个元素交换数据，交换一次后，再创新建立堆，但堆的长度减1，直到数组长度变为1为止，这样就排序完成。

3 . 交换排序

冒泡排序 ： 在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

快速排序 ： 选择一个基准元素, 通常选择第一个元素或者最后一个元素, 通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。此时基准元素在其排好序后的正确位置。然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

4 . 归并排序 ： 归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。