| « | Mar.2026 | » | | 日 | 一 | 二 | 三 | 四 | 五 | 六 | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | | | | | |
|
|
| [技术文档]关于排序的认识 |
|
排序总的可以分为插入排序，交换排序，选择排序，归并排序，基数排序等。
其中插入排序又可以细分为直接插入排序，折半排序，希尔排序。
直接排序的基本思想是：当插入第i （i>=1）个对象时，前面的v[0]，v[1]，…….v[i-1]已经排好序，这时，用v[i]的关键码与v[i-1],v[i-2]……的关键码顺序进行比较，找到插入位置即将v[i]插入，原来位置上的对象向后顺移。直接插入排序的时间复杂度为n2,直接插入排序是一种稳定的排序方法。
折半排序的基本思想是：设在顺序表中有一个对象序列v[0]，v[1]，….v[n-1]，其中，v[0]，v[1]，….v[i-1]是已经排好序的对象。在插入v[i]时，利用折半查找法寻找v[i]的插入位置。折半插入是一种稳定的排序方法。
希尔排序：当待排序的数列很长时，（即n很大时），关键码平均比较次数和对象平均移动次数大约在n1.25（即n的1.25次方，以下同样）到1.6n1.25范围内。
交换排序又可细分为冒泡排序，快速排序。
冒泡排序的基本思想是：设待排序的数列的大小为n，首先比较v[n-2]和v[n-1]的大小，如果v[n-2]>v[n-1],则交换v[n-2]和v[n-1]，然后对v[n-2]和v[n-3]作相同的处理，如此处理， 直到处理完v[0]和v[1],这个称为一趟冒泡，所以只要经过n-1 趟冒泡就可以排好所有对象。 在最坏情况下总的关键码比较次数为0.5n(n-1),对象移动次数为1.5n（n-1）
快速排序的基本思想是：取待排序的数列的某个对象（例如第一个对象）作为基准，将对象分为左右两个数列，左边的全都小于基准，右边的全都大于基准，然后对左右两个树列重复以上操作，直到全部完成。它是一种不稳定的方法，对于待排序的数列很大时，快速排序的确很快，但当待排序的数列很小时，它往往比其它简单的排序方法还要慢。
选择排序又可以细分为直接选择排序，堆排序。
直接选择排序的最坏情况是每一趟都要进行交换，总的对象移动次数是3(n-1)。
堆排序可以分为两个步骤：首先，根据初始输入数据，利用堆的调整算法FilterDown()形成初始堆， 第二步通过一系列的对象交换和重新调整堆进行排序。堆排序的是一个不稳定的排序方法，并且当待排序的数列很大时，堆排序不可取。
归并排序就是将两个或两个以上的有序表合并成一个新的有序表。
基数排序的基本思想是：待排序的对象按m个关键码key[0],…..key[m-1]排序，每个对象的关键码域用一个数组key[m]表示，对各关键码的排序采用箱排序。
从上面可以得出结论（本人观点），当待排序的数列很小时，可以采取直接插入排序，折半排序，希尔排序，直接选择排序，堆排序，归并排序，基数排序等众多排序方法，但当待排序的数列很大时，采用快速排序为优。
就平均性能而言，我认为快速排序最好。 | |
|
|
|
|
| 公告 |
人在上海不断的学技术,学生活,再苦再累也要坚持! |
| 统计 |
blog名称:
日志总数:20
评论数量:37
留言数量:0
访问次数:81073
建立时间:2006年7月5日 | |
