本文目录
- 1,2,3,4，用冒泡排序法，折半查找法等方法求它们的具体解答过程
- 用c语言写一个算法（折半或二分法），实现可以选择1到20的从小到大以
- 用折半插入排序算法，解决例1.
- 折半插入排序例题
- c语言中的折半排序法是怎样的，基本程序是怎样的
- 折半插入排序
- 折半插入排序和归并排序
- 求详细解释 排序算法 折半插入排序and简单选择排序（）
- 折半插入排序和直接插入排序的区别
1,2,3,4，用冒泡排序法，折半查找法等方法求它们的具体解答过程
折半查找是1.给一个定值key与中间位置记录的关键字进行比较，若相等则查找成功2.若不相等则利用中间位置记录将表对分成前后俩子表，若key比中间位置记录的关键字小，则下一次只在前一子表中继续查找，否则在后一子表中继续查找3.重复1.2，将查找区间不断对分，直到查找成功，或者当前查找区间为空，查找失败。冒泡排序1.设待排序的记录放在数组r〔1，n〕中。首先将第一二个记录的关键字进行比较，若一大于二，则交换两个记录，然后比较二三，以此类推，直到第n－1个记录和第n个记录的关键字进行比较为止，这是第一趟排序2.进行第二趟排序，对前n－1个记录进行同样的操作，其结果是是关键字次大的记录被安置到第n－1个记录的位置上3.重复上述比较和交换过程，第i趟是从r〔1〕到r〔n－i＋1〕依次比较相邻两个记录的关键字，并在逆序时交换相邻记录，直到在某一趟排序过程中没有进行过交换记录的操作，说明序列已经全部达到排序要求，则完成排序。排序过程：首先将95.6与92.3比较，92.3＜95.6，所以两数交换位置，再将第二个位置的95.6与第三个位置的81.4进行比较，81.4＜95.6两数交换，依次类推，将小数放在前面，第一趟排序之后最大的分数98.4必定会在最后一个位置；按照这样的方法再对除了98.4以外的前面那些分数进行排序，第二趟结束后，第二大分数95.6就会在倒数第二的位置，再进行第三趟排序。。。直到所有分数由低到高排好。查找过程：假设输入的成绩为92.3，此时表已排好序，分别是：79.8 81.4 82.1 86.5 88.7 88.9 92.3 93.2 95.6 98.4首先将92.3与此表中间的数88.7进行比较，92.3大，所以只在88.7后面那些数字中再进行折半查找，后面子表中间位置的数是93.2，而93.2＞92.3，所以在此前面的子表进行比较，也就是88.9 92.3这一子表，此时中间位置即为88.9，小于92.3，而现在表中只有92.3，相等，查找成功。。。没有表示指针移动情况，感觉这样比较易懂
用c语言写一个算法（折半或二分法），实现可以选择1到20的从小到大以
解：用有序列插入法排序，过程如下：第一步：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
用折半插入排序算法，解决例1.
思路分析：用折半插入排序法将一新数据插入到一有序列中，就是反复运用“折半”思想，寻找新数据所在的位置的过程. 用折半插入排序法，设计算法步骤如下： 第一步：把新数据38与“中间位置”的数据26比较，由于38＞26，所以应将38放到26的右边的一半有序列中，即应放到有序列37，39，46，70中. 第二步：把38与有序列37，39，46，70“中间位置”的数据39比较，由于38＜39，所以应将38放到39的左边的一半有序列中，即应放到有序列37，39中. 第三步：把38与有序列37，39“中间位置”的数据37比较，由于38＞37，所以应将38放到37的右边的一半有序列中，至此排序完成，得到一新的有序列 10 13 18 26 37 38 39 46 70 温馨提示 有序插入排序法就是先比较两个数的大小，再把其余的数依次进行比较插入到这个数列中.而折半插入排序法是先将新数据与“中间位置”的数据进行比较，把原有序列折半，直到确定新数据应有的位置.
折半插入排序例题
折半插入排序仍然是一种插入排序,与基本的插入排序算法没有区别.只是在搜索插入位置时使用折半(二分)查找的方法. 过程示例 13 30 70 85 39 42 6 20 //136所以在39之前,13 30 39 中间数为30,30》6所以在30之前,13 30中间数为13,13》6所以在13之前,所以13之前插入6 6 13 20 30 39 42 70 85 //20需要被排序,在确认其插入位置时20前为已经排序的6 13 30 39 42 70 85,中间数为39,39》20所以在39之前,6 13 30 39 中间数为13,1320所以在30之前,所以13与30间插入20
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={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;}
折半插入排序
折半插入排序是对插入排序算法的一种改进。所谓插入排序，就是不断的依次将元素插入前面已排好序的序列中。
折半插入排序（binary insertion sort）是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。
在将一个新元素插入已排好序的数组的过程中，寻找插入点时，将待插入区域的首元素设置为a。
折半插入排序算法是一种稳定的排序算法，比直接插入算法明显减少了关键字之间比较的次数，因此速度比直接插入排序算法快，但记录移动的次数没有变，所以折半插入排序算法的时间复杂度仍然为O(n^2)，与直接插入排序算法相同。附加空间O(1)。
折半查找只是减少了比较次数，但是元素的移动次数不变，所以时间复杂度为O(n^2)是正确的！
折半插入排序和归并排序
所有程序在win-tc和Dev-c++下都调试通过。 1 折半插入排序： #include 《stdio.h》 #include 《stdlib.h》 #define LT(a,b) ((a)《(b)) #define GT(a,b) ((a)》(b)) void output(unsigned int *a, signed int n) { signed int i; for (i=0; i《n; i++) { printf("%-5d",a); } printf("\n"); } /* 折半插入 */ void binInset(unsigned int *a, signed int i) { signed int left=0,right=i-1; signed int k; unsigned int temp=a将被覆盖，故暂存 */ while (left《=right) { signed int middle=(left+right)/2; if (LT(temp,a))/* LT: 《的宏 */ { right=middle-1; } else left=middle+1; } /* 移位 */ for (k=i-1; k》right; k--) { a; } a=temp; } void BinSort(unsigned int *a, signed int n) { signed int i; for (i=1; i《n; i++) { binInset(a,i); } } int main() { unsigned int a={1,3,2,5,4,9,8,7,6}; signed int n=sizeof(a)/sizeof(int); BinSort(a,n); output(a,n); system("pause"); return 0; } 2 归并排序： #include 《stdio.h》 #include 《stdlib.h》 #define MAX 255 int R; void Merge(int low,int m,int high) {/* 将两个有序的子文件R归并成一个有序的 */ /* 子文件R */ int i=low,j=m+1,p=0; /* 置初始值 */ int *R1; /* R1是局部向量，若p定义为此类型指针速度更快 */ R1=(int *)malloc((high-low+1)*sizeof(int)); if(!R1) /* 申请空间失败 */ { puts("Insufficient memory available!"); return; } while(i《=m&&j《=high) /* 两子文件非空时取其小者输出到R1上 */ R1; while(i《=m) /* 若第1个子文件非空，则复制剩余记录到R1中 */ R1; while(j《=high) /* 若第2个子文件非空，则复制剩余记录到R1中 */ R1; for(p=0,i=low;i《=high;p++,i++) R */ } void Merge_SortDC(int low,int high) {/* 用分治法对R进行二路归并排序 */ int mid; if(low《high) {/* 区间长度大于1 */ mid=(low+high)/2; /* 分解 */ Merge_SortDC(low,mid); /* 递归地对R排序 */ Merge_SortDC(mid+1,high); /* 递归地对R排序 */ Merge(low,mid,high); /* 组合，将两个有序区归并为一个有序区 */ } } int main() { int i,n; printf("Please input total number of the array:\n"); scanf("%d",&n);/*输入数字个数*/ if(n《=0||n》MAX) { printf("n must more than 0 and less than %d.\n",MAX); exit(0); } puts("Please input the elements one by one:");/*输入各个数字*/ for(i=1;i《=n;i++) scanf("%d",&R); puts("The sequence you input is:"); for(i=1;i《=n;i++) printf("%4d",R); Merge_SortDC(1,n); puts("\nThe sequence after merge_sortDC is:"); for(i=1;i《=n;i++) printf("%4d",R); printf("\n"); system("pause"); return 0; }
求详细解释 排序算法 折半插入排序and简单选择排序（）
折半插入排序：我对这些名称比较模糊，但如果没有猜错，应该是快速排序算法这样子的算法，或者更准确点，有一个排序算法叫做归并排序算法。因为每次都取半，而且要处理所有元素，所以理论时间时间效率是O(nlogn)。但是这一类算法在一定情况下会退化成O(n^2)，根据算法原理，逆向思维构造数据，是可以让算法卡出翔的。所以延伸出了随机快速排序算法这一类算法。简单选择排序：这个算法比较简单，一共有n个元素，每个元素俩俩之间比较，肯定需要O(n^2)的时间复杂度。至于移动次数，跟算法中的比较函数有关系。当且仅当两个元素为逆序对的时候才尽享移动，所以移动次数最少可以为0，即序列在一开始就为有序。最多为3(n-1)次，因为移动元素需要n-1次，而每次做出移动需要一个辅助空间，即t = a, a = b, b = t，这就是常数3的由来。本人大学生ACMer，看到这个问题就手打了一下，希望能对你有帮助。我以上所有回答都需要斟酌，不排除有出错的地方。恳请发现错误的网友帮忙斧正，谢谢。@海胖博客
折半插入排序和直接插入排序的区别
教材上有写：折半插入排序基本思想和直接插入排序一样，区别在于寻找插入位置的方法不同，折半插入排序采用折半查找法来寻找插入位置。折半查找法只能对有序的序列使用。基本思想就是查找插入位置的时候，把序列分成两半（选择一个中间数mid），如果带插入数据大于mid则到右半部分序列去在进行折半查找；反之，则到左半部分序列去折半查找。折半插入排序在记录移动次数上和直接插入排序是一样，所以算法时间复杂度也是一样，只是在寻找插入位置的时候可能会节约相当多的时间。
