莱芜手机网站设计公司,搜索动图素材的网站,北京网站建设找德冿朴,网站架构设计师工资目录 一、内排序和外排序二、排序算法的稳定性三、插入排序#xff08;一#xff09;直接插入排序的步骤#xff08;二#xff09;直接插入排序的稳定性#xff08;三#xff09;折半插入排序的步骤#xff08;四#xff09;希尔排序的步骤 四、交换排序#xff08;一… 目录 一、内排序和外排序二、排序算法的稳定性三、插入排序一直接插入排序的步骤二直接插入排序的稳定性三折半插入排序的步骤四希尔排序的步骤 四、交换排序一冒泡排序的步骤二冒泡排序的趟数和比较次数三快速排序的步骤四快速排序的稳定性 五、堆排序一堆排序的步骤二堆排序的稳定性三堆排序的时间复杂度 六、归并排序一k路归并排序的步骤二k路归并排序的稳定性三二路归并排序的步骤 七、排序算法的综合运用 一、内排序和外排序 1、内排序和外排序有什么区别内排序有哪些算法 答根据排序过程中数据元素是否完全在内存中进行可分为内排序和外排序。内排序有直接/折半插入排序、简单旋转排序、冒泡排序、希尔排序、快速排序和堆排序。
二、排序算法的稳定性 1、什么是稳定排序 答经过排序后能使关键字相同的元素保持原本顺序中的相对位置不变则称这个算法是稳定的反之则不稳定。
三、插入排序
一直接插入排序的步骤 1、简述直接插入排序算法的基本思想。 答直接插入排序是将要排序的序列按照关键字的大小插入至已排好序的子序列中一直进行直到整个序列有序。
二直接插入排序的稳定性 1、直接插入排序算法是不是稳定的排序方法 答由于每次插入元素时总是从后向前比较后再移动所以不会出现相同元素相对位置发生变化的情况即直接插入排序是稳定的。
三折半插入排序的步骤 1、简述折半插入排序算法的基本思想。 答折半插入排序的具体步骤如下 初始化一个已排序序列该序列只包含第一个元素从第二个元素开始通过折半查找确定每个待排序元素的插入位置根据已排序序列中元素的中点比较待排序元素与中点元素的大小若待排序元素大于中点元素则插入位置在中间位置的右侧否则插入位置在中间位置的左侧然后插入元素同时需要将插入位置及其之后的所有元素向后移动一位以为待排序元素腾出空间重复步骤直到所有元素都被插入到已排序序列中。
四希尔排序的步骤 1、简述希尔排序的基本思想。 答希尔排序也称为缩小增量排序即通过选取一定的增量来排序的本质还是插入排序通过增量将序列分为几个子序列然后对每个子序列进行直接插入排序。
四、交换排序
一冒泡排序的步骤 1、简述冒泡排序的步骤。 答通过两两比较相邻的元素若发生逆序则进行交换直到整个序列有序为止即若某一趟冒泡排序中没有发生元素交换说明此时序列已整体有序。
二冒泡排序的趟数和比较次数 1、设有n 个元素采用冒泡排序法进行排序通常需要进行多少趟排序?对于第i 次冒泡通常需要进行多少次关键字比较? 答n个元素采用冒泡排序进行排序最多需要进行n-1趟排序即最坏情况下排好的序列刚好与初始序列相反呈逆序排列而最少是初始序列正序只需一趟即可完成排序。 2、设有n 个元素采用冒泡排序法进行排序第i 次冒泡通常需要进行多少次关键字比较? 答最好情况下比较次数为n-1最坏情况下由于需要进行n-1趟排序第i趟排序中要进行n-i次比较。
三快速排序的步骤 1、简述快速排序的步骤。 答快速排序又称为分区交换排序通过多次划分操作来实现排序思想其步骤如下 ①每一趟排序中选取一个关键字作为枢轴 ②枢轴将待排序的序列分为两个部分比枢轴小的元素移到其前比枢轴大的元素移到其后这是一趟快速排序 ③然后递归地对两个部分按照枢轴划分规则继续进行快速排序直至每个区域只有一个元素为止或序列为空最后达到整个序列有序。
四快速排序的稳定性 1、试举例说明快速排序的稳定性。 答快速排序是不稳定的。当快速排序在处理包含有相等的元素的数组时相等元素的值没有改变但它们的相对顺序已经发生了变化从而导致排序结果不稳定。
五、堆排序
一堆排序的步骤 1、简述堆排序的基本思想。 答堆排序的基本思想是利用大根堆小根堆进行排序的方法步骤如下 ①将待排序的序列构造成一个大根堆小根堆此时整个序列的最大值最小值即为堆的根结点。 ②将当前根结点移走即与堆数组的末尾元素交换此时末尾元素就是最大值最小值然后将剩余的n-1个序列重新构造成一个堆依次得到n个元素中的次大值次小值 ③重复以上步骤从而得到一个有序序列。
二堆排序的稳定性 1、堆排序是不是稳定排序 答堆排序不是因为在进行筛选时可能会将后面相同关键字的元素调整到前面所有不是稳定的排序算法。
三堆排序的时间复杂度 1、设结点个数为 n采用堆排序法进行排序其时间复杂性是多少? 答堆排序的时间复杂性取决于堆的构造和调整过程将结点个数为n的初始序列构造成一个大根堆或小根堆建堆过程中元素比较次数最多为4n由于需要遍历整个序列所以这个构造过程的时间复杂度为O(n)。然后从剩余n-1个元素中选出一个最大或最小的元素与末尾元素交换这样的步骤最多需要n-1次所以复杂度是n(n-1)/2次对数级别的比较但是需要减去n/2的建堆时间即排序过程的时间复杂度为O(nlog2n)所以总的堆排序的时间复杂度为O(n)O(nlog2n)O(nlog2n)。
六、归并排序
一k路归并排序的步骤 1、什么是归并排序 答将已有序的子序列合并得到完全有序的序列其中先使每个子序列有序再使子序列间有序即为归并排序。
二k路归并排序的稳定性 1、归并排序是不是稳定的 答归并排序是稳定的排序算法满足稳定算法的定义即假设在数列中存在a[i]a[j]若在排序之前a[i]在a[j]前面且排序之后a[i]仍然在a[j]前面。
三二路归并排序的步骤 1、简述二路归并排序的算法思想。 答二路归并排序的步骤如下 ①将含n个元素的序列分为由n个长度为1的有序子表 ②相邻的两个有序子表归并为一个有序子表两两相邻归并 ③重复以上步骤最终归并成一个长度为n的有序表。
七、排序算法的综合运用 1、现有一文件F含有 1000 个记录其中只有少量记录次序不对且它们距离正确位置不远如果以比较和移动次数作为度量那么将其排序最好采用什么方法?为什么? 答由于文件中基本都是有序的只有少量记录次序不正确所以可以通过直接插入排序它在初始序列已基本有序的情况下表现较好即在每一步中只需要移动很少的记录而不像其他排序算法可能需要交换多个记录。因为只需要比较和交换记录的位置所以比较次数较少且由于距离正确位置不远从而使通过直接插入排序的移动次数也较少所以选择直接插入排序。 2、全国有 10000 人参加物理竞赛只录取成绩优异的前 10 名将他们从高分到低分输出。而对落选的其他考生不需排出名次问此种情况下用何种排序方法速度最快?为什么? 答堆排序。一般在n个元素中选出kknk2个最大或最小元素时均采用堆排序且堆排序建堆时的最多比较次数为4n而其他排序算法的时间复杂度较高。
