Python折半插入排序

折半插入排序是插入排序的一种,这是直接插入排序的改进,当将要为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[i];
        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 = 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[i];
        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 = 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]);