leetcode常规算法题复盘（基础篇）—

leetcode常规算法题复盘（基础篇）——十大排序算法（二）

 1   ##############################
 2  #        6、快速排序          #
 3 #############################
 4 def QuickSort(array,left,right):
 5     lenth = len(array)
 6     left = left if type(left) is int else 0 
 7     right = right if type(right) is int else lenth-1 
 8     if left<right:
 9         partitionIndex = partition(array,left,right)
10         QuickSort(array,left,partitionIndex-1)
11         QuickSort(array,partitionIndex+1,right)
12     return array
13 
14 def partition(array,left,right):
15     pivot = left
16     index = pivot+1
17     for i in range(index,right+1):
18         if array[i]<array[pivot]:
19             temp = array[i]
20             array[i] = array[index]
21             array[index] = temp
22             index += 1
23     temp = array[pivot]
24     array[pivot] = array[index-1]
25     array[index-1] = temp
26     return index-1

 1   ##############################目前还有些问题
 2  #         7、堆排序           #
 3 #############################
 4 def buildMaxHeap(array):
 5     lenth = len(array)
 6     for i in range(lenth//2,-1,-1):
 7         heapify(array,i)
 8 def heapify(array,i):
 9     left = 2*i+1
10     right = 2*i+2
11     largest = i
12     if left<lenth and array[left]>array[largest]:
13         largest = left
14     if right<lenth and array[right]>array[largest]:
15         largest = right
16     if largest != i:
17         temp = array[i]
18         array[i] = array[largest]
19         array[largest] = temp
20 def HeapSort(array):
21     lenth = len(array)
22     buildMaxHeap(array)
23     for i in range(len(array)-1,0,-1):
24         temp = array[i]
25         array[i] = array[0]
26         array[0] = temp
27         lenth += -1
28         heapify(array,0)
29     return array

 1   ##############################
 2  #        8、计数排序          #
 3 #############################
 4 def CountingSort(array,maxValue):
 5     bucket = [0]*(maxValue+1)
 6     sortedIndex = 0
 7     arrLen = len(array)
 8     bucketLen = maxValue+1
 9     for i in range(0,arrLen):
10         bucket[array[i]] += 1
11     for j in range(0,bucketLen):
12         while(bucket[j]>0):
13             array[sortedIndex] = j
14             sortedIndex += 1
15             bucket[j] += -1
16              
17              
18     return array

 1   ##############################
 2  #         9、桶排序           #
 3 #############################
 4 def BuckerSort(array,bucketSize):
 5     if len(array) == 0:
 6         return array
 7     minValue = array[0]
 8     maxValue = array[0]
 9     for i in range(1,len(array)):
10         if array[i]<minValue:
11             minValue = array[i]
12         if array[i]>maxValue:
13             maxValue = array[i]
14             
15     DEFAULT_BUCKET_SIZE = 5
16     bucketSize = bucketSize or DEFAULT_BUCKET_SIZE
17     bucketCount = ((maxValue-minValue)//bucketSize)+1
18     buckets = []
19     for i in range(0,len(buckets)):
20         buckets[i] = []
21     for i in range(0,len(array)):
22         buckets[(array[i]-minValue)//bucketSize].append(array[i])
23     array = []
24     for i in range(0,len(buckets)):
25         InsertionSort(buckets[i])
26         for j in range(0,len(buckets[i])):
27             array.append(buckets[i][j])
28             
29             
30     return array

 1   ##############################
 2  #       10、基数排序        #
 3 #############################
 4 def RadixSort(array,maxDigit):
 5     counter = [0]*10
 6     mod = 10
 7     dev = 1
 8     for i in range(0,maxDigit):
 9         for j in range(0,len(array)):
10             bucket = int((array[j] % mod) / dev)#求基数
11             
12             counter[bucket] = []
13             counter[bucket].append(array[j])
14         dev *= 10
15         mod *= 10
16     pos = 0
17     for j in range(0,len(counter)):
18         value = None
19         if counter[j] is not None:
20             while(len(counter[j]) != 0):
21                 value = counter[j].pop(0)
22                 array[pos] = value
23                 pos += 1
24                 
25                 
26     return array