网站地址英文,东莞seo推广机构帖子,企业网站实名认证怎么做,上海建设网站的公司思考#xff1a;在把待排序的元素插入已经有序的子序列中时#xff0c;是不是一定要逐一比较#xff1f;有没有改进方法#xff1f;
在查找插入位置的时候可以采用折半#xff08;二分#xff09;搜索的办法。
一、折半插入排序
1.折半插入排序算法的基本思想
假设待…思考在把待排序的元素插入已经有序的子序列中时是不是一定要逐一比较有没有改进方法
在查找插入位置的时候可以采用折半二分搜索的办法。
一、折半插入排序
1.折半插入排序算法的基本思想
假设待排序的n个数据元素存放在数组a中那么折半插入排序可做如下描述
1初始条件有序子序列中只有一个元素a[0]
2从a[1]开始对于每次要插入的数据元素a[i]使用折半查找法查找a[i] 在已经有序的序列中的插入位置然后进行插入。
3循环n-1次直到所有元素都插入到有序序列中算法结束。
2.折半插入排序代码
def bin_insertion_sort(self):data_len len(self.data)for i in range(1, data_len):if self.data[i] self.data[i - 1]:low 0high i - 1temp self.data[i]while low high:mid (low high) // 2if temp self.data[mid]:high mid - 1else:low mid 1j i - 1while j low:self.data[j 1] self.data[j]j j - 1self.data[low] temp3.折半插入排序举例
例设待排元素序列为{1615191618192014}请给出折半插入排序算法按关键字递增排列。 4.折半插入排序算法分析
1空间复杂度折半插入排序与直接插入排序一样空间上只需要一个记录大小的辅助空间来临时存放待插入记录空间复杂度为O(1)。
2时间复杂度折半插入排序这种改进考虑了数据元素的比较次数。要插入a[i]时要在长度为i的有序序列中查找位置因此综合起来总的比较次数nlog2n。但是折半插入排序并没有减少数据元素移动的次数因此其时间复杂度仍然是O(n2)。
3其他方面折半查找只能用于顺序结构存储的序列当初始记录无序性强数据元素个数较多时效率较高是一种稳定的排序方法。
二、希尔排序
1.希尔算法的基本思想
1把数据元素按照增量分为若干个小组对每个小组内元素利用直接插入排序进行排序。 2通过分组使得每次利用直接插入排序的元素个数降低
3通过每次组内排序使得整个序列趋向于有序。
4每趟排序过后再按照新的更小的增量进行上述过程直至增量为1所有数据元素都在一个小组内排序后算法结束。
2.希尔排序举例
例设待排元素序列为{56,25,70,99,82,10,15,56,42,18 }取增量序列为{531}请给出希尔排序法进行排序的过程。 3.希尔排序代码
def shell_sort(self):data_len len(self.data)gap data_lenwhile True:gap gap // 3 1 # 保证增量递减且最后为1for i in range(gap, data_len):temp Record(self.data[i].key, self.data[i].value)j i-gapwhile j 0 and temp.key self.data[j].key:self.data[jgap].key self.data[j].keyj j-gapself.data[j gap] tempif gap 1:break4.希尔排序算法分析
1空间复杂度也需要一个数据元素空间其空间复杂度为O(1)。
2时间复杂度希尔排序的时间复杂度分析是个非常复杂的问题因为其性能与所选增量序列有关介于O(n)和O(n2)之间。
3希尔排序算法是不稳定算法。
