排序算法总结

分类

排序算法

排序基本思想(升序)

交换排序

冒泡排序

1、首先将第1个和第2个关键字比较大小，如果第1个比第2个小，则交换，再对第2个和第 3个进行比较，以此类推，重复进行上述计算，直到完成第(n-1)和第n个记录关键字进行比较；

2、再按照上述方式进行第2次、第3次排序，直到整个序列有序为止；

快速排序

1、从数列中找出一个基准值

2、将所有比基准值小的放在基准值的前面，比基准值大的放在基准值的后面；

3、递归的把基准值前面的子数列和基准值后面的子数列进行排序

插入排序

简单插入排序

1、将n个待排序的元素看成一个有序表和一个无序表；

2、开始时有序表表只含有1个元素，无序表含有n-1个元素；

3、每次从无序表中取出1个元素，将它插入到有序表中适当的位置，使之成为新的有序表，重复n-1次可完成排序过程；

希尔排序(对插入排序的改进又名缩小增量排序)

1、将待排序的序列按某种规则分成几个子序列，分别对几个子序列进行直接插入排序。

2、这个规则就是增量，增量选取很重要，增量一般选序列长度一半，然后逐半递减，直到最后一个增量为1，为1相当于直接插入排序。

选择排序

简单选择排序

1、从n个待排序列中选出最小的一个放在序列的起始位置；

2、然后从剩余未排序中找出最小的元素，放在已排序序列的末尾；

3、以此为推，直到所有待排序列的元素为零；

堆排序(完全二叉树的结构)

大顶堆: 每个结点的值都大于或等于其子结点的值；(升序排序)

小顶堆：每个结点的值小于或等于其子结点的值；(降序排序)

1、将待排序列构造成一个大顶堆；

2、将顶端的数有末尾的数交换，此时末尾的树为最大数；

3、将剩余的n-1个数构造成大顶堆，再将顶端树与n-1位置的数交换，如此反复的执行；

归并排序

(分治算法:将一个大的问题划分为n个规模较小而结构相似的子问题)

二路归并

二路归并排序的宗旨:”分解”与归并

1、分解:

   A将一个数组分成两个数组，分别对两个数组进行排序；

   B循环第一步，直到划分出来的小数组只包含一个元素，只有一个元素的数组默认已经排好序；

2、归并：

   A将两个有序的数组合并到一个大的数组中

   B从最小的只包含一个元素的数组开始两两合并；

多路归并排序

1、按可用内存的大小，把外存上含有n个记录的文件分成若干个长度为L的子文件，把这些文件一次读入到内存，并利用有效的内部排序方法对它们进行排序，在将排序后得到的有序子文件重新重新写入外存；

2、对这些有序子文件逐趟归并，使其逐渐由小到大，直至得到整个有序文件为止。