|
|
| 又称分类”。按关键字大小递增或递减的次序，对文件中的全部记录重新排列的过程。是计算机程序设计中的一种重要运算。分内部排序和外部排序两大类。内部排序中常用的方法有插入排序、冒泡排序、快速排序、堆排序、基数排序等。 |
|
排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。
内部排序和外部排序：
若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；
反之，若参加排序的记录数量很大，
整个序列的排序过程不可能在内存中
完成，则称此类排序问题为外部排序。
内部排序的过程是一个逐步扩大
记录的有序序列长度的过程。
一、冒泡排序
已知一组无序数据a、a、……a[n]，需将其按升序排列。首先比较a与a的值，若a大于a则交换两者的值，否则不变。再比较a与a的值，若a大于a则交换两者的值，否则不变。再比较a与a，以此类推，最后比较a[n-1]与a[n]的值。这样处理一轮后，a[n]的值一定是这组数据中最大的。再对a~a[n-1]以相同方法处理一轮，则a[n-1]的值一定是a~a[n-1]中最大的。再对a~a[n-2]以相同方法处理一轮，以此类推。共处理n-1轮后a、a、……a[n]就以升序排列了。
优点：稳定，比较次数已知；
缺点：慢，每次只能移动相邻两个数据，移动数据的次数多。
二、选择排序
已知一组无序数据a、a、……a[n]，需将其按升序排列。首先比较a与a的值，若a大于a则交换两者的值，否则不变。再比较a与a的值，若a大于a则交换两者的值，否则不变。再比较a与a，以此类推，最后比较a与a[n]的值。这样处理一轮后，a的值一定是这组数据中最小的。再将a与a~a[n]以相同方法比较一轮，则a的值一定是a~a[n]中最小的。再将a与a~a[n]以相同方法比较一轮，以此类推。共处理n-1轮后a、a、……a[n]就以升序排列了。
优点：稳定，比较次数与冒泡排序一样，数据移动次数比冒泡排序少；
缺点：相对之下还是慢。
三、插入排序
已知一组升序排列数据a、a、……a[n]，一组无序数据b、b、……b[m]，需将二者合并成一个升序数列。首先比较b与a的值，若b大于a，则跳过，比较b与a的值，若b仍然大于a，则继续跳过，直到b小于a数组中某一数据a[x]，则将a[x]~a[n]分别向后移动一位，将b插入到原来a[x]的位置这就完成了b的插入。b~b[m]用相同方法插入。（若无数组a，可将b当作n=1的数组a）
优点：稳定，快；
缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决这个问题。
四、缩小增量排序
由希尔在1959年提出，又称希尔排序。
已知一组无序数据a、a、……a[n]，需将其按升序排列。发现当n不大是，插入排序的效果很好。首先取一增量d(d<n)，将a、a[1+d]、a[1+2d]……列为第一组，a、a[2+d]、a[2+2d]……列为第二组……，a[d]、a[2d]、a[3d]……列为最后一组以次类推，在各组内用插入排序，然后取d'<d，重复上述操作，直到d=1。
优点：快，数据移动少；
缺点：不稳定，d的取值是多少，应取多少个不同的值，都无法确切知道，只能凭经验来取。
五、快速排序
快速排序是冒泡排序的改进版，是目前已知的最快的排序方法。
已知一组无序数据a、a、……a[n]，需将其按升序排列。首先任取数据a[x]作为基准。比较a[x]与其它数据并排序，使a[x]排在数据的第k位，并且使a~a[k-1]中的每一个数据<a[x]，a[k+1]~a[n]中的每一个数据>a[x]，然后采用分治的策略分别对a~a[k-1]和a[k+1]~a[n]两组数据进行快速排序。
优点：极快，数据移动少；
缺点：不稳定。 |
|
排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。
内部排序和外部排序：
若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；
反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。
内部排序的过程是一个逐步扩大记录的有序序列长度的过程。
内排序的方法有许多种，按所用策略不同，可归纳为五类：插入排序、选择排序、交换排序、归并排序和分配排序。
其中，插入排序主要包括直接插入排序和希尔排序两种；选择排序主要包括直接选择排序和堆排序；交换排序主要包括气（冒）泡排序和快速排序。
一、冒泡排序
已知一组无序数据a、a、……a[n]，需将其按升序排列。首先比较a与a的值，若a大于a则交换两者的值，否则不变。再比较a与a的值，若a大于a则交换两者的值，否则不变。再比较a与a，以此类推，最后比较a[n-1]与a[n]的值。这样处理一轮后，a[n]的值一定是这组数据中最大的。再对a~a[n-1]以相同方法处理一轮，则a[n-1]的值一定是a~a[n-1]中最大的。再对a~a[n-2]以相同方法处理一轮，以此类推。共处理n-1轮后a、a、……a[n]就以升序排列了。
优点：稳定；
缺点：慢，每次只能移动相邻两个数据。
二、选择排序
冒泡排序的改进版。
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
选择排序是不稳定的排序方法。
n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：
①初始状态：无序区为R[1..n]，有序区为空。
②第1趟排序
在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
……
③第i趟排序
第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。
优点：移动数据的次数已知（n-1次）；
缺点：比较次数多。
三、插入排序
已知一组升序排列数据a、a、……a[n]，一组无序数据b、b、……b[m]，需将二者合并成一个升序数列。首先比较b与a的值，若b大于a，则跳过，比较b与a的值，若b仍然大于a，则继续跳过，直到b小于a数组中某一数据a[x]，则将a[x]~a[n]分别向后移动一位，将b插入到原来a[x]的位置这就完成了b的插入。b~b[m]用相同方法插入。（若无数组a，可将b当作n=1的数组a）
优点：稳定，快；
缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决这个问题。
三、缩小增量排序
由希尔在1959年提出，又称希尔排序(shell排序)。
已知一组无序数据a、a、……a[n]，需将其按升序排列。发现当n不大时，插入排序的效果很好。首先取一增量d(d<n)，将a、a[1+d]、a[1+2d]……列为第一组，a、a[2+d]、a[2+2d]……列为第二组……，a[d]、a[2d]、a[3d]……列为最后一组以次类推，在各组内用插入排序，然后取d'<d，重复上述操作，直到d=1。
优点：快，数据移动少；
缺点：不稳定，d的取值是多少，应取多少个不同的值，都无法确切知道，只能凭经验来取。
四、快速排序
快速排序是目前已知的最快的排序方法。
已知一组无序数据a、a、……a[n]，需将其按升序排列。首先任取数据a[x]作为基准。比较a[x]与其它数据并排序，使a[x]排在数据的第k位，并且使a~a[k-1]中的每一个数据<a[x]，a[k+1]~a[n]中的每一个数据>a[x]，然后采用分治的策略分别对a~a[k-1]和a[k+1]~a[n]两组数据进行快速排序。
优点：极快，数据移动少；
缺点：不稳定。
五、箱排序
已知一组无序正整数数据a、a、……a[n]，需将其按升序排列。首先定义一个数组x[m],且m>=a、a、……a[n]，接着循环n次，每次x[a]++.
优点：快，效率达到O(1)
缺点：数据范围必须为正整数并且比较小
六、归并排序
归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。
归并排序是稳定的排序.即相等的元素的顺序不会改变.如输入记录 1(1) 3(2) 2(3) 2(4) 5(5) (括号中是记录的关键字)时输出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按输入的顺序.这对要排序数据包含多个信息而要按其中的某一个信息排序,要求其它信息尽量按输入的顺序排列时很重要.这也是它比快速排序优势的地方. |
|
paixu
排序
sorting
将文件中的各个记录按关键字值（见数据查找）的递升或递降次序重新排列成为一个新的记录序列，这是数据处理的一项基本功能。经过排序的文件便于分类比较或进一步处理。例如，对于一个未经排序的文件，在查毕整个文件之前不能判定某个给定的关键字值确实不在该文件中。组织排序之后，则无需查毕整个文件就能作出这一判断。排序是数据处理，特别是批处理任务中最常用的操作之一。对计算机内存储器中的记录进行排序称为内排序。对存储在外部设备中的文件记录排序称为外排序，外排序需要以内存储器作为过渡介质来进行。
内排序 常用的内排序有三种算法。
①线性查找排序算法 以线性查找法为基础的排序算法。在内存储器中确定一个与被排序文件同样大小的区域作为新区，用线性查找法在原文件中找出具有最小（或最大）关键字值的记录,放入新区第一记录位置,再从原文件中找出第二个最小（或最大）关键字值的记录，放入新区第二个记录位置。重复上述过程，直至原文件中所有记录都已放入新区为止。这种算法简单，但效率很低，只适于对少量记录的排序。
②互换排序算法 对原文件中不合指定顺序的两相邻记录互换位置。有三种互换算法。a.线性查找互换算法：将第一记录逐一与其后面的记录比较，并与较小关键字值的记录互换，结果使最小关键字值的记录处于第一记录位置。然后从第二记录开始，重复上述过程，使第二小关键字值记录处于第二记录位置。如此继续，直到关键字值最大的记录处于最后记录位置为止。b.相邻比较互换算法：将相邻记录比较，并按指定次序互换其位置。第一个记录和第二个记录比较，第二个和第三个比较，直到倒数第二个和最后一个比较。从头到尾算完一遍，然后进行第二遍，直至某一遍没有一个比较需要互换位置时为止。c.起泡互换排序算法：首先将第二个记录与第一个记录比较，必要时互换。然后将第三个记录与第二个记录比较，必要时互换。若互换，则新的第二个记录与第一个记录比较，必要时互换。第三个记录再与第二个记录比较，重复上述过程。使一个记录如同起泡一样，上升到适当的位置，在它上面再没有关键字值比它大（或小）的记录。直到最后一个记录经过比较而不再上升为止。
③合并排序算法 先将文件中的各个记录分为合乎次序的若干组，然后分别两组两组地合并，使组数减少一半；再如此继续合并，直到全部合为一组为止。
外排序 外排序包括两个步骤。①把要排序的文件中的一组记录读入内存储器的排序区，对读入的记录按上面讲到的内排序法进行排序，排序之后输出到外存储器。重复这一过程，每次一组，直到原文件所有记录被处理完毕。②将上一步分组排好序的记录两组两组地合并排序。在内存容量允许的条件下，每组中包含的记录越大越好，这样可减少合并的次数。
（罗大卫）
|
|
- : rank, reorder, Sorting
- n.: compositor, ordering, taxis
- v.: sort
- vt.: collate
|
|
- n. mise en ordre
|
|
| 编程 | 算法 | 分治 | vb | 超链分析 | 搜索引擎 | 相关性 | pagerank | | 计算机 | 冒泡排序 | 冒泡 | 冒泡法 | 选择 | 定位 | 交换 | 程序 | | 数据结构 | 更多结果... |
|