python 归并排序

coverl

　　排序思路:
　　1.将数组分成两组A,B,建立临时数组 C,C长度=A + B
　　2. i,j分别属于A,B
　　3. 若A > B[j] , 将B[j]放入C, j++; 否则 A放入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 + 1;
elif arrData > arrData[j]:
self.tmpData[k] = arrData[j];
j = j + 1;
else:
self.tmpData[k] = arrData;
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),空间效率较差