文档章节

二分法查找和排序c语言示例

y
 yky20190625
发布于 06/26 16:06
字数 712
阅读 5
收藏 0

二分法查找和排序  示例:

#include <stdio.h>
/*
        二分法查找和排序示例
        20190626   
*/ 
int main()
{
   int data[10] = {7,1,11,67,5,3,89,4,5,33};
    for(int i=1;i<10;i++)  //大循环 从数组第2个元素开始,前面的第一个元素构成一个有序数组(此时数组里只有一个元素,当然是"有序"的了) , 在大循环的第一次循环中,把第2个元素通过二分查找方法,插入前面的有序数组(只有一个元素)中, 这样头两个元素就构成一个新的有序数组. 依次类推, 下次循环把第三个元素插入前面的有序数组中... 不断循环下去, 整个数组就排序了.
    {
    
         int mid=0;   //二分位置 
         int left=0;  //左边界位置 
         int right=i-1;  // 右边界位置 
         int tmp=data[i];  
         while(left<=right)   //如果左右边界重合了, 即left==right了, 但此时插入元素可能比重合处的元素小,也可能比重合处的元素大,因此,还要循环一次,进一步与重合处位置处的元素比较 ,所以这里的循环条件必须是 (left<=right)
         {
             mid=(left+right)/2;  //求中间元素数组坐标    (~~当左右边界重合时, 中间元素就是自身) 
             if(tmp<data[mid]){   //把待插入数与二分位置处元素比较, 如果比二分元素小,则右边界right移到二分元素之前的位置 
                 right=mid-1;
             }else{              //如果大于等于二分元素,则左边界left移动到二分元素之后的位置 
                 left=mid+1;
             } 
             printf("mid=%d,left=%d,right=%d\n",mid,left,right);           
         }
         //循环结束时, 插入位置就是left所指向的位置. 
        for(int j=i-1;j>=left;j--)  //循环的作用是把有序数组中元素从left位置向后平移一次,把left位置腾出来
        {
            data[j+1]=data[j];
         }
        data[left]=tmp;   //腾出的left位置放入要插入元素 
    } 
    for (int i = 0; i <10 ; i++)
    {
            printf("%d ",data[i]);
    }
return 0;
}

输出结果: mid=0,left=0,right=-1
mid=0,left=1,right=1
mid=1,left=2,right=1
mid=1,left=2,right=2
mid=2,left=3,right=2
mid=1,left=0,right=0
mid=0,left=1,right=0
mid=2,left=0,right=1
mid=0,left=1,right=1
mid=1,left=1,right=0
mid=2,left=3,right=5
mid=4,left=5,right=5
mid=5,left=6,right=5
mid=3,left=0,right=2
mid=1,left=2,right=2
mid=2,left=2,right=1
mid=3,left=4,right=7
mid=5,left=4,right=4
mid=4,left=4,right=3
mid=4,left=5,right=8
mid=6,left=7,right=8
mid=7,left=7,right=6
1 3 4 5 5 7 11 33 67 89 

© 著作权归作者所有

y
粉丝 0
博文 10
码字总数 13594
作品 0
荆州
私信 提问
【数据结构与算法JavaScript实现与应用】查找算法 —— 顺序查找 PK 二分法+排序

前言 在列表中查找数据有两种方式:顺序查找和二分查找。对于一个已排序的列表,二分法无疑效率更高,因为每次可排除一半的元素,但若是对于一个无序的列表,如果先对其排序,再用二分法查找...

haoshuai1950
07/20
0
0
递归 —— 二分查找法 —— 归并排序

PS:什么是递归、二分查找、归并排序。 递归排序大家都不陌生,递归简单的说就是自己在没有达到目的的同时在此调用本身,把一个大问题层层转化为和原问题相似的小问题解决,递归需要有边界条...

CMusketeer
2018/07/29
0
0
算法-数据结构

时间复杂度 O(log n) 意味着什么? 写给小白的时间复杂度指南 查找算法的 Java 实现 查找算法的 Java 实现 两个有序数组合并成一个有序数组 用拉链法和线性探测法解决哈希冲突 用拉链法和线性...

掘金官方
2017/12/14
0
0
算法与数据结构(五)二叉搜索树

二叉搜索树 (Binary Search Tree) 核心是解决问题。高效解决问题。 查找问题 Searching Problem: 查找问题是计算机中非常重要的基础问题 查找问题的基础:二分查找法 Binary Search 对于有序...

天涯明月笙
2017/09/16
0
0
【python】手把手带你掌握算法基础01_二分法和选择排序法的实现

一、大O表示法 学算法就绕不开大O表示法,大O法可以告诉我们算法的时间和空间复杂度。 我们先聊点简单的,请你从1数到10,这里的复杂度是多少呢?O(10)。那么从1数到n,归纳法告诉我们,复...

徐胥
05/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

从零基础到拿到网易Java实习offer,我做对了哪些事

作为一个非科班小白,我在读研期间基本是自学Java,从一开始几乎零基础,只有一点点数据结构和Java方面的基础,到最终获得网易游戏的Java实习offer,我大概用了半年左右的时间。本文将会讲到...

Java技术江湖
昨天
5
0
程序性能checklist

程序性能checklist

Moks角木
昨天
7
0
VUE 计算属性

本文转载于:专业的前端网站▶VUE 计算属性 1、示例代码 <!DOCTYPE html><html lang="zh"> <head> <meta charset="UTF-8" /> <title>vue示例</title> </hea......

前端老手
昨天
6
0
快速搭建LNMT平台和环境部署 Tomcat详解

Tomcat部署的基本概念 1. CATALINA_HOME与CATALINA_BASE分别指什么?     CATALINA_HOME指的是Tomcat的安装目录     bin:\\Tomcat一些脚本存放目录,比如启动脚本startup.bat/start...

网络小虾米
昨天
7
0
float浮动

float浮动 float浮动概念及原理: 文档流:文档流是文档中可显示对象在排列时所占用的位置。 加浮动的元素,会脱离文档流,会沿父容器靠左或靠右排列,如果之前已经有浮动的元素,会挨着浮动...

studywin
昨天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部