数据结构各种排序方法汇总.docx

数据结构各种排序方法汇总
1：直接插入排序
核心算法：

排序过程：

第零趟，固定58有序

第一趟，15<58,将15作为监视哨，前面有序的数列，所有大于15的右移一位。
将15放入空位。

第二趟，46<58,将46作为监视哨，然后在前面有序的数列中，所有大于46的右移一位，将46放入空位。

然后就不写了，太累了。。。。
注意：直接插入排序是一种稳定的排序方法。

2：希尔排序：
思路：将整个数组一次每5个，3个，1个一组，每次每组都进行直接插入排序，让每组都有序，这样，每5个和每3个一组的排完之后，最后一次时，数组已经基本有序，这样在进行一次直接插入排序就好了！

最后对这个家伙进行直接插入排序就好！

三：堆排序

堆排序的方法：
1）：建立初始堆：

将序列变成一个二叉树。如下图

从最后一个有孩子的结点开始做起，那么这里面就是36.对36和她的左右孩子进行一次筛选，把大的放在根节点上。再依次进行53,18,36,45的筛选工作。

2）：将最后一个元素和和第一个元素交换位置。

摘掉93，然后将最后一个元素36放到93的位置。
不是堆了，调整吧。
调整好了，哈哈，然后摘掉72.继续上述操作。

3：快速排序
思想方法
1）、先从待排序数中选一个数做为基准数。
2）、将所有比基准数小的放在它的左边，比它大的放在右边。
3）、对划分好的左右区间各自独立执行前两步，直至有序。
具体步骤
1）：
给定一组数，让最小的指针为i，最大的为j。设置第一个数字45为明星数字，一次快速排序完成后，明星数字的左边都比明星数字小，右边的都比他大。
2）：从j开始，在[i,j]之间找寻比明星数字45小的，好了，找到了21。
那么21和明星数字45替换。然后j--,成为了：
21 33 58 67 51 12 45 45
i j
3)：从i开始向后找，在[i,j]之间找寻比明星数字45大的，和明星数字互换。好了，58找到了！然后i++。
21 33 45 67 51 12 58 45
i j
4）：重复2），3）。直至明星数字的左边都比他小，右面都比他大。

4：归并排序

算法：

五：冒泡排序

冒泡排序是一种稳定的算法。
六：选择排序
For(i=1;i<n;i++)
for(j=i+1,j<=n,j++)
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}