|
|
|
|
知识点：
快速排序
数组
排序
排序算法
|
|
关键词：
快速排序
数组
算法
排序
章/节：
计算机软件知识
|
|
|
|
|
|
|
|
对数组A=(2,8,7,1,3,5,6,4)用快速排序算法的划分方法进行一趟划分后得到的数组A为（62）(非递减排序， 以最后一个元素为基准元素)。进行一趟划分的计算时间为（63）。
|
|
|
|
|
| A.
(1,2,8,7,3,5,6,4)
|
|
|
| B.
(1,2,3,4,8,7,5,6)
|
|
|
| C.
(2,3,1,4,7,5,6,8)
|
|
|
| D.
(2,1,3,4,8,7,5,6)
|
|
|
|
|
|
|
|
| |
|
为保障您的权益，请登录
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 第60题
2010年下半年
|
|
46%
|
|
| 某一维数组中依次存放了数据元素15, 23, 38, 47, 55, 62, 88, 95, 102, 123, 采用折半（二分）法查找元素95时，依次与（60)进行了..
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
快速排序的基本思想是：通过一趟排序将待排的记录分割为独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后再分别对这两部分记录继续进行排序，以达到整个序列有序。
|
|
|
|
具体做法是：附设两个指针low和high，它们的初值分别指向文件的第一个记录和最后一个记录。设枢轴记录的关键字为Pivotkey，则首先从high所指位置起向前搜索，找到第一个关键字小于Pivotkey的记录并与枢轴记录互相交换，然后从low所指位置起向后搜索，找到第一个关键字大于Pivotkey的记录并与枢轴记录相互交换，重复这两步直至low=high为止。
|
|
|
|
在所有同数量级(O(nlog2n))的排序方法中，快速排序被认为是平均性能最好的一种，但是，若初始记录序列按关键字有序或基本有序时，快速排序将退化为冒泡排序，此时算法的时间复杂度为O(n2)。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n维数组是一种"同构"的数据结构，其每个元素类型相同、结构一致。数组是定长线性表在维数上的扩张，即线性表中的元素又是一个线性表。
|
|
|
|
数组结构的特点是：数据元素数目固定；数据元素具有相同的类型；数据元素的下标关系具有上下界的约束且下标有序。
|
|
|
|
|
|
|
|
（2）给定一组下标，修改相应的数据元素中某个数据项的值。
|
|
|
|
|
|
一旦定义了数组，结构中的数据元素个数和元素之间的关系就不再发生变动，因此数组适合于采用顺序存储结构。
|
|
|
|
由于计算机的内存结构是一维线性的，因此存储多维数组时必须按照某种方式进行降维处理，即将数组元素排成一个线性序列，这就产生了次序约定问题。对二维数组有两种存储方式：一种是以列为主序的存储方式；另一种是以行为主序的存储方式。
|
|
|
|
设每个数据元素占用L个单元，m、n为数组的行数和列数，那么以行为主序优先存储的地址计算公式为
|
|
|
|
Loc(aij)=Loc(a11)+((i-1)n+(j-1))L
|
|
|
|
|
|
Loc(aij)=Loc(a11)+((j-1)m+(i-1))L
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
假设含n个记录的文件内容为｛R1，R2，…，Rn｝，其相应的关键字为｛k1，k2，…，kn｝。经过排序确定一种排列｛Rj1，Rj2，…，Rjn｝，使得它们的关键字满足如下递增（或递减）关系：kj1≤kj2≤…≤kjn（或kj1≥kj2≥…≥kjn）。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
简单排序包括直接插入排序、冒泡排序、简单选择排序等方法。
|
|
|
|
|
|
直接插入排序的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。
|
|
|
|
|
|
首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序（即 r[1].key>r[2].key），则交换两个记录，接着比较第二个记录和第三个记录的关键字。依次类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。这个过程称为第一趟冒泡排序，使得关键字最大的记录被安置到最后一个记录的位置上。然后进行第二趟冒泡排序，对前n-1个记录进行同样的操作，结果是使关键字次大的记录被安置到第n-1个记录的位置上。当进行完第n-1趟冒泡排序时，所有记录都已有序排列。
|
|
|
|
|
|
简单选择排序的基本思想是：在进行每趟排序时，从无序的记录中选择出关键字最小（或最大）的记录，将其插入到有序序列（初始时为空）的尾部。
|
|
|
|
|
|
希尔排序又称"缩小增量排序"，是对直接插入排序方法的改进。希尔排序的基本思想是：先将整个待排记录序列分割成若干序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。
|
|
|
|
|
|
快速排序是对冒泡排序的一种改进。先通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后分别对这两部分记录继续进行排序，使得整个序列有序。
|
|
|
|
|
|
|
|
对于n个元素的关键字序列｛k1,k2,…,kn｝，当且仅当所有关键字都满足下列关系时称其为堆：
|
|
|
 或
|
|
|
|
从序列元素间的关系来看，堆是一棵完全二叉树的层次序列。显然，堆顶元素为序列中n个元素的最小值（或最大值）。若堆顶为最小元素，则称为小根堆；若堆顶为最大元素，则称为大根堆。
|
|
|
|
|
|
对一组待排序记录的关键字，首先把它们按堆的定义排成一个堆序列，从而输出堆顶的最小关键字，然后将剩余的关键字再调整成新堆，便得到次小的关键字，如此反复进行，直到全部关键字排成有序序列。
|
|
|
|
|
|
归并排序是不断将多个小而有序的序列合成一个大而有序的序列的过程。其中最常用的归并排序是二路归并排序，它是将整个序列中的元素进行分组，相邻的两个元素为一组，然后分别为每个小组进行排序，随后将两个相邻的小组合成一个组，继续进行组内排序；直到所有元素被合并成一个组内，并使组内元素有序，此时排序结束。
|
|
|
|
|
|
基数排序的思想是按组成关键字的各个数位的值进行排序，它是分配排序的一种。基数排序把一个关键字Ki看成一个d元组，即
|
|
|
|
|
其中 称为最高有效位，@ 称为最低有效位。基数排序可以从最高有效位开始，也可以从最低有效位开始。
|
|
|
|
基数排序的基本思想是：设立r个队列（r为基数），队列的编号为0, 1, 2, …,r-1。首先按最低有效位的值，把n个关键字分配到这r个队列中；然后从小到大将各队列中的关键字再依次收集起来；接着再按次低有效位的值把刚收集起来的关键字再分配到r个队列中。重复上述收集过程，直至最高位有效。这样得到了一个从小到大有序的关键字序列。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
