用JAVA实现折半插入排序的题目

别忘记给分哦

package comadtechinterftest;

public class Test{

public Test(Record a[]) {

int i, j, m, low, high;

Record temp;

for (i = 0; i < alength; i++) {

temp = a[i];

low = 0;

high = i;

while (low <= high) {

m = (low + high) / 2;

if (tempgetStudentID() < a[m]getStudentID()) {

high = m - 1;

} else {

low = m + 1;

}

}

for (j = i; j > high + 1 && j > 0; j--) { // 如果j>high 就会少遍历一个元素 || j>low

a[j] = a[j - 1];

}

a[j] = temp;

}

for (int t = 0; t < alength; t++) {

Systemoutprintln(a[t]getStudentID());

}

}

public static void main(String args[]) {

Record record1 = new Record(2,"张三1",810,18);

Record record2 = new Record(4,"张三2",820,11);

Record record3 = new Record(5,"张三3",830,12);

Record record4 = new Record(43,"张三4",840,13);

Record record5 = new Record(21,"张三5",850,14);

Record record6 = new Record(54,"张三6",860,15);

Record record7 = new Record(22,"张三7",870,16);

Record record8 = new Record(6,"张三4",880,17);

Record record9 = new Record(223,"张三9",890,18);

Record record10 = new Record(545,"张三10",800,19);

Record [] record = new Record[]{record1,record2,record3,record4,

record5,record6,record7,record8,record9,record10};

new Test(record);

}

}

//参考代码如下：

#include <stdioh>

int main()

{

int i, j, n, k=0, isFound=0;

int num[15] = {88,86,75,74,61,56,52,43,39,34,31,22,18,16,8}; //测试数组

printf("请输出一个整数：\n");

scanf("%d", &n);

i = (int)15/2; //对折位移量

j = (int)15/2; //取数“指针”

while(k<2)

{

i = (int)i/2;

if(i == 0) k++; //i==0 即折半到无可再折时，仍有最后一次比较，故以k做计数

//若未相等，计算下一循环指针的位置

if(n<num[j])

j = j + (i + 1);

else if(n>num[j])

j = j - (i + 1);

else

{

isFound = 1;

break; //若找到相等数，标记已找到并退出循环

}

}

//输出结果

if(isFound)

printf("该数是数组中第%d个元素的值\n", j);

else

printf("查无此数！\n");

return 0;

}

折半插入排序是对直接插入排序的一种改良方式，在直接插入排序中，每次向已排序序列中插入元素时，都要去寻找插入元素的合适位置，但是这个过程是从已排序序列的最后开始逐一去比较大小的，这其实很是浪费，因为每比较一次紧接着就是元素的移动。

折半排序就是通过折半的方式去找到合适的位置，然后一次性进行移动，为插入的元素腾出位置。

折半查找，因为再已排序的序列中，序列元素都是按照顺序排列的，既然这样，完全不需要逐一去比较大小，而是去比较已排序序列的中位数，这个中间的位置将一排序列分为左右两部分，通过一次比较后，就缩小了比较的范围，重复这样的 *** 作，需要插入的元素就找到了合适的位置了。

