代码计算各种排序的时间复杂度
时间: 2023-06-22 21:38:38 浏览: 45
下面是几种常见的排序算法的代码及时间复杂度注释:
1. 冒泡排序(Bubble Sort):
```python
def bubble_sort(arr):
n = len(arr)
for i in range(n):
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]
bubble_sort(arr)
print("Sorted array is:", arr)
```
时间复杂度为O(n^2)。
2. 选择排序(Selection Sort):
```python
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_index = i
for j in range(i+1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
arr = [64, 34, 25, 12, 22, 11, 90]
selection_sort(arr)
print("Sorted array is:", arr)
```
时间复杂度为O(n^2)。
3. 插入排序(Insertion Sort):
```python
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
arr = [64, 34, 25, 12, 22, 11, 90]
insertion_sort(arr)
print("Sorted array is:", arr)
```
时间复杂度最好情况为O(n),最坏情况为O(n^2)。
4. 快速排序(Quick Sort):
```python
def quick_sort(arr, low, high):
if low < high:
pivot = partition(arr, low, high)
quick_sort(arr, low, pivot-1)
quick_sort(arr, pivot+1, high)
def partition(arr, low, high):
i = low - 1
pivot = arr[high]
for j in range(low, high):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[high] = arr[high], arr[i+1]
return i+1
arr = [64, 34, 25, 12, 22, 11, 90]
n = len(arr)
quick_sort(arr, 0, n-1)
print("Sorted array is:", arr)
```
时间复杂度最好情况为O(nlogn),最坏情况为O(n^2)。
5. 归并排序(Merge Sort):
```python
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left_arr = arr[:mid]
right_arr = arr[mid:]
merge_sort(left_arr)
merge_sort(right_arr)
i = j = k = 0
while i < len(left_arr) and j < len(right_arr):
if left_arr[i] < right_arr[j]:
arr[k] = left_arr[i]
i += 1
else:
arr[k] = right_arr[j]
j += 1
k += 1
while i < len(left_arr):
arr[k] = left_arr[i]
i += 1
k += 1
while j < len(right_arr):
arr[k] = right_arr[j]
j += 1
k += 1
arr = [64, 34, 25, 12, 22, 11, 90]
merge_sort(arr)
print("Sorted array is:", arr)
```
时间复杂度为O(nlogn)。
6. 堆排序(Heap Sort):
```python
def heap_sort(arr):
n = len(arr)
for i in range(n//2-1, -1, -1):
heapify(arr, n, i)
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
def heapify(arr, n, i):
largest = i
left_child = 2 * i + 1
right_child = 2 * i + 2
if left_child < n and arr[left_child] > arr[largest]:
largest = left_child
if right_child < n and arr[right_child] > arr[largest]:
largest = right_child
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
arr = [64, 34, 25, 12, 22, 11, 90]
heap_sort(arr)
print("Sorted array is:", arr)
```
时间复杂度为O(nlogn)。