------------------------------------------
本文为本人原创,欢迎转载!
雪夜流星
------------------------------------------
1.二分排序也叫折半插入排序,是直接插入排序的一种改进,查找插入位置的时候利用了二分查找算法,从而减少了比较和移动这两种操作的次数。实现代码如下:
- #include <stdio.h>
- #include <stdlib.h>
- /*****************************************************************
- *功能描述:二分排序(折半排序)算法
- *传入参数:num:需要排序的数组首地址, n:数组的元素
- *传出参数:num:排序后的数组首地址,传入参数和传出参数空间复用,降低空间复杂度
- *返回值: 无
- ****************************************************************/
- void B_insert_sort(int *num, int n)
- {
- int tmp, i, j, low, high, m;
-
- /*判断参数的合法性,当指针为空或者数组中只有一个元素时,直接返回*/
- if((num == NULL) || (n<2))
- {
- return;
- }
- /*把第一个节点当成有序表,将第二个节点插入到这个表中, 有序表
- 更新为两个 节点的表,把后面的节点逐个插入到不断更新的有序表中*/
- for(i=1; i<n; i++)
- {
- tmp = num[i];
- low = 0;
- high = i-1;
- /*二分查找算法:当下界low大于上界时,能够确定插入元素的位置为high+1,因为上界的
- 最后一次更新是tmp <= num[m],num[m]存放的是比tmp大并且最接近tmp的数,tmp插入到
- num[m]的位置是最适合的,此处的m=high+1*/
- while(low<=high)
- {
- m = (low+high)/2;
- if(tmp <= num[m])
- {
- high = m - 1;
- }
- else
- {
- low = m + 1;
- }
- }
-
- /*由于程序是将num[i]插入到含i个元素(num[0]--num[i-1])的有序表中,前面已经将
- num[i]的值保存在临时变量中,在找到插入的位置后,将插入位置及后面的元素均往后移
- 一位,把high+1位置腾出来放待插入元素num[i]*/
- for(j=i-1; j>=high+1; j--)
- {
- num[j+1] = num[j];
- }
- num[high+1] = tmp;
- /* 因为while退出条件为low>high,其变化量均为1,退出循环时必为low=high+1,每次查找
- 完毕后,low总比high大一,num[low]总是存放第一个比tmp大的数,因此亦可以用下面的一段程序
- 替代上面的代码
- for(j=i-1; j>=low; j--)
{
num[j+1] = num[j];
}
num[low] = tmp;
- */
- }
- return;
- }
- int main(void)
- {
- int i;
- int num[5] = {5, 4, 3, 2, 1};
-
- printf("before:\n");
- for(i=0; i<5; i++)
- {
- printf("num[%d]:%d\n", i, num[i]);
- }
-
- B_insert_sort(num, 5);
- printf("after:\n");
- for(i=0; i<5; i++)
- {
- printf("num[%d]:%d\n", i, num[i]);
- }
- return 0;
- }
阅读(2444) | 评论(1) | 转发(1) |