直接插入排序
- 前提条件
前 i-1 个元素是有序的，第i个元素依次从第i-1个元素往前比较，直到找到一个比第i个元素值小的元素，而后插入及其后的元素依次向后移动。 - 当给出一队无需的元素时，首先，应该将第1个元素看做是一个有序的队列，而后从第2个元素起，按插入排序规则，依次与前面的元素进行比较，直到找到一个小于他的值，才插入。
希尔排序
- 希尔排序又称“缩小增量排序”，是对直接插入排序方法的改进。
希尔排序的基本思想是：先将整个待排序记录序列分割成若干子序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，在对全体记录进行一次直接插入排序。
-具体做法是：先取一个小于n得到整数d1作为第一个增量，把文件的全部记录分成d1个组，将所有距离为d1倍数的记录放在同一个组中，在各组内进行直接插入排序；然后又取第二个增量d2（d2<d1）,重复上述分组和排序工作，依次类推，直至所取的增量di=1（di<di-1<..<d2<d1）,既所有记录放在同一组进行直接插入排序为止。 - 按上述，希尔排序实际是为了解决大数据的排序问题，当待排序的数据很多时，使用直接插入排序效率很低，因此，采取分组的方式，使问题细化，可以提高效率，适用于多数据。
简单选择排序
- n个记录进行简单选择排序的基本方法是：通过n-i（1<=i<=n）次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录进行交换，当i等于n时所有记录有序排列。
- 按上述，本质是每次选择出最小的元素进行交换，主要是选择比较过程，交换过程只有1次。
堆排序
对于n个元素的关键字序列｛k1，k2，...,kn｝,当且仅当满足下列关系时
称为堆排序，期中2i和2i+1需不大于n。
堆排序的基础思想是：对一组待排序记录的关键字，首先按堆的定义排成一个序列（即建立初始堆），从而可以输出堆顶的最大关键字（对于大根堆而言），然后将剩余的关键字再调整成新堆，便得到次大的关键字，如此反复，直到全部关键字排成有序序列为止。
冒泡排序
- n个记录进行冒泡排序的方法是：
首先将第一记录的关键字和第二个记录的关键字进行比较，若为逆序，则交换这两个记录的值，然后比较第二个记录和第三个记录的关键字，依次类推直到n-1个记录的第n个记录的关键字比较过为止。上述过程称为一趟冒泡排序，其结果是关键字最大的记录被交换到第n个记录的位置上。然后进行第二趟冒泡排序，对前n-1个记录进行同样的位置上。最多进行n-1趟，所有记录有序排序。若在某趟冒泡排序过程没有进行相邻位置的元素交换处理，则可结束排序过程。 - 实例给的是从后往前排序，也是可以的，需要从最后两个元素开始进行比较，将较小的元素交换到前面去，依次进行比较交换，比较是为了交换，交换的次数很多。区分冒泡排序和简单选择排序。
快速排序
- 快速排序是将n个记录分成两块，在递归，实际分成两块的方式如图所示：
设定一基准为57，设定两个指针high=1，low=n，从low指向的第n个元素开始，与基准值进行比较，若小于基准值，则与基准值交换 low--，此时，转而从high指向的第1个元素开始和基准值进行比较，若大于基准值，则和基准值进行交换，此时，又转而从low-指向的值和基准进行比较，重复上述过程。
- 要注意的是：每次都是和基准值进行比较，因此最终是以基准值为中间，将队列分成两块。只有当和基准值发生了交换，才表换high和low的指针的计数，否则会一直low--下去。
- 上图中，最终以 57 为界，左边都是小于57的元素，右边都是大于57的元素，完成一次快速排序，接着对两块再分别进行递归即可。
归并排序
将两个或两个以上的有序文件合并成为一个新的有序文件。归并排序的一种实现方式是把一个有n个记录的无序文件看成是由n个长度为1的有序子文件组成的文件，然后进行两两归并，得到 [n/2] 个长度为2或1的有序文件，再两两归并，如此反复，直到最后形成包含n个记录的有序文件为止。这种反复将两个有序文件归并成一个有序文件的排序方法称为两路归并排序。
- 一般归并排序都是用来合并多个线性表，对单列数据，二路归并排序可以对元素进行两两合并，示例如下：
对第三次归并，将53和28比较，28小，放入新表头，52再与33比较，33放入新表，52再与72比较，52放入新表，57再与72比较，57放入新表.....
基数排序
基数排序是基于多个关键字来进行多轮排序的，本质也是将问题细分，如图例子，分别按个位、十位、百位的大小作为关键字进行了三轮排序，最终得出结果。
排序算法解决
- 若待排序的记录数目n较小，可采用直接插入排序和简单选择排序。由于直接插入排序所需的记录移动操作较简单选择排序多，因此当记录本身信息量较大时，用简单选择排序方法较好。
- 若待排序记录按关键字基本有序，则宜采用直接插入排序或冒泡排序。
- 但n很大且关键字的位数较小时，采用链式基数排序较好。
- 若n较大，则赢2采用时间复杂度为O（nlogn）的排序方法；例如快速排序、堆排序或归并排序。
文章评论