//------------插入排序---void InsertSort(SqList &L){//对顺序表L作直接插入排序。 int i,j; for(i=2;i<=Llength;++i) if(LT(Lr[i]key,Lr[i-1]key))//“<”，需将Lr[i]插入有序子表 { Lr[0]=Lr[i];//复制为哨兵 Lr[i]=Lr[i-1]; for(j=i-2;LT(Lr[0]key,Lr[j]key);--j) Lr[j+1]=Lr[j];//记录后移 Lr[j+1]=Lr[0];//插入到正确位置 }}//--------------冒泡排序---void BubbleSort(SqList &L){//Lr是待排序的文件，采用自下向上扫描，对Lr做冒泡排序 int i,j; int exchange; // 交换标志 for(i=1;i<Llength;i++) {// 最多做 n-1 趟排序 exchange=FALSE; // 本趟排序开始前，交换标志应为假 for(j=Llength-1;j>=i;j--) // 对当前无序区 R[in] 自下向上扫描 if(LT(Lr[j+1]key,Lr[j]key)) { // 交换记录 Lr[0]=Lr[j+1]; //Lr[0]不是哨兵，仅做暂存单元 Lr[j+1]=Lr[j]; Lr[j]=Lr[0]; exchange=TRUE; // 发生了交换，故将交换标志置为真 } if(!exchange) // 本趟排序未发生交换，提前终止算法 return; } }//-----------快速排序---int Partition(SqList &L,int low,int high){//交换顺序表L中子表r[lowhigh]的记录，枢轴记录到位，并返回其所在位置，此时 //在它之前（后）的记录均不大（小）于它。 KeyType pivotkey; Lr[0]=Lr[low];//用子表的第一个记录作枢轴记录 pivotkey=Lr[low]key;//枢轴记录关键字 while(low<high) {//从表的两端交替地向中间扫描 while (low<high&&Lr[high]key>=pivotkey) --high; Lr[low]=Lr[high];//将比枢轴记录小的记录移到低端 while (low<high&&Lr[low]key<=pivotkey) ++low; Lr[high]=Lr[low];//将比枢轴记录大的记录移到高端 } Lr[low]=Lr[0];//枢轴记录到位 return low;//返回枢轴位置} void QSort(SqList &L,int low,int high){//对顺序表L中的子序列Lr[lowhigh]进行快速排序 int pivotloc; if(low<high) {//长度大于1 pivotloc=Partition(L,low,high);//将Lr[lowhigh]一分为二 QSort(L,low,pivotloc-1);//对低子表递归排序pivotloc是枢轴位置 QSort(L,pivotloc+1,high);//对高子表递归排序 }} void QuickSort(SqList &L){//对顺序表L作快速排序。 QSort(L,1,Llength);}//----------归并排序---void Merge(RedType SR[],RedType TR[],int i,int m,int n){//将有序的SR[im]和SR[m+1n]归并为有序的TR[in] int j,k; for(j=m+1,k=i;i<=m&&j<=n;++k) {//将SR中记录由小到大地并入TR if LQ(SR[i]key,SR[j]key) TR[k]=SR[i++]; else TR[k]=SR[j++]; } if(i<=m)//TR[kn]=SR[im];将剩余的SR[im]复制到TR while(k<=n&&i<=m) TR[k++]=SR[i++]; if(j<=n)//将剩余的SR[jn]复制到TR while(k<=n&&j<=n) TR[k++]=SR[j++];} void MSort(RedType SR[],RedType TR1[],int s,int t){//将SR[st]归并排序为TR1[st]。 int m; RedType TR2[20]; if(s==t) TR1[t] = SR[s]; else { m=(s+t)/2;//将SR[st]平分为SR[sm]和SR[m+1t] MSort(SR,TR2,s,m);//递归地将SR[sm]归并为有序的TR2[sm] MSort(SR,TR2,m+1,t);//将SR[m+1t]归并为有序的TR2[m+1t] Merge(TR2,TR1,s,m,t);//将TR2[sm]和TR2[m+1t]归并到TR1[st] }} void MergeSort(SqList &L){// 对顺序表L作归并排序。 MSort(Lr, Lr, 1, Llength);}//-----------堆排序---void HeapAdjust(SqList &H,int s,int m){//已知Hr[sm]中记录的关键字除Hr[s]key之外均满足堆的定义， //本函数调整Hr[s]的关键字，使Hr[sm]成为一个大顶堆 //（对其中记录的关键字而言） int j; RedType rc; rc=Hr[s]; for(j=2s;j<=m;j=2) {//沿key较大的孩子结点向下筛选 if(j<m&&Hr[j]key<Hr[j+1]key) ++j;//j为key较大的记录的下标 if(rckey>=Hr[j]key) break;//rc应插入在位置s上 Hr[s]=Hr[j]; s=j; } Hr[s]=rc;//插入} void HeapSort(SqList &H){//对顺序表H进行堆排序。 int i; RedType temp; for(i=Hlength/2;i>0;--i)//把Hr[1Hlength]建成大顶堆 HeapAdjust(H,i,Hlength); for(i=Hlength;i>1;--i) { temp=Hr[i]; Hr[i]=Hr[1]; Hr[1]=temp;//将堆顶记录和当前未经排序子序列Hr[1i]中 //最后一个记录相互交换 HeapAdjust(H,1,i-1);//将Hr[1i-1]重新调整为大顶堆 }} void main(){ SqList S; printf("---------- 五种排序算法 ----------\n"); InitList_Sq(S); printf(" 1简单插入排序\n"); InsertSort(S); Print_Sq(S); printf(" 2冒泡排序\n"); BubbleSort(S); Print_Sq(S); printf(" 3快速排序\n"); QuickSort(S); Print_Sq(S); printf(" 4归并排序\n"); MergeSort(S); Print_Sq(S); printf(" 5堆排序\n"); HeapSort(S); Print_Sq(S);}

