2016年
7月
28日
08:
21:
18
折半插入排序:折半插入排序算法是对直接插入排序算法的改进,它的主要改进在于在已经有序的子集中确定待排序元素的位置
找到要插入的位置后,将相应的元素插入到该位置即可;
假设所给的数据为:[
67,
53,
73,
21]
第一趟排序:初始的状态为:[
67,|
53,
73,
21]
t =
53,在有序子集中
min =
0,
max =
0;->mid = (
min+
max)/
2 =
0
将
53与L->data[mid]进行比较->发现
53<
67;更新有序子集的查找范围:
max = mid-
1 = -
1;
___________________________________________________________________________________
注意:假设[
67,|
67,
73,
21]
t =
67,在有序子集中
min =
0,
max =
0;->mid = (
min+
max)/
2 =
0
将
67与
67进行比较,发现相等,那么为了排序的稳定性,排序前第二位置的
67,在第一个位置前面,
排序后它也应该在第一个的前面,
_____________________________________________________________________________________
发现
max<
min这时就不能继续查找了,需要查找的位置已经找到,即为
min,将
min到有序子集
的元素向后移动->[
67,|
67,
73,
21]
将元素插入到
min所在的位置:->[
53,|
67,
73,
21]
同时有序子集的个数增加一个->[
53,
67|
73,
21]
第二趟排序:初始的状态为:[
53,
67|
73,
21]
t =
73,在有序子集中
min =
0,
max =
1;->mid = (
min +
max )/
2 =
0;
将
73与L->data[mid]进行比较->发现
73>
53;更新有序子集的查找范围:
min = mid+
1 =
1;中间mid = (
min+
max)/
2 =
1
将
73与L->data[mid]进行比较->发现
73>
67;更新有序子集的查找范围:
min = mid+
1 =
2;发现
max<
min
这时就不用再继续查找了,需要查找的位置已经找到,即为
min =
2;
这时不用移动有序表表中的元素了,直接将元素插入到它原来的位置;
同时有序表子集的个数增加一个->[
53,
67,
73|
21]
第三趟排序:初始的状态为:[
53,
67,
73|
21]
______________________________________________________________________________________
注意:假设[
53,
67,
73|
67]
在有序子集中
min =
0,
max =
2;->mid = (
min+
max)/
2 =
1
将
67和
67比较,发现相等,那么那么为了排序的稳定性,排序前第二位置的
67,在第一个位置前面,
排序后它也应该在第一个的前面,[
53,
67,
73|
73]->[
53,
67,
67,
73],即令
min = mid+
1
______________________________________________________________________________________
t =
21;在有序子集中
min =
0,
max =
2;->mid = (
min +
max )/
2 =
1;
将
21与L->data[mid]进行比较->发现
21<
67;更新有序子集的查找范围:
max = mid-
1 =
0;中间mid = (
min+
max)/
2 =
0;
将
21与L->data[mid]进行比较->发现
21<
53;更新有序子集的查找范围:
max = mid-
1 = -
1;发现
max<
min
这时就不用再继续查找了,需要查找的位置已经找到,即为
min =
0;
将
min及其有序表后面的所有元素都往后移动一个元素的位置;
[
53,
67,
73|
21]->[
53,
67,
73|
73]->[
53,
67,
67|
73]->[
53,
53,
67|
73]
最后将当前的元素插入到
min所在的位置;
同时有序表子集的个数增加一个->[
53,
67,
73,
21|]
当未排序的子集中元素为空,算法执行结束;
#include<stdio.h>
#include<stdlib.h>
#define MAXISIZE 100
#define random(x)(rand()%x)
//顺序表结构体类型
typedef struct
{
int
data[MAXISIZE];
int length;
}
SeqList;
//函数前置声明
void initSeqList(
SeqList *
S);
void seqListAssign(
SeqList *
S);
void traverseSeqList(
SeqList *
S);
void binInsertSort(
SeqList *
S);
//折半插入排序
void binInsertSort(
SeqList *
S)
{
int i,j;
int min,max,mid;
int tempVal;
for( i =
1;i<
S->length;i++)
{
tempVal =
S->
data[i];
min =
0;
max = i-
1;
mid = (min+max)/
2;
while(min<=max)
{
if(tempVal<
S->
data[mid])
{
max = mid-
1;
mid = (min+max)/
2;
}
else if(tempVal>=
S->
data[mid])
{
min = mid+
1;
mid = (min+max)/
2;
}
/*
else
{
min = mid +
1;
break;
}*/
}
for(j = i-
1;j>= min;j
{
/*
S->
data[i] = S->data[i-1];
S->
data[i-1] = S->data[i-2];
...
S->
data[min+1] = S->data[min];
*/
S->
data[j+1] = S->data[j];
}
S->
data[min] = tempVal;
/*for( j =
0;j<=i-
1&&min<=max;j++)
{
min = j;
max = i-
1;
mid = (min+max)/
2;
if(tempVal<
S->
data[mid])
{
max = mid-
1;
}
else if(tempVal>
S->
data[mid])
{
min = mid+
1;
}
}*/
//
S->
data[min] = tempVal;
}
return;
}
//初始化顺序表
void initSeqList(
SeqList *
S)
{
S->length =
0;
return ;
}
//给顺序表赋值
void seqListAssign(
SeqList *
S)
{
int i;
for(i =
0;i<
MAXISIZE;i++)
{
S->
data[i] = random(100);
}
S->length =
MAXISIZE;
return;
}
//将顺序表中的元素遍历输出
void traverseSeqList(
SeqList *
S)
{
int i;
for( i =
0;i<
S->length;i++)
{
printf(
"%-6d",
S->
data[i]);
}
printf(
"\n");
return ;
}
//主函数
int main(void)
{
SeqList S;
initSeqList(&
S);
seqListAssign(&
S);
printf(
"产生的随机数据为:\n");
traverseSeqList(&
S);
binInsertSort(&
S);
printf(
"排序后数据为:\n");
traverseSeqList(&
S);
return
0;
}
转载请注明原文地址: https://ju.6miu.com/read-700035.html