import random
#生成指定个数的随机数组
def gen_random_list(num):
if num<1:
return []
return [random.randint(1,100) for _ in range(num)]
"""
归并的结果存储到原数组
索引为low~mid范围的元素是有序的
索引为mid+1~high范围的元素是有序的
"""
class Merg_Sort:
def _merg(self,array,low,mid,high):
print('_merg low:{} mid:{} high:{}'.format(low,mid,high)) #打印这句话是为了跟踪栈的轨迹
left_index=low
right_index=mid+1
k=low
while k<=high:
self.temp_list[k]=array[k]
k+=1
k=low
while k<=high:
if left_index>mid: #左半边有序子列已经遍历完了
array[k]=self.temp_list[right_index]
right_index+=1
elif right_index>high: #右半边有序子列已经遍历完了
array[k]=self.temp_list[left_index]
left_index+=1
elif self.temp_list[left_index]<=self.temp_list[right_index]: #就是当前左右指针所指向的右半边元素大于左半边元素
array[k]=self.temp_list[left_index]
left_index+=1
else: # self.temp_list[left_index]>self.temp_list[right_index] 就是当前左右指针所指向的左半边元素大于右半边元素
array[k]=self.temp_list[right_index]
right_index+=1
k+=1
def sort(self,random_list,non_recursive=False):
self.temp_list=[_ for _ in random_list]
if non_recursive:
self._sort_non_recursive(random_list)
else:
self._sort_recursive(random_list,0,len(random_list)-1)
def _sort_non_recursive(self,array):
array_len=len(array)
size=1
while size<=array_len:
low=0
print('_sort_non_recursive size:{}'.format(size)) #观察栈的轨迹
while low<array_len-size:
mid=low+size-1
high=low+2*size-1 if low+2*size-1 <= array_len-1 else array_len-1
self._merg(array,low,mid,high)
low+=(size*2)
size*=2
"""
输入为:
original_list=gen_random_list(5)
print('----------------------unsort original_list:{}-----------------'.format(original_list))
Merg_Sort().sort(original_list,non_recursive=True)
print('------------------------sort original_list:{}-----------------'.format(original_list))
输出为:
----------------------unsort original_list:[19, 50, 20, 11, 14]-----------------
_sort_non_recursive size:1
| |
| |_merg low:0 mid:0 high:1 [0,1]有序,此时size为1
| |_merg low:2 mid:2 high:3 [2,3]有序,此时size为1
| |
|_sort_non_recursive size:2
| |
| |_merg low:0 mid:1 high:3 [0,3]有序,此时size为2
| |
|_sort_non_recursive size:4
| |
| |_merg low:0 mid:3 high:4 [0,4]有序,此时size为4
| |
| |
栈指针 0 1
------------------------sort original_list:[11, 14, 19, 20, 50]-----------------
"""
"""
输出为:
----------------------unsort original_list:[18, 72, 43, 94, 62, 57, 26, 55, 34, 79]-----------------
_sort_non_recursive size:1
| |
| |_merg low:0 mid:0 high:1 [0,1]有序,此时size为1
| |_merg low:2 mid:2 high:3 [2,3]有序,此时size为1
| |_merg low:4 mid:4 high:5 [4,5]有序,此时size为1
| |_merg low:6 mid:6 high:7 [6,7]有序,此时size为1
| |_merg low:8 mid:8 high:9 [8,9]有序,此时size为1
| |
|_sort_non_recursive size:2
| |
| |_merg low:0 mid:1 high:3 [0,3]有序,此时size为2
| |_merg low:4 mid:5 high:7 [4,7]有序,此时size为2
| |
|_sort_non_recursive size:4
| |
| |_merg low:0 mid:3 high:7 [0,7]有序,此时size为4
| |
|_sort_non_recursive size:8
| |
| |_merg low:0 mid:7 high:9 [0,9]有序，此时size为8
| |
| |
栈指针 0 1
------------------------sort original_list:[18, 26, 34, 43, 55, 57, 62, 72, 79, 94]-----------------
"""
def _sort_recursive(self,array,low,high):
print('_sort_recursive low:{} high:{}'.format(low,high)) #打印这句话是为了跟踪栈的轨迹
if low>=high:
return
mid=low+int( (high-low)/2 )
self._sort_recursive(array,low,mid) #将左半边排序
self._sort_recursive(array,mid+1,high) #将右半边排序
self._merg(array,low,mid,high) #归并结果
'''
输入如此:
original_list=gen_random_list(5)
print('----------------------unsort original_list:{}-----------------'.format(original_list))
Merg_Sort().sort(original_list)
print('------------------------sort original_list:{}-----------------'.format(original_list))
输出如下:
----------------------unsort original_list:[94, 33, 21, 56, 92]-----------------
_sort_recursive low:0 high:4
|
| _sort_recursive low:0 high:2
| | |
| | |_sort_recursive low:0 high:1
| | | |
| | | |_sort_recursive low:0 high:0
| | | |_sort_recursive low:1 high:1
| | | |_merg low:0 mid:0 high:1
| | | |
| | |_sort_recursive low:2 high:2
| | | |
| | |_merg low:0 mid:1 high:2
| | | |
| |_sort_recursive low:3 high:4
| | | |
| | |_sort_recursive low:3 high:3
| | |_sort_recursive low:4 high:4
| | |_merg low:3 mid:3 high:4
| | | |
| |_merg low:0 mid:2 high:4
| | | |
| | | |
栈指针 0 1 2 3
------------------------sort original_list:[21, 33, 56, 92, 94]-----------------
可见最深的时候栈为4层
输入如此:
original_list=gen_random_list(8)
print('----------------------unsort original_list:{}-----------------'.format(original_list))
Merg_Sort().sort(original_list)
print('------------------------sort original_list:{}-----------------'.format(original_list))
输出如下:
----------------------unsort original_list:[65, 80, 99, 41, 76, 40, 71, 68]-----------------
_sort_recursive low:0 high:7
| |
| |_sort_recursive low:0 high:3
| | |
| | |_sort_recursive low:0 high:1
| | | |
| | | |_sort_recursive low:0 high:0
| | | |_sort_recursive low:1 high:1
| | | |_merg low:0 mid:0 high:1
| | | |
| | |_sort_recursive low:2 high:3
| | | |_sort_recursive low:2 high:2
| | | |_sort_recursive low:3 high:3
| | | |_merg low:2 mid:2 high:3
| | | |
| | |_merg low:0 mid:1 high:3
| | | |
| |_sort_recursive low:4 high:7
| | | |
| | |_sort_recursive low:4 high:5
| | | |
| | | |_sort_recursive low:4 high:4
| | | |_sort_recursive low:5 high:5
| | | |_merg low:4 mid:4 high:5
| | | |
| | |_sort_recursive low:6 high:7
| | | |
| | | |_sort_recursive low:6 high:6
| | | |_sort_recursive low:7 high:7
| | | |_merg low:6 mid:6 high:7
| | | |
| | |_merg low:4 mid:5 high:7
| | | |
| |_merg low:0 mid:3 high:7
| | | |
| | | |
栈指针 0 1 2 3
------------------------sort original_list:[40, 41, 65, 68, 71, 76, 80, 99]-----------------
可见最深的时候栈的层数为4
'''
网友评论