Python实现的堆排序

堆排序属于选择排序,它其实就是一个建立大顶堆的过程

大顶堆:

ki <= k2i+1 且 ki <= k2i+2; i>=0;ki>=0& ki<=n;

堆排序相较于直接选择排序的优势在于在建堆的过程中,剩余序列元素已经部分有序,剩余部分减少交换次数,节省时间, 本人觉得也有点像冒泡排序(每一次比较后将最大值放到后面).

它的时间复杂度为O(nlogn),空间复杂度为O(1). 不稳定

 

算法思路:

1.i 为最后结点(叶子结点) (i-1)/2或(i-2)/2为它的父结点p,其实是相等的

2.p值小于i值, 交换p 和i

3.p值与另外一个子结点比较,若 p值较小,再交换

4. p= p-1,i = 2* p + 1,重复2-4

5. 若p<0,结束循环

 

import util
class HeapSort:
    def sort(self,arrData):
        for i in range(0,len(arrData)):
            self.buildMaxHeap(arrData,len(arrData) -i);
        return;
    #建立最大堆
    def buildMaxHeap(self,arrData,length):
        #最后的结点
        n = length - 1;
        #最后结点的父结点
        pn = (n-1)//2;
        while pn >=0: #父结点为为根结点后停止
            #("结点[%d]=" % n,arrData[n],",父结点[%d]=" % pn,arrData[pn]);
            if arrData[n] > arrData[pn]:
                util.swap(arrData,n,pn);
            if pn * 2 + 2 == n:
                #n为右结点
                if arrData[n - 1] > arrData[pn]:
                    util.swap(arrData,n-1,pn);
            else:
                #n为左结点
                if n + 1 < length:
                    #("左结点,有右结点为",arrData[n+1]);
                    if arrData[n + 1] > arrData[pn]:
                        util.swap(arrData,n+1,pn);
                #else:
                #("左结点,没有右结点");
            #pn设为pn的兄弟结点或父结点
            pn = pn -1;
            #n设为pn的子结点
            n = pn * 2 +1;
        #0位置为最大值
        #最大值要放到后边
        util.swap(arrData,0,length-1);
        return;

arr = [7,2,5,3,1,8,6,100,48,38,45,20,34,67,12,23,90,58];
#[3, 1, 7, 5, 6, 8, 12, 2];
#[7,2,5,3,1,8,6,100,48,38,45,20,34,67,12,23,90,58];
print(arr);
shellSort = HeapSort();
shellSort.sort(arr);
print(arr);

 

class Util:  
    @classmethod  
    def test():  
        return 0;  
  
  
def swap(arr,x,y):  
    t=arr[x];  
    arr[x]=arr[y];  
    arr[y]=t;

def printArr(arr,len):
    str ='[';
    for i in range(0,len):
        if i == len -1:
            str = str + "%d" % arr[i] ;
        else:
            str = str + "%d" % arr[i] +", ";
    str = str +"]";
    print(str);