c語言折半插入排序
⑴ c語言折半插入排序 要求是要用指針
#include<stdio.h>#defineMax7
voidB_sort(inta[],intn)
{
intlow,high,i,j,t;
intm;
for(i=2;i<=n;++i)
{
t=a[i];//臨時存放
low=1;high=i-1;
while(low<=high)
{
m=(low+high)/2;
if(t<a[m])
high=m-1;
else
low=m+1;
}
for(j=i-1;j>=high+1;--j)
{
a[j+1]=a[j];
}
a[high+1]=t;
}}
main()
{inta[Max],i;
intlength=Max-1;
printf("這是一個折半排序 ");
printf("請輸入%d個待排序的記錄序列: ",length-1);
for(i=1;i<length;i++)
scanf("%d",&a[i]);
B_sort(a,length);
printf("折半排序後的序列:");
for(i=2;i<=length;i++)
printf("%d",a[i]);
printf(" ");
}
⑵ 用c語言，折半插入排序10個隨機數，主體插入排序，查找位置採用折半查找的方法。
教材上有寫：折半插入排序基本思想和直接插入排序一樣，區別在於尋找插入位置的方法不同，折半插入排序採用折半查找法來尋找插入位置。折半查找法只能對有序的序列使用。基本思想就是查找插入位置的時候，把序列分成兩半（選擇一個中間數mid），如果帶插入數據大於mid則到右半部分序列去在進行折半查找；反之，則到左半部分序列去折半查找。
折半插入排序在記錄移動次數上和直接插入排序是一樣，所以演算法時間復雜度也是一樣，只是在尋找插入位置的時候可能會節約相當多的時間。
⑶ C語言折半插入排序
修改好了。
你的主要錯誤是一個j--寫成了j++. 此外，我給你加了一點檢查的代碼。
此外，count的值是0，你沒有統計它，你自己再修改一下。
#include <stdio.h>
main()
{
int a[101],b[101],con,count = 0,i,j,t,n,m=0; /*count用來記錄計算次數，a數組是輸入數組，b數組時排序以後數組，con用來標記看a數組中的數字是否找到相應的位置，m用來表示b數組長度*/
scanf ("%d",&n);
for ( i = 0;i < n; i++) /*輸入數據*/
scanf ("%d",&a[i]);
b[0] = a[0];
m = 1;
for (i = 1;i < n;i++)
{
j = m / 2;
con = 1;
t = compare ( a[i],&b[j],&count,&con,&m,&j); /*conpare函數用來尋找a中數字插入的位置*/
if (t == 200) { /* check abnormal return */
printf("unexpected error\n");
exit(1);
}
printf("m = %d, t = %d\n", m, t);
for (j = m;j > t;j--) /*找到位置以後重新排序*/ // j--, not j++
b[j] = b[j-1];
b[t] = a[i];
if ( t != 200)
m = m+1;
}
printf("The sorted array:\n");
for (i = 0;i < m;i++)
printf ("%d ",b[i]);
printf ("\b\ncount: %d\n",count);
printf("press any key to exit\n");
getch();
}
int
compare (a,b,count,con,m,j) /*j表示所插入的位置*/
int a,*b,*count,*con,*m,*j;
{
int i,k = 0;
if (a > *b)
{
*con = 2 * (*con); /*用整除的方式表示，能被2整除，說明有過比a小的數字，能被3整除說明比較過比a大的數字，而當a在比它比它小的數之間時，被六整除，可以得到所求的位置*/
i = 1;
*j = *j + 1;
}
if (a < *b)
{
*con = 3 * (*con);
i = -1;
*j = *j -1;
k = 1;
}
if (a == *b)
return 200; /*返回值為200說明有數字相同，重新排序操作*/
if (*con % 6 == 0 || *j == -1 || *j == *m) /*當j過大或者過小的時候把數字排列在最左邊或者最右邊，返回主函數*/
return (*j + k);
else return compare (a,b+i,count,con,m,j); /*當還沒找到所需要位置的時候，再次使用該函數找到位置*/
}
⑷ 用折半插入排序方法寫出程序，完成數字12在數列（1，6，9，13，20，29）的排序工作（C語言）
解：用有序列插入法排序，過程如下：
第一步：7 1 （前兩個數7，1排成有序列）
第二步：7 3 1 （第3個數3按要求插入到已排好的有序列中）
第三步：12 7 3 1 （第4個數12按要求插入到已排好的有序列中）
第四步：12 8 7 3 1 （第5個數8按要求插入到已排好的有序列中）
第五步：12 8 7 4 3 1 （第6個數4按要求插入到已排好的有序列中）
第六步：12 9 8 7 4 3 1 （第7個數9按要求插入到已排好的有序列中）
第八步：12 10 9 8 7 4 3 1 （第8個數10按要求插入到已排好的有序列中）
這時各數的順序就是符合要求的最終順序.
用折半插入排序法，將新數據6插入到上面的有序列中，演算法步驟設計如下：
第一步：把新數據6與「中間位置」的數據8比較，由於6＜8，所以應將6放到8的右邊的一半有序列中，即應放到有序列7，4，3，1中.
第二步：把6與有序列7，4，3，1「中間位置」的數據4比較，由於4＜6，所以應將6放到4的左邊的一半有序列中，即應放到有序列7，4中.
第三步：把6與有序列7，4「中間位置」的數據7比較，由於7＞6，所以應將6放到7的右邊的一半有序列中，至此排序完成，得到一新的有序列
12，10，9，8，7，6，4，3，1
⑸ 數據結構實現折半插入排序(c語言版)
# include <stdio.h>#define Max 7
void B_sort(int a[], int n)
{
int low,high, i,j, t;
int m;
for(i=2;i<=n;++i)
{
t = a[i];//臨時存放
low =1;high =i-1;
while(low<=high)
{
m=(low+high)/2;
if(t<a[m])
high =m-1;
else
low =m+1;
}
for(j=i-1;j>=high+1;--j)
{
a[j+1] = a[j];
}
a[high+1] = t;
}}
main()
{int a[Max],i;
int length = Max-1;
printf(" 這是一個折半排序 \n");
printf("請輸入%d個待排序的記錄序列:\n",length-1);
for(i=1;i<length;i++)
scanf("%d",&a[i]);
B_sort(a,length);
printf("折半排序後的序列:");
for(i=2;i<=length;i++)
printf(" %d",a[i]);
printf("\n");
}
vc下面編譯通過的，折半插入排序，希望採納
⑹ c語言中的折半排序法是怎樣的，基本程序是怎樣的
折半法
應該叫做2分法。
用2分法查找數
需要先對數組進行排序（升序或降序）
假如你所要查找的數是20
數組是 1 4 7 8 20 30 34
每次都拿中間的數跟你要比的數比
也就是 8和20比
發現20比8大
所以左面的數都不要了
剩下的是 20 30 34
再拿20跟30比
發現20比30小
右面的數都不要了
再拿20跟20比
相等，則找到了。
如果找不到返回-1
下面是程序。
#include <iostream>
using namespace std;
int binarySearch(int* data,int low,int high,int value)
{
int k=(low+high)/2;
if(value<*(data+low)||value>*(data+high))
{
return -1;
}
if(value<*(data+k))
{
return binarySearch(data,low,k-1,value);
}
else if(value>*(data+k))
{
return binarySearch(data,k+1,high,value);
}
else
return k;
}
void main()
{
int pos;
int arr1[9]={1,2,3,4,5,6,7,8,9};
int i=9;
while(i)
{
pos=binarySearch(arr1,0,8,i);
cout<<"數字"<<i<<"的下標是:"<<pos<<endl;
i--;
}
pos=binarySearch(arr1,0,8,20);
cout<<"數字20的下標是:"<<pos<<endl;
}
⑺ C語言幫我解釋下折半插入排序代碼
你把題目給我一下！其實你要學排序最好就學
1.冒泡排序（最簡單，最慢）
2。取中快排（最快，但不穩定，不過不影響大局，最好背這個）
3.桶排序（比較快，其實也還沒有2的一半，就是結構穩定）
⑻ 請寫一個折半插入排序演算法（最好用C語言寫出來，只要求寫一個函數）。
折半插入排序演算法：
//創建鏈表
StatusEnSqList(SqList*L,ElemTypee,intn)
{
if(L->length>=n)
returnERROR;
L->data[L->length+1]=e;
L->length++;
returnOK;
}
//折半插入排序演算法
voidBInsertSort(SqList*L)
{
inti,j,mid,high,low;
for(i=2;i<=L->length;i++)
{
low=1;
high=i-1;
L->data[0]=L->data[i];
while(low<=high)
{
mid=(low+high)/2;
if(L->data[0]<L->data[mid])
high=mid-1;
else
low=mid+1;
}
for(j=i-1;j>=high+1;j--)
L->data[j+1]=L->data[j];
L->data[high+1]=L->data[0];
}
}
intmain(void)
{
SqListL;
intn,i;
ElemTypee;
L.length=0;
printf("輸入元素個數：");
scanf("%d",&n);
L.data=(int*)malloc(sizeof(int)*n);
printf("輸入各個元素的值：");
for(i=0;i<n;i++)
{
scanf("%d",&e);
EnSqList(&L,e,n);
}
BInsertSort(&L);
for(i=1;i<=n;i++)
printf("%d",L.data[i]);
printf(" ");
return0;
}
⑼ c語言折半插入排序要求是用指針
可以減少比較的次數，折半插入要比直接插入排序要快一點，因為它改善了，演算法中比較的次數，它的時間復雜度是:n*(log2(n));
這個演算法要比直接插入排序要求，但是時間復雜度的籠統的演算法是和直接一樣的O(n*n);
⑽ 請寫一個折半插入排序演算法（最好用C語言寫出來，只要求寫一個函數）
/***折半插入排序***/
/*演算法原理：從第二個數開始逐個置入監視哨，使用low，high標簽在L[0..i-1]有序區內進行折半查找
來確認待排序數的插入位置，然後將該位置到最後一個數全部後移一位，最後騰出該位置，
把監視哨裡面的數置入該位置。後面的數以此類推進行排序，直到最後一個數比較完畢。
*/
#include<stdio.h>
voidbinaryInsertSort(intL[],intn)
{
inti,j;
intlow,high,mid;
//用L[0]作為監視哨，L[1..i-1]為有序區，
for(i=2;i<=n;i++)
{
L[0]=L[i]; //待排序的數進監視哨
low=1;
high=i-1; //初始化low，high
while(low<=high)//循環語句確定插入位置，必須保證low<=high
{
mid=(low+high)/2;
if(L[0]<L[mid])//根據L[0]的值的大小,確定屬於低半區還是高半區
high=mid-1;//插入低半區//插入低半區
else
low=mid+1;//插入高半區
}
for(j=i-1;j>=high+1;j--)//待插入位置後面L[hign+1..i-1]全部數後移一位
L[j+1]=L[j];
L[high+1]=L[0]; //或者換成L[j+1]=L[0];監視哨裡面的數插入數組
}
}
voidbinaryInsertSort1(intL[],intn)
{
inti,j;
intlow,high,mid,tmp;
//用臨時變數tmp作為監視哨，L[0..i-1]為有序區
for(i=1;i<n;i++)
{
tmp=L[i];
low=0;
high=i-1;
while(low<=high)
{
mid=(low+high)/2;
if(tmp<L[mid])
high=mid-1;
else
low=mid+1;
}
for(j=i-1;j>=high+1;j--)
L[j+1]=L[j];
L[high+1]=tmp;
}
}
intmain()
{
inti,n;
inta[50];
printf("輸入n=");
scanf("%d",&n);
printf("輸入數組元素： ");
// for(i=1;i<=n;i++)
for(i=0;i<n;i++)
scanf("%d",&a[i]);
// binaryInsertSort(a,n);
binaryInsertSort1(a,n-1);
printf("排序後; ");
// for(i=1;i<=n;i++)
for(i=0;i<n;i++)
printf("%-4d",a[i]);
putchar(10);
return0;
}