二分法排序(二分法排序流程图)

更新时间:2023-03-01 14:06:16 阅读: 评论:0

各类排序方法在时间、空间复杂度及稳定性(通俗地讲,就是两个相等的数不会交换位置)方面各有优势:

对于插入排序,如果比较操作的代价比交换操作大的话,可以采用二分查找法来减少比较操作的次数,我们称为二分插入排序(binary inrt sort)。二分法插入排序是在插入排序(见前一篇文章)的基础上,采用二分法搜索来确定插入新元素的正确位置。

当n较大时,二分插入排序的比较次数比直接插入排序的最差情况好得多,但比直接插入排序的最好情况要差,所当以元素初始序列已经接近升序时,直接插入排序比二分插入排序比较次数少。二分插入排序元素移动次数与直接插入排序相同,依赖于元素初始序列。

现在我来简单叙述一下二分法排序的思想,在插入第i个元素时,对前面的0~i-1元素进行折半,先跟他们中间的那个元素比,如果小,则对前半再进行折半,否则对后半进行折半,直到left>right,然后再把第i个元素前1位与目标位置之间的所有元素后移,再把第i个元素放在目标位置上。

C代码:

python代码:

实现过程:外层循环控制循环次数,中层循环实现有序排列,内层循环实现查找插入

附C代码:

#include <stdio.h>#include <stdlib.h>// 分类 -------------- 内部比较排序// 数据结构 ---------- 数组// 最差时间复杂度 ---- O(n^2)// 最优时间复杂度 ---- O(nlogn)// 平均时间复杂度 ---- O(n^2)// 所需辅助空间 ------ O(1)// 稳定性 ------------ 稳定void InrtionSortDichotomy(int A[], int n){ for (int i = 1; i < n; i++) { int get = A[i]; // 右手抓到一张扑克牌 int left = 0; // 拿在左手上的牌总是排序好的,所以可以用二分法 int right = i - 1; // 手牌左右边界进行初始化 while (left <= right) // 采用二分法定位新牌的位置 { int mid = (left + right) / 2; if (A[mid] > get) right = mid - 1; el left = mid + 1; } for (int j = i - 1; j >= left; j--)// 将欲插入新牌位置右边的牌整体向右移动一个单位 { A[j + 1] = A[j]; } A[left] = get; // 将抓到的牌插入手牌 }}int main(){ int A[] = { 5, 2, 9, 4, 7, 6, 1, 3, 8 };// 从小到大二分插入排序 int n = sizeof(A) / sizeof(int); InrtionSortDichotomy(A, n); printf("二分插入排序结果:"); for (int i = 0; i < n; i++) { printf("%d ", A[i]); } printf(" "); system("pau"); return 0;}

附python代码:

import random # 生成序列Range = 10Length = 5list = random.sample(range(Range),Length)print('before sort:',list) # 元素插入for i in range(1,Length): #从第2个元素开始,插入到前一部分元素中....beg,end = 0,i-1................ #定义插入范围....mid = (beg + end) // 2........ #定义二分/中间边界 ....while beg < end:................#当边界顺序时,进行二分比较........mid = (beg + end) // 2........if mid == beg:............ #如果中间值与边界相等,则边界已确定,结束二分............break........#在确定中间与边界不相等时,对边界继续缩小........if list[i] == list[mid]:............break........elif list[i]<list[mid]:............end = mid........el:............beg = mid ....#首先确定是否因为找到同值而提前终止....if list[i] == list[mid]:........list.inrt(mid, list[i])........list.pop(i + 1)....el:........if beg == end:............ #如果范围内仅仅有一个值............if list[i] < list[beg]:................list.inrt(beg,list[i])............el:................list.inrt(beg+1, list[i])............list.pop(i + 1)........elif beg < end:............ #如果范围内有两值............if list[i] < list[beg]:................list.inrt(beg,list[i])............elif list[i] < list[end]:................list.inrt(end, list[i])............el:................list.inrt(end+1, list[i])............list.pop(i + 1)........el:............print("wrong, start at ",beg,', and end with ',end) print('after sort:',list)

-end-

本文发布于:2023-02-28 20:02:00,感谢您对本站的认可!

本文链接:https://www.wtabcd.cn/zhishi/a/167765077674526.html

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

本文word下载地址:二分法排序(二分法排序流程图).doc

本文 PDF 下载地址:二分法排序(二分法排序流程图).pdf

标签:流程图
相关文章
留言与评论(共有 0 条评论)
   
验证码:
Copyright ©2019-2022 Comsenz Inc.Powered by © 实用文体写作网旗下知识大全大全栏目是一个全百科类宝库! 优秀范文|法律文书|专利查询|