Python折半插入排序

banbanbai

折半插入排序是插入排序的一种,这是直接插入排序的改进,当将要为i元素排序时,[0,i-1]位置的元素已有序,用折半查找法比顺序查找一般要快些.
　　实现思路:
　　i属于[1,n], 
　　在[0,i-1]中取得中间位置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要在[mi,ma]中查找合适的位置
def halfSort(self,arrData,target,mi,ma):  
i=(mi+ma)//2;#中间索引
c=arrData[target]-arrData;
if mi==ma or i==ma or i==mi:
d=arrData[target]-arrData[ma];
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[target];
i = target - 1;
#将dest身后的已排序的元素向后移动一位
while i>=dest:
arrData[i+1]=arrData;
i = i -1;
arrData[dest]=tmp;  
return;  
sortVal=HalfInsertSort();  
sortVal.sort([7,2,5,3,1,8,6,100,48,38,45,20,34,67,12,23,90,58]);  


[2, 7, 5, 3, 1, 8, 6, 100, 48, 38, 45, 20, 34, 67, 12, 23, 90, 58]
[2, 5, 7, 3, 1, 8, 6, 100, 48, 38, 45, 20, 34, 67, 12, 23, 90, 58]
[2, 3, 5, 7, 1, 8, 6, 100, 48, 38, 45, 20, 34, 67, 12, 23, 90, 58]
[1, 2, 3, 5, 7, 8, 6, 100, 48, 38, 45, 20, 34, 67, 12, 23, 90, 58]
[1, 2, 3, 5, 7, 8, 6, 100, 48, 38, 45, 20, 34, 67, 12, 23, 90, 58]
[1, 2, 3, 5, 6, 7, 8, 100, 48, 38, 45, 20, 34, 67, 12, 23, 90, 58]
[1, 2, 3, 5, 6, 7, 8, 100, 48, 38, 45, 20, 34, 67, 12, 23, 90, 58]
[1, 2, 3, 5, 6, 7, 8, 48, 100, 38, 45, 20, 34, 67, 12, 23, 90, 58]
[1, 2, 3, 5, 6, 7, 8, 38, 48, 100, 45, 20, 34, 67, 12, 23, 90, 58]
[1, 2, 3, 5, 6, 7, 8, 38, 45, 48, 100, 20, 34, 67, 12, 23, 90, 58]
[1, 2, 3, 5, 6, 7, 8, 20, 38, 45, 48, 100, 34, 67, 12, 23, 90, 58]
[1, 2, 3, 5, 6, 7, 8, 20, 34, 38, 45, 48, 100, 67, 12, 23, 90, 58]
[1, 2, 3, 5, 6, 7, 8, 20, 34, 38, 45, 48, 67, 100, 12, 23, 90, 58]
[1, 2, 3, 5, 6, 7, 8, 12, 20, 34, 38, 45, 48, 67, 100, 23, 90, 58]
[1, 2, 3, 5, 6, 7, 8, 12, 20, 23, 34, 38, 45, 48, 67, 100, 90, 58]
[1, 2, 3, 5, 6, 7, 8, 12, 20, 23, 34, 38, 45, 48, 67, 90, 100, 58]
[1, 2, 3, 5, 6, 7, 8, 12, 20, 23, 34, 38, 45, 48, 58, 67, 90, 100]

　　自己实现的排序算法还是和书上的不一样,不用递归更简单些

#折半排序类
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要在[mi,ma]中查找合适的位置
def halfSort(self,arrData,target,mi,ma):  
i=(mi+ma)//2;#中间索引
c=arrData[target]-arrData;
if mi==ma or i==ma or i==mi:
d=arrData[target]-arrData[ma];
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[target];
i = target - 1;
#将dest身后的已排序的元素向后移动一位
while i>=dest:
arrData[i+1]=arrData;
i = i -1;
arrData[dest]=tmp;  
return;
#非递归插入排序
def halfSort_(self,arrData,target,mi,ma):
low = mi;
high = ma;
k = 0;
while low <= high:
k = (low + high) // 2;
if arrData[target] > arrData[k]:
low = k+1;
else:
high = k - 1;
if arrData[target] >= arrData[k]:
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_([7,2,5,3,1,8,6,100,48,38,45,20,34,67,12,23,90,58]);