def BinSort(sequence):
start = -1
sequence.insert(0,-1)
for i in range(2, len(sequence)):
x = sequence[0] = sequence[i]
left,right = 1,i-1
if x >= sequence[right]:
start = i
elif x < sequence[left]:
start = left
else:
while right - left > 1:
mid = (left + right)//2
if x >= sequence[mid]:
left = mid
else:
right = mid
start = right
move = i-1
while move >= start:
sequence[move+1] = sequence[move]
move -= 1
sequence[start] = x
return sequence[1:]
def heap_crt(Array):#index 0 as sentinal
n = len(Array) - 1
i = n//2
while i >= 1:
heap_ajt(Array, i, n)#由完全二叉树以及函数的性质 此处最后一个参数选n可以正确判断边界
i -= 1
#index 0 as sentinal
#I FOR EMPTY, J FOR CANDIDATE
#A[k...m] as a heap k < m
def heap_ajt(Array, k, m):#仅root不对劲时的调整
x = Array[0] = Array[k]
i,j = k,k*2
while j <= m :#这个while不满足，即Array[i]已无子节点
if j + 1 <= m and Array[j+1] > Array[j]:
j = j + 1#j targets the bigger
if Array[j] <= x:
break
else:#Array[j] > x
Array[i] = Array[j]
i = j
j = i * 2
Array[i] = x
def heapsort(Array):
Array.insert(0, -1)
heap_crt(Array)
n = len(Array) - 1
for i in range(n, 1, -1):
Array[1], Array[i] = Array[i], Array[1]
heap_ajt(Array, 1, i-1)
Array.pop(0)
#我认为该排序方式是稳定的
#from array1 to array2, they are different
#low <= mid < mid+1 <= high
#[low to mid], [mid+1 to high] 已有序
def MergeSort(arraya, low, high):
if low == high:
return
mid = (low + high)// 2
MergeSort(arraya, low, mid )
MergeSort(arraya,mid+1,high)
temp = [0 for i in range(high + 1)]
Merge(arraya, low, mid, high, temp)
arraya[low:high+1] = temp[low:high+1]
def Merge(array1, low, mid, high, array2):
i = low
j = mid + 1
k = low
while i <= mid and j <= high:
if array1[i] <= array1[j] :
array2[k] = array1[i]
i += 1
else:
array2[k] = array1[j]
j += 1
k += 1
while i <= mid:
array2[k] = array1[i]
i += 1
k += 1
while j <= high:
array2[k] = array1[j]
j += 1
k += 1
def QKPass(array, low, high):
if low == high:
return low
else:
x = array[low]
while low < high:
while low < high and array[high] >= x:
high -= 1
#2 possibilities; 1)low == high 2)low < high and array[high] < x
array[low] = array[high]
while low < high and array[low] < x:
low += 1
array[high] = array[low]
array[low] = x
return low
def QuickSort(array, low, high):
if low >= high:
return
r = QKPass(array, low, high)
QuickSort(array, low, r-1)
QuickSort(array, r+1, high)
def ShellInsert(sequence, delta):
sequence.insert(0, -1)
for i in range(1+delta, len(sequence)):
x = sequence[0] = sequence[i]
j = i - delta
while j > 0 and sequence[j] > x:
sequence[j+delta] = sequence[j]
j -= delta
sequence[j+delta] = x
sequence.pop(0)
def ShellSort(sequence):
delta = 4
while delta != 0:
ShellInsert(sequence, delta)
delta //= 2
|