黑马程序员技术交流社区

标题: （c语言）关于一个随机数组用二分法从大到小排序。 [打印本页]

作者: youngrivers 时间: 2016-1-16 19:00
标题: （c语言）关于一个随机数组用二分法从大到小排序。
怎么弄的？原理告诉我也可以

作者: wuxueshuan 时间: 2016-1-16 19:00

youngrivers 发表于 2016-1-18 14:49
说的有点明白了，你把你的代码发到这里来看一看啊

int [] arr = {12,32,455,112,36,23,67,7,27};
Arrays.sort(arr); //二分算法需要数组是有序的所以先排序
/*
   * 先定义最大索引,最小索引,和中间值索引
   *
   * */
int min = 0; //最小索引
int max = arr.length -1;//最大索引
int mid = (min + max) / 2; //中间值
//需要循环来判断,因为不知道具体次数所以用while来做
while (arr[mid] != a) { //用中间索引的值来跟传入的a值进行比较
if (arr[mid] > a) { //如果中间索引的值大于a,那么下次寻找的范围就在0到中间索引减去1的位置
max = mid -1; //就是最大索引max = 中间索引mid-1
}else if (arr[mid] < a) {
min = mid +1;
}
mid = (min + max) / 2;  //每次判断完了以后mid需要重新计算

if (min > max) {
return -1; //如果最小索引大于最大索引证明传入的数不再数组中返回-1表示
}

}

return mid; //如果传入的数等于中间索引的元素值,直接返回mid,

就是这些了其实写起来还是不难,主要是思路

作者: hdhunter 时间: 2016-1-17 10:47
#include "stdio.h"

typedef struct
{
char *elem;
int length;
}sstable;

void create(char **t)
{
int i;
static char a[11];
*t=a;
for(i=1;i<=10;i++)
{
printf("A[%d] is:",i);
scanf("%c",&a[i]);
    if (a[i] != '\n') getchar();
}
}

int searth(char *t,char k)
{
int i;
for (i=10;i>=0 && t[i]!=k ;i--);
return i;
}

void output(char *t)
{
int i;
for (i=1;i<=10;i++)
printf("\n          A[%d] is %c",i,t[i]);
}

void px(char *t)
{
char s;
int i,j;
for (i=1;i<=10;i++)
    for (j=i+1;j<=10;j++)
    {
    if (t[i]>t[j])  {s=t[i];t[i]=t[j];t[j]=s;}
    }
}

int search_bin(char *t,char k)
{
int low=1,high=10,mid;
while (low<=high)
{
mid=(low+high)/2;
if (k==t[mid]) return mid;
else if (k<t[mid]) high=mid-1;
     else low=mid+1;
}
return 0;
}

main()
{
char *t,k;
int s;
create(&t);
output(t);

printf("\nplease input you search char:");
k=getchar();
s=searth(t,k);

if (s>=0) printf("1: use search find is A[%d]\n",s);
else printf("1:can not find it\n");

px(t);
output(t);

s=search_bin(t,k);
if(s==0) printf("\n1:can not find it \n");
else printf("\n2:use search_bin find is A[%d]\n",s);

getchar();
}

作者: youngrivers 时间: 2016-1-17 11:42

hdhunter 发表于 2016-1-17 10:47
#include "stdio.h"

typedef struct

来点注释啊，有点看不明白

作者: JC小子 时间: 2016-1-17 22:11
对于小白的我来说，楼上代码有够复杂的，没有完全理解到位

作者: wuxueshuan 时间: 2016-1-17 23:05
二分法,首先二分法是用来查找一个元素是不是在这个数组,返回的是数组索引,或者叫下标,二分法,就是计算的时候会将一个数组一分为二,设置一个中间值,这里我们定义三个变量,最大索引值max,最小索引值min,中间索引值mid,假设需要用二分法的数组名字叫arr,你传入的需要查找是不是在这个数组的元素假设为a,计算原理是:先用a与arr[mid]做比较,如果小于arr[mid],那么就可以缩小a查询范围是在arr[min]到ar[mid]之间的,这时候在进行查询的时候max就可以规定到mid-1的索引位置了,因为范围减小了,如果是大于,就是在mid+1到原先的max的范围,
然后在重新寻找mid中间值,就是这样循环下去,每次都跟mid做比较,当寻找到min的值大于max的时候就证明这个元素不再数组当中,就是这样,如果那里不明白,可以再问,加油哦!想要代码说一下,发给你.!!!

作者: 西葫芦虾仁 时间: 2016-1-17 23:10
二分法排序最重要的一个步骤就是查找要插入元素的位置，也就是要在哪一个位置上放我们要准备排序的这个元素。
当我们查找到位置以后就很好说了，和插入排序一样，将这个位置以后的所有元素都向后移动一位。这样就实现了二分法排序。
　　然后是怎么查找着一个位置呢，就是不断的比较已排序的序列中的中间元素和要排序元素，如果大于的话，说明这个要排
序的元素在已排序序列中点之前的序列。

public static void DichotomySort(int[] array)
      {
         for (int i = 0; i < array.Length; i++)
         {
            int start, end, mid;
            start = 0;
            end = i - 1;
            mid = 0;
            int temp = array[i];
            while (start <= end)
            {
                  mid = (start + end) / 2;
                  if (array[mid] > temp)//要排序元素在已经排过序的数组左边
                  {
                     end = mid - 1;
                  }
                  else
                  {
                     start = mid + 1;
                  }
            }
            for (int j = i - 1; j > end; j--)//找到了要插入的位置，然后将这个位置以后的所有元素向后移动

            {
                  array[j + 1] = array[j];
            }
            array[end + 1] = temp;

         }
      }

作者: youngrivers 时间: 2016-1-18 14:49

wuxueshuan 发表于 2016-1-17 23:05
二分法,首先二分法是用来查找一个元素是不是在这个数组,返回的是数组索引,或者叫下标,二分法,就是计算的时 ...

说的有点明白了，你把你的代码发到这里来看一看啊

作者: 彬小彬 时间: 2016-1-18 23:50
你不要闹,二分法是用类查找的,你是不是想知道二叉树排序,如果你是想知道二叉树排序的话,可以回复的时候说一下

查找.jpg (8.98 KB, 下载次数: 160)

查找

1fef1656ee3957e98d54300f.jpg (39.92 KB, 下载次数: 149)

排序

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2