...排序代码为{46,79,56,38,40,84},则利用快速排序的方法,以第一个记录...
发布网友
发布时间:2024-04-14 18:45
我来回答
共3个回答
热心网友
时间:2024-04-14 22:02
设待排序序列为{L.r[1],L.r[2],…,L.r[n]),首先任意选取一个记录(通常选择第一个记录L.r[1])作为支点(pivot),然后按照下述原则排列其余记录:将所有关键字比L.r[1].key小的记录都安排在它的位置之前,将所有关键字比L.r[1].key大的记录都安排在它的位置之后。可以发现,在安置的过程中,L.r[1]的确切位置将被最终确定。设该支点(pivot)最后确定的位置为i,则将序列分割为左右两部分。这个过程称为一趟快速排序。
设待排序序列用数组e[low..high]保存。设置两个指针low和high,分别指向数组的开始位置和终止位置。设支点记录为e[low],并将之暂存于t。
首先,从high的位置向前搜索,找到第一个小于t的记录,将这个记录和e[low]的值交换;然后,从low所指向的位置向后搜索,找到第一个值大于t的记录,将这个记录和e[high]的值交换。重复以上步骤,直到low=high。完成一趟排序,low(或者high)指向的位置就是第一个元素的确切位置(从两边向中间“夹挤”)。
第一趟完成后,确定了第一个元素的确切位置,同时生成了两个子序列,然后再对这两个序列使用同样的办法,最终实现整个序列的有序。
扩展资料:
快速排序通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
在以49为中点分割这个数据序列,分别对前面一部分和后面一部分进行类似的快速排序,从而完成全部数据序列的快速排序,最后把此数据序列变成一个有序的序列,根据这种思想对于上述数组A的快速排序。
热心网友
时间:2024-04-14 22:00
46<->40
79<->46
46<->38
56<->46
这是第一轮的交换过程
热心网友
时间:2024-04-14 21:58
一组记录的排序代码为{46,79,56,38,40,84},则利用快速排序的方法,以...
设待排序序列为{L.r[1],L.r[2],…,L.r[n]),首先任意选取一个记录(通常选择第一个记录L.r[1])作为支点(pivot),然后按照下述原则排列其余记录:将所有关键字比L.r[1].key小的记录都安排在它的位置之前,将所有关键字比L.r[1].key大的记录都安排在它的位置之后。可以发现,在安置...
数据结构的问题~
3 在一个顺序表的表尾插入一个元素的时间复度的量级为( )。 A O(n) B O(1) C O(n2) D O(log n) 4 表长为n的顺序存储的线性表,当在任意位置上插入或删除一个元素的概率相等时,插入一个元素所需移动元素的平均个数为( ),删除一个元素需要移动元素的平均个数为( ) A (n-1)/2 B n C (...
求几道数据结构选择题答案?以下:
D) 84,56,79,40,46,38 15.若一组记录的关键码为(46,79,56,38,40,84),则利用快速序的方法,以第一个记录为基准得到的第一趟结果为 A) 38,40,46,56,79,84 B) 40,38,46,79,56,84 C)40,38,46,56,79,84 D) 40,38,46,84,56,79 16.B 17.下列...
下面的题目容易混淆,求各位高手帮忙解释!!!
2. 第一次,40,79,56,38,46,84;第二次:40,46,56,38,79,84;第三次:40,38,56,46,79,84;第四次:40,38,46,56,79,84 3. (25,48),(16,35),(79,82),(23,40),(36,72)(25,48,16,35),(79,82,23,40),(36,72)→(16,25,35,48),(23,40,79,82)...
若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一...
则采用仅有尾指针的单循环链表存储方式最节省运。仅有尾指针的单循环链表,可以非常方便地找到尾结点,尾结点后面的第一个结点往往是头结点,头结点的下一个结点就是第线性表的第一个结点。对最后一个元素和第一个元素操作对带尾指针的单循环链表是非常方便的。
一组记录的关键字序列为(37,70,47,29,31,85),利用快速排序,_百度...
while(q->datadatanext=q->next; free(q); q=p->next; } 另外Delete_Between函数里应该先判断如果mink大于maxk则返回,否则继续。
c++之数据排序
选择排序(1) 基本思想:每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在待排序的数列的最前,直到全部待排序的数据元素排完。(2)排序过程: 【示例】:初始 关键字 [49 38 65 97 76 13 27 49]第一趟排序后 13[38 65 97 76 49 27 49]第二趟排序后 13 27[65 97 76 49 38 49]...
有关匹配和排序的算法,高手帮帮忙哈
一、插入排序(Insertion Sort)1. 基本思想: 每次将一个待排序的数据元素,插入到前面已经排好序的数列中的适当位置,使数列依然有序;直到待排序数据元素全部插入完为止。2. 排序过程: 【示例】:[初始关键字] [49] 38 65 97 76 13 27 49 J=2(38) [38 49] 65 97 76 13 27 49 J=3(65) [38 49 ...
快速排序算法(free pascal)详解,不要源程序,时间复杂度n(logn);谢了/...
快速排序法是所有排序方法中速度最快、效率最高的方法。程序如下:var a:array[0..10] of integer;n:integer;procedure qsort(l,r:longint);{r,l表示集合的左右边界,即把第r到第l个数进行排序} var i,j,m:longint;begin m:=a[l];{标准数} i:=l; {I,J为指针} j:=r;repeat...
java怎么让数组的数字从大到小排序?
将数字从大到小排序的方法:例如简一点的冒泡排序,将第一个数字和后面的数字逐个比较大小,如果小于,则互换位置,大于则不动。此时,第一个数为数组中的最大数。然后再将第二个数与后面的数逐个比较,以次类推。示例代码如下: public class Test { public static void main(String[] args) { ...