二分法查找，排序
首先申明，二分法查找只适用与已排序的数列，如果是混乱数列。。我也无能为力~有一个数组 v 已经按升序排列了，数组 v 有 n=20 个元素。数组中有个元素 x，如何知道 x 位于该数组的第几位呢？
解决这个问题的一个普遍方法是二分法查找。下面是程序：
#include <stdio.h>int binsearch(int x, int v[], int n);main(){ int i, result, n;int wait; int x = 17;// 需要查找的数值int v[19]; // 定义一个数组// 给数组赋值for(i = 0; i < 20; ++i) v[i] = i;/**for(i = 0; i < 20; ++i)printf("%d \n", v);*/n = 20;result = binsearch(x, v, n);printf("%d", result);scanf("%d", &wait);}int binsearch(int x, int v[], int n){int low, high, mid;low = 0;high = n - 1;while (low <= high){mid = (low + high) / 2;if(x < v[mid])high = mid - 1;else if (x > v[mid])low = mid + 1;elsereturn mid;// 看看循环执行了多少次printf("mid = %d, low = %d, high = %d \n", mid, low, high);}return -1;}思路很简单：首先将输入值 x 与数组 v 的中间元素比较，如果 x 小于中间的元素，则将 high 值设为 中间元素-1，同理，若 x 大于中间元素，则将中间元素 + 1作为 low，再在low 与 high之间进行查找
<span style="color: #333333; font-family: Arial, Console, Verdana, 'Courier New';"><div class="article_content" style="">二分法插入排序
算法思想简单描述：
在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们
中间的那个元素比，如果小，则对前半再进行折半，否则对后半
进行折半，直到left>right，然后再把第i个元素前1位与目标位置之间
的所有元素后移，再把第i个元素放在目标位置上。
二分法没有排序，只有查找。所以当找到要插入的位置时。移动必须从最后一个记录开始，向后移动一位，再移动倒数第2位，直到要插入的位置的记录移后一位。
二分插入排序是稳定的，平均时间O(n2)
void binsort(ref int[] data1)
1、二分法查找插入位置
如果R<R成立，那右指针就要向左移动中间指针一位，否则，左指针要向左移动中间指针一位。反复查找，直到左指针大于右指针时停止。
2、后移，有点迷惑，什么时候需要后移呢？有哪些记录需要移动呢？
虽然我们很清楚的知道，我们需要后移那些排序码大于R的记录，但难免会问自己这样几个问题。其实它相当于需要移动从i-1到左指针的记录。
3、插入
由1中得到的左指针其实就是元素要插入的位置。
4、算法
{
int left,right,num;
int middle,j;
for( int i = 1;i < data1.Length;i++)
{
// 准备
left = 0;
right = i-1;
num = data1;
// 二分法查找插入位置
while( right >= left)
{
// 指向已排序好的中间位置
middle = ( left + right ) / 2;
if( num < data1 )
// 插入的元素在右区间
right = middle-1;
else
// 插入的元素在左区间
left = middle+1;
}
// 后移排序码大于R的记录
for( j = i-1;j >= left;j-- )
{
data1 = data1;
}
// 插入
data1 = num;
}
// 插入的元素在左区间
left = middle+1;
}
// 后移排序码大于R的记录
for( j = i-1;j >= left;j-- )
{
data1 = data1;
}
// 插入
data1 = num;
}
/* 二分法插入排序的算法源程序*/#include<stdio.h>#define MAXNUM 100typedef int KeyType;typedef int DataType;typedef struct { KeyType key; /* 排序码字段 */ /*DataType info; 记录的其它字段 */} RecordNode;typedef struct { int n; /* n为文件中的记录个数，n<MAXNUM */ RecordNode record;} SortObject;void binSort(SortObject * pvector) { /* 按递增序进行二分法插入排序 */ int i, j, left, mid, right; RecordNode temp; RecordNode *data = pvector->record; for( i = 1; i < pvector->n; i++ ) { temp = data; left = 0; right = i-1; /* 置已排序区间的下、上界初值 */ while (left <= right) { mid = (left + right)/2; /* mid指向已排序区间的中间位置 */ if (temp.key < data.key) right = mid-1; /* 插入元素应在左子区间 */ else left = mid+1; /* 插入元素应在右子区间 */ } for (j = i-1; j >= left; j--) data = data; /* 将排序码大于ki的记录后移 */ if (left != i) data = temp; }}SortObject vector={10, 49,38,65,97,76,13,27,49,50,101};int main(){ int i; binSort(&vector); for(i = 0; i < vector.n; i++) printf("%d ", vector.record); getchar(); return 0;}
页:
[1]