折半插入排序顺序结构

    xiaoxiao2021-12-10  21

    201672808:21:18 折半插入排序:折半插入排序算法是对直接插入排序算法的改进,它的主要改进在于在已经有序的子集中确定待排序元素的位置 找到要插入的位置后,将相应的元素插入到该位置即可; 假设所给的数据为:[67,53,73,21] 第一趟排序:初始的状态为:[67,|53,73,21] t = 53,在有序子集中min = 0,max = 0;->mid = (min+max)/2 = 053与L->data[mid]进行比较->发现53<67;更新有序子集的查找范围:max = mid-1 = -1; ___________________________________________________________________________________ 注意:假设[67,|67,73,21] t = 67,在有序子集中min = 0,max = 0;->mid = (min+max)/2 = 06767进行比较,发现相等,那么为了排序的稳定性,排序前第二位置的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 = 173与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 =16767比较,发现相等,那么那么为了排序的稳定性,排序前第二位置的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

    最新回复(0)