Python折半插入排序
折半插入排序是插入排序的一种,这是直接插入排序的改进,当将要为i元素排序时,位置的元素已有序,用折半查找法比顺序查找一般要快些.实现思路:
i属于,
在中取得中间位置k=(min+max)/2,这个区间已排好序,递归比较中间值, 直到 |min-max| <=1为止,将i元素插入到k附近.
#折半排序类
class HalfInsertSort:
#开始排序
#arrData:要排序的数组
def sort(self, arrData):
for i in range(1,len(arrData)):
self.halfSort(arrData,i,0,i-1);
print(arrData);
return;
#折半排序
#target:要排序的目标的索引值
#mi:已排序的最小索引
#ma:已排序的最大索引
#target要在中查找合适的位置
def halfSort(self,arrData,target,mi,ma):
i=(mi+ma)//2;#中间索引
c=arrData-arrData;
if mi==ma or i==ma or i==mi:
d=arrData-arrData;
if c>=0 and d<0:
self.insert(arrData,target,i + 1);
elif c<0:
self.insert(arrData,target,i);
elif d>=0:
self.insert(arrData,target,ma + 1);
return;
if c>0:
self.halfSort(arrData,target,i+1,ma);
elif c==0:
self.insert(arrData,target,i+1);
return;
else:
self.halfSort(arrData,target,mi,i-1);
return;
#将目录插入到dest位置
def insert(self,arrData,target,dest):
tmp=arrData;
i = target - 1;
#将dest身后的已排序的元素向后移动一位
while i>=dest:
arrData=arrData;
i = i -1;
arrData=tmp;
return;
sortVal=HalfInsertSort();
sortVal.sort();
自己实现的排序算法还是和书上的不一样,不用递归更简单些
#折半排序类
class HalfInsertSort:
#开始排序
#arrData:要排序的数组
def sort(self, arrData):
for i in range(1,len(arrData)):
self.halfSort(arrData,i,0,i-1);
print(arrData);
return;
#折半排序
#target:要排序的目标的索引值
#mi:已排序的最小索引
#ma:已排序的最大索引
#target要在中查找合适的位置
def halfSort(self,arrData,target,mi,ma):
i=(mi+ma)//2;#中间索引
c=arrData-arrData;
if mi==ma or i==ma or i==mi:
d=arrData-arrData;
if c>=0 and d<0:
self.insert(arrData,target,i + 1);
elif c<0:
self.insert(arrData,target,i);
elif d>=0:
self.insert(arrData,target,ma + 1);
return;
if c>0:
self.halfSort(arrData,target,i+1,ma);
elif c==0:
self.insert(arrData,target,i+1);
return;
else:
self.halfSort(arrData,target,mi,i-1);
return;
#将目录插入到dest位置
def insert(self,arrData,target,dest):
tmp=arrData;
i = target - 1;
#将dest身后的已排序的元素向后移动一位
while i>=dest:
arrData=arrData;
i = i -1;
arrData=tmp;
return;
#非递归插入排序
def halfSort_(self,arrData,target,mi,ma):
low = mi;
high = ma;
k = 0;
while low <= high:
k = (low + high) // 2;
if arrData > arrData:
low = k+1;
else:
high = k - 1;
if arrData >= arrData:
self.insert(arrData,target,k+1);
else:
self.insert(arrData,target,k);
return;
def sort_(self, arrData):
for i in range(1,len(arrData)):
self.halfSort_(arrData,i,0,i-1);
print(arrData);
return;
sortVal=HalfInsertSort();
sortVal.sort_();
页:
[1]