广西建设领域证书查询官方网站,游戏微网站模板,菏泽网站网站建设,苏州建设交通学校网站首页目录 一、内排序和外排序二、排序算法的稳定性三、插入排序#xff08;一#xff09;直接插入排序的步骤#xff08;二#xff09;直接插入排序的稳定性#xff08;三#xff09;折半插入排序的步骤#xff08;四#xff09;希尔排序的步骤 四、交换排序#xff08;一… 目录 一、内排序和外排序二、排序算法的稳定性三、插入排序一直接插入排序的步骤二直接插入排序的稳定性三折半插入排序的步骤四希尔排序的步骤 四、交换排序一冒泡排序的步骤二快速排序的步骤三快速排序的稳定性 五、堆排序一堆排序的步骤二堆排序的稳定性 六、归并排序一k路归并排序的步骤二k路归并排序的稳定性三二路归并排序的步骤 一、内排序和外排序 1、内排序和外排序有什么区别内排序有哪些算法 答根据排序过程中数据元素是否完全在内存中进行可分为内排序和外排序。内排序有直接/折半插入排序、简单旋转排序、冒泡排序、希尔排序、快速排序和堆排序。
二、排序算法的稳定性 1、什么是稳定排序 答经过排序后能使关键字相同的元素保持原本顺序中的相对位置不变则称这个算法是稳定的反之则不稳定。
三、插入排序
一直接插入排序的步骤 1、简述直接插入排序算法的基本思想。 答直接插入排序是将要排序的序列按照关键字的大小插入至已排好序的子序列中一直进行直到整个序列有序。
二直接插入排序的稳定性 1、直接插入排序算法是不是稳定的排序方法 答由于每次插入元素时总是从后向前比较后再移动所以不会出现相同元素相对位置发生变化的情况即直接插入排序是稳定的。
三折半插入排序的步骤 1、简述折半插入排序算法的基本思想。 答折半插入排序的具体步骤如下 初始化一个已排序序列该序列只包含第一个元素从第二个元素开始通过折半查找确定每个待排序元素的插入位置根据已排序序列中元素的中点比较待排序元素与中点元素的大小若待排序元素大于中点元素则插入位置在中间位置的右侧否则插入位置在中间位置的左侧然后插入元素同时需要将插入位置及其之后的所有元素向后移动一位以为待排序元素腾出空间重复步骤直到所有元素都被插入到已排序序列中。
四希尔排序的步骤 1、简述希尔排序的基本思想。 答希尔排序也称为缩小增量排序即通过选取一定的增量来排序的本质还是插入排序通过增量将序列分为几个子序列然后对每个子序列进行直接插入排序。
四、交换排序
一冒泡排序的步骤 1、简述冒泡排序的步骤。 答通过两两比较相邻的元素若发生逆序则进行交换直到整个序列有序为止即若某一趟冒泡排序中没有发生元素交换说明此时序列已整体有序。
二快速排序的步骤 1、简述快速排序的步骤。 答快速排序又称为分区交换排序通过多次划分操作来实现排序思想其步骤如下 ①每一趟排序中选取一个关键字作为枢轴 ②枢轴将待排序的序列分为两个部分比枢轴小的元素移到其前比枢轴大的元素移到其后这是一趟快速排序 ③然后递归地对两个部分按照枢轴划分规则继续进行快速排序直至每个区域只有一个元素为止或序列为空最后达到整个序列有序。
三快速排序的稳定性 1、试举例说明快速排序的稳定性。 答快速排序是不稳定的。当快速排序在处理包含有相等的元素的数组时相等元素的值没有改变但它们的相对顺序已经发生了变化从而导致排序结果不稳定。
五、堆排序
一堆排序的步骤 1、简述堆排序的基本思想。 答堆排序的基本思想是利用大根堆小根堆进行排序的方法步骤如下 ①将待排序的序列构造成一个大根堆小根堆此时整个序列的最大值最小值即为堆的根结点。 ②将当前根结点移走即与堆数组的末尾元素交换此时末尾元素就是最大值最小值然后将剩余的n-1个序列重新构造成一个堆依次得到n个元素中的次大值次小值 ③重复以上步骤从而得到一个有序序列。
二堆排序的稳定性 1、堆排序是不是稳定排序 答堆排序不是因为在进行筛选时可能会将后面相同关键字的元素调整到前面所有不是稳定的排序算法。
六、归并排序
一k路归并排序的步骤 1、什么是归并排序 答将已有序的子序列合并得到完全有序的序列其中先使每个子序列有序再使子序列间有序即为归并排序。
二k路归并排序的稳定性 1、归并排序是不是稳定的 答归并排序是稳定的排序算法满足稳定算法的定义即假设在数列中存在a[i]a[j]若在排序之前a[i]在a[j]前面且排序之后a[i]仍然在a[j]前面。
三二路归并排序的步骤 1、简述二路归并排序的算法思想。 答二路归并排序的步骤如下 ①将含n个元素的序列分为由n个长度为1的有序子表 ②相邻的两个有序子表归并为一个有序子表两两相邻归并 ③重复以上步骤最终归并成一个长度为n的有序表。
