排序算法总结.doc

《排序算法总结.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、现有序列{9,3,5,1,6,2,8,4,7}，以此为例子，阐述各个常用排序算法。直接插入排序：　　每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。　　第一趟比较前两个数,然后把第二个数按大小插入到有序表中;第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。直接插入排序属于稳定的排序，时间复杂性为o(n^2)，空间复杂度为O(1)。9，3，5，1，6，2，8，4，73，9，5，1，6，2，8，4，73，5，9，1，6，2，8，4，71，3，5，9，6，2，8，4，71，3，5，6，

2、9，2，8，4，71，2，3，5，6，9，8，4，71，2，3，5，6，8，9，4，71，2，3，4，5，6，8，9，71，2，3，4，5，6，7，8，9希尔排序：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2

3、为3则分为三个组（2，1，5）（3，6，7）（4，8，9）得到：1，3，4，2，6，8，5，7，9取增量为1得到1，2，3，4，5，6，7，8，99，3，5，1，6，2，8，4，7增量＝5对同一颜色进行内部插入排序2，3，4，1，6，8，5，7，9增量＝31，3，4，2，6，8，5，7，9增量＝11，2，3，4，5，6，7，8，9冒泡排序：冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复以上

4、过程，仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到最大数前的一对相邻数，将小数放前，大数放后，第二趟结束，在倒数第二个数中得到一个新的最大数。如此下去，直至最终完成排序。9，3，5，1，6，2，8，4，73，5，1，6，2，8，4，7，93，1，5，2，6，4，7，8，91，3，2，5，4，6，7，8，91，2，3，4，5，6，7，8，91，2，3，4，5，6，7，8，91，2，3，4，5，6，7，8，91，2，3，4，5，6，7，8，9快速排序：设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常

5、选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。一趟快速排序的算法是：　　1）设置两个变量I、J，排序开始的时候：I=1，J=N-1；　　2）以第一个数组元素作为关键数据，赋值给X，即X=A[0]；　　3）从J开始向前搜索，即由后开始向前搜索（J=J-1），找到第一个小于X的值，让该值与X交换；　　4）从I开始向后搜索，即由前开始向后搜索（I=I+1），找到第一个大于X的值，让该值与X交换；5）重复第3、4步，直到I=J；9351628477351628494351628792351648792341658792314658

6、79123456879123456789123456789归并排序：归并排序（MERGESORT）是又一类不同的排序方法，合并的含义就是将两个或两个以上的有序数据序列合并成一个新的有序数据序列，因此它又叫归并算法。它的基本思想就是假设数组A有N个元素，那么可以看成数组A是又N个有序的子序列组成，每个子序列的长度为1，然后再两两合并，得到了一个N/2个长度为2或1的有序子序列，再两两合并，如此重复，直到得到一个长度为N的有序数据序列为止，这种排序方法称为2—路合并排序。9，3，5，1，6，2，8，4，73，9，1，5，2，6，4，8，71，3，5，9，2，4，6，8，7两次合并后1，2，3，4，

7、5，6，8，9，7第三次合并后1，2，3，4，5，6，7，8，9第四次合并后选择排序：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。　　选择排序是不稳定的排序方法。　　n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：　　①初始状态：无序区为R[1..n]，有序区为空。　　②第1趟排序　　在无序区R[1..n]