Sorting Algorithm in Python
copy and learn
Quick sort
def quick_sort(lists,i,j):
if i >= j:
return list
pivot = lists[i]
low = i
high = j
while i < j:
while i < j and lists[j] >= pivot:
j -= 1
lists[i]=lists[j]
while i < j and lists[i] <=pivot:
i += 1
lists[j]=lists[i]
lists[j] = pivot
quick_sort(lists,low,i-1)
quick_sort(lists,i+1,high)
return lists
if __name__=="__main__":
lists=[30,24,5,58,18,36,12,42,39]
print("排序前的序列为:")
for i in lists:
print(i,end =" ")
print("\n排序后的序列为:")
for i in quick_sort(lists,0,len(lists)-1):
print(i,end=" ")
Time Complexity in average: O(nlogn)
Space Complexity in average: O(logn)
Principle: find the correct place of each number one by one
Bubble Sort
def bubbleSort(arr):
n = len(arr)
# 遍历所有数组元素
for i in range(n):
# Last i elements are already in place
for j in range(0, n-i-1):
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]
arr = [64, 34, 25, 12, 22, 11, 90]
bubbleSort(arr)
print ("排序后的数组:")
print(arr)
Time Complexity in average: O(n²)
Space Complexity in average: O(1)
Principle: only switch with the next number