python 归并排序

排序思路:

1.将数组分成两组A,B,建立临时数组 C,C长度=A + B

2. i,j分别属于A,B

3. 若A[i] > B[j] , 将B[j]放入C, j++; 否则 A[i]放入C, i++

4.循环3步骤,将A或B中剩余的元素放入C,再将C复制到数组中

5.递归3-4直到A,B序列的长度=1

 

#归并排序
class MergeSort:

    def __init__(self, arrData):
        self.arrData = arrData;
        self.tmpData=[];
        #建立临时数组
        for i in range(len(self.arrData)):
            self.tmpData.append(0);
        return;
    #left 要排序的序列的最小索引
    #right 要排序的序列的最大索引
    def sortHalf(self,arrData,left,right):
        center = (left + right) // 2;
        self.mergeSort(arrData,left,center,right);
        return;
    #排序方法
    #[left,center]为第一个序列
    #[center, right]为第二个序列
    #两个序列进行归并排序
    def mergeSort(self,arrData,left,center,right):
        ##将左边和右边递归分别分成两组再进行排序
        #直到两个序列的长度为1后停止递归
        if left < center :
           self.sortHalf(arrData,left,center);
        if center < right:
            self.sortHalf(arrData,center+1,right);
        i = left;
        j = center + 1;
        k = i;
        #排序算法
        while k <= right:
            #print(i,center,j);
            if i > center:
                self.tmpData[k] = arrData[j];
                j = j + 1;
            elif j > right:
                self.tmpData[k] = arrData[i];
                i = i + 1;
            elif arrData[i] > arrData[j]:
                self.tmpData[k] = arrData[j];
                j = j + 1;
            else:
                self.tmpData[k] = arrData[i];
                i = i + 1;
            k = k + 1;
        #复制tmpData序列到arrData序列
        for l in range(left,right + 1):
            arrData[l] = self.tmpData[l];
        return;
    #排序入口
    def sort(self):
        arrData = self.arrData;
        left = 0;
        right = len(arrData) - 1;
        center = (left + right) // 2;
        self.sortHalf(arrData,left,right);
        return;
    def __del__(self):
        del self.tmpData;
arr = [7,2,5,3,1,8,6,100,48,38,45,20,34,67,12,23,90,58];
print(arr);
shellSort = MergeSort(arr);
shellSort.sort();
print(arr);

 

归并排序的时间复杂度为O(nLog2n),空间效率较差