网络热词 > 二分法插入排序

二分法插入排序

在插入第i个元素时,对前面的0~i-1元素进行折半,先跟他们 中间的那个元素比,如果小,则对前半再进行折半,否则对后半 进行折半,直到left>right,然后再把第i个元素前1位与目标位置之间 的所有元素后移,再把第i个元素放在目标位置上。 二分法没有排序,只有查找。所以当找到要插入的位置时。移动必须从最后一个记录开始,向后移动一位,再移动倒数第2位,直到要插入的位置的记录移后一位。

在插入第i个元素时,对前面的0~i-1元素进行折半,先跟他们 中间的那个元素比,如果小,则对前半再进行折半,否则对后半 进行折半,直到left>right,然后再把第i个元素前1位与目标位置之间 的所有元素后移,再把第i个元素放在目标位置上。 二分法没有排序,只有查找。所以当找到要插入的位置时。移动必须从最后一个记录开始,向后移动一位,再移动倒数第2位,直到要插入的位置的记录移后一位。

二分插入排序是稳定的与二分查找的复杂度相同;

最好的情况是当插入的位置刚好是二分位置 所用时间为O(n);

最坏的情况是当插入的位置不在二分位置 所需比较次数为

n

S<=∑n「logn「-2^n「logn「+1

k= 1

平均时间O(n^2)

/* 二分法插入排序的算法源程序*/

#include<stdio.h>

#define MAXNUM 100

typedef int KeyType;

typedef int DataType;

typedef struct {

KeyType key; /* 排序码字段 */

/*DataType info; 记录的其它字段 */

} RecordNode;

typedef struct {

int n; /* n为文件中的记录个数,n<MAXNUM */

RecordNode record[MAXNUM];

} SortObject;

void binSort(SortObject * pvector) { /* 按递增序进行二分法插入排序 */

int i, j, left, mid, right;

RecordNode temp;

RecordNode *data = pvector->record;

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

temp = data;

left = 0; right = i-1; /* 置已排序区间的下、上界初值 */

while (left <= right) {

mid = (left + right)/2; /* mid指向已排序区间的中间位置 */

if (temp.key < data[mid].key)

right = mid-1; /* 插入元素应在左子区间 */

else left = mid+1; /* 插入元素应在右子区间 */[Page]

}

for (j = i-1; j >= left; j--)

data[j+1] = data[j]; /* 将排序码大于ki的记录后移 */

if (left != i) data[left] = temp;

}

}

SortObject vector={10, 49,38,65,97,76,13,27,49,50,101};

int main(){

int i;

binSort(&vector);

for(i = 0; i < vector.n; i++)

printf(\"%d \", vector.record);

getchar();

return 0;

}

public static int[] BarnarySort(int[] data) {

int[] temp = new int[data.length];

for (int i = 0; i < temp.length; i++) {

if (i == 0) {

temp = data;

} else {

for (int j = 0, k = i - 1; j < i && k >= 0;) {

if (temp[(j + k) / 2] >= data) {

if ((j + k) / 2 == 0) {

for (int iter = i; iter > 0; iter--) {

temp[iter] = temp[iter - 1];

}

temp[0] = data;

break;

} else if (temp[(j + k) / 2 - 1] <= data) {

for (int iter = i; iter > (j + k) / 2; iter--) {

temp[iter] = temp[iter - 1];

}

temp[(j + k) / 2] = data;

break;

} else {

k = (k + j) / 2-1;

}

} else if (temp[(j + k) / 2] < data) {

if ((j + k) / 2 == i - 1) {

temp = data;

break;

} else {

j=(k + j) / 2+1;

}

}

}

}

}

return temp;

}

All rights reserved Powered by 网络热词 87994.com

copyright ©right 2010-2020。
网络热词内容来自网络,如有侵犯请联系客服。zhit325@126.com