#include <stdioh>

int main()

{

int a[10],i,j,tem;

for(i=0;i<=9;i++)

{

printf("请输入第%d个数:",i+1);

scanf("%d",&a[i]);

}

for(i=0;i<=8;i++)

for(j=0;j<=1-i;j++)

if(a[j]>a[j+1])

{

tem=a[i];

a[i]=a[i+1];

a[i+1]=tem;

}

for(i=0;i<=9;i++)

printf("%d ",a[i]);

return 0;

}

排序：

#include<stdioh>

#define N 10

void Display(int a, int n)

{

int i;

for (i = 0; i < n; i++) {

printf("%d ", a[i]);

}

printf("\n");

}

void SelectionSort(int a, int n)

{

int i, j, index, value;

for (i = 0; i < n - 1; i ++) {

index = i;

value = a[i];

for (j = i + 1; j < n; j ++)

if (value > a[j]) {

index = j;

value = a[j];

}

a[index] = a[i];

a[i] = value;

Display(a, n);

}

}

void main()

{

int a[N],i ;

for(i=0;i<N;i++)

a[i]=N-i;

Display(a, N);

SelectionSort(a, N);

}

折半查找：

int binarysearch(int number)

{

int mid, start = 0, end = LEN - 1;

/ 假定a是排好序的 /

/ mustbe(start, end, number)，因为a[startend]就是整个数组a[0LEN-1] /

while (start <= end) {

/ mustbe(start, end, number)，因为一开始进入循环时是正确的，每次循环也都维护了这个条件 /

mid = (start + end) / 2;//取a数组中间的值，与number比较

if (a[mid] < number)

/ 如果a数组中间值小于number，那么number一定要在mid后的后半段数组中，所以我们就将mid+1，将这个作为start，number必然在后半段数组a[mid+1,end]中/

start = mid + 1;

else if (a[mid] > number)

/如果a数组中间值大于number，那么number一定在mid前的前半段数组中，那么应该将mid-1，这个mid-1就是前半段数组的最后一个元素 /

end = mid - 1;

else

/ a[mid] == number，说明找到了 /

return mid;

}

/

mustbe(start, end, number)一直被循环维护着，到这里应该仍然成立，在a[startend]范围之外一定不存在number，

但现在a[startend]是空序列，在这个范围之外的正是整个数组a，因此整个数组a中都不存在number

/

return -1;

}

// hgjkgcpp : 定义控制台应用程序的入口点。

//

#include "stdafxh"

#define n 11

int count=0;

int bin_search(int a[],int low,int high,int x) //折半查找函数

{ count++;

int mid;

if(low>high) return -1;

else

{

mid=(low+high)/2;

if(x==a[mid]) return mid;

else if(x<a[mid])

return bin_search(a,low,mid-1,x);

else

return bin_search(a,mid+1,high,x);

}

}

int _tmain(int argc, _TCHAR argv[])

{

int s;

int a[n]={3,5,8,10,15,22,28,30,31,55};

s=bin_search(a,0,9,28);

if(s==-1){

printf("没有找到要查询的数\n");

printf("本次查询总用了 %d 次\n",count);

}

else

{

printf("本次查询总用了 %d 次\n",count);

printf("本次查找到的下标是: %d \n",s);

}

return 0;

}

这程序我已经运行成功了，我是在VS2005环境下运行的

以上就是关于用JAVA实现折半插入排序的题目全部的内容，包括:用JAVA实现折半插入排序的题目、c语言编程实现“折半查找”的过程。、折半插入排序等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！