《啊哈算法》第一章--排序

**《啊哈算法》第一章--排序**

在计算机科学中，排序是指将数据按某种顺序排列的过程。它是许多算法和程序设计中的一个基本组成部分。在本章，我们将介绍各种常见的排序算法及其实现。

###1.1 算法复杂度首先，让我们了解一下算法复杂度这个概念。算法复杂度是指算法执行所需时间或空间的量度，它通常用来衡量算法的效率。常见的复杂度表示法包括：

* O(1)：恒定时间复杂度，表示算法在任何输入下都需要相同的时间。
* O(log n)：对数时间复杂度，表示算法执行所需时间与输入大小成正比，但增长速度非常缓慢。
* O(n)：线性时间复杂度，表示算法执行所需时间与输入大小成直接比例。
* O(n log n)：线性对数时间复杂度，表示算法执行所需时间与输入大小成直接比例，并且增长速度非常快。
* O(n^2)：平方时间复杂度，表示算法执行所需时间与输入大小的平方成正比。

###1.2 冒泡排序冒泡排序是一种简单的排序算法，它通过反复地遍历列表来将元素按顺序排列。具体来说，每次遍历都会比较相邻的两个元素，如果它们的顺序不正确，则交换它们。这个过程持续直到整个列表被排序。

def bubble_sort(arr):
 n = len(arr)
 for i in range(n-1):
 # Create a flag that will allow the function to terminate early if there's nothing left to sort already_sorted = True # Start looking at each item of the list one by one, comparing it with its adjacent value for j in range(n-i-1):
 # If we come across an element that is greater than the next one, then swap them if arr[j] > arr[j+1]:
 # Swap values arr[j], arr[j+1] = arr[j+1], arr[j]
 # Since we had to swap two elements,
 # we need to iterate over the list again.
 already_sorted = False # If there were no swaps during the last iteration, the list is already sorted, and we can terminate if already_sorted:
 break return arr# Test the functionarr = [64,34,25,12,22,11,90]
print("Original array:", arr)
print("Sorted array:", bubble_sort(arr))

###1.3选择排序选择排序是一种简单的排序算法，它通过反复地遍历列表来将元素按顺序排列。具体来说，每次遍历都会找到列表中最小或最大元素，并将其放在列表的起始位置。

def selection_sort(arr):
 n = len(arr)
 for i in range(n-1):
 # Find the minimum element in the unsorted part of the list min_idx = i # Look through the unsorted part of the list and find the smallest element for j in range(i+1, n):
 if arr[j] < arr[min_idx]:
 min_idx = j # Swap the found minimum element with the first element that is larger than it arr[i], arr[min_idx] = arr[min_idx], arr[i]
 return arr# Test the functionarr = [64,34,25,12,22,11,90]
print("Original array:", arr)
print("Sorted array:", selection_sort(arr))

###1.4 插入排序插入排序是一种简单的排序算法，它通过反复地遍历列表来将元素按顺序排列。具体来说，每次遍历都会找到列表中一个元素的正确位置，并将其放在该位置。

def insertion_sort(arr):
 n = len(arr)
 for i in range(1, n):
 key = arr[i]
 # Move elements of arr[0..i-1], that are greater than key,
 # to one position ahead of their current position j = i -1 while j >=0 and key < arr[j]:
 arr[j +1] = arr[j]
 j -=1 arr[j +1] = key return arr# Test the functionarr = [64,34,25,12,22,11,90]
print("Original array:", arr)
print("Sorted array:", insertion_sort(arr))

###1.5 归并排序归并排序是一种高效的排序算法，它通过反复地将列表分成两半来将元素按顺序排列。具体来说，每次分割都会找到两个子列表中最小或最大元素，并将其放在父列表的起始位置。

def merge_sort(arr):
 if len(arr) <=1:
 return arr mid = len(arr) //2 left_half = arr[:mid]
 right_half = arr[mid:]
 # Recursively sort both halves left_half = merge_sort(left_half)
 right_half = merge_sort(right_half)
 # Merge the sorted halves return merge(left_half, right_half)

def merge(left, right):
 merged = []
 left_index =0 right_index =0 while left_index < len(left) and right_index < len(right):
 if left[left_index] <= right[right_index]:
 merged.append(left[left_index])
 left_index +=1 else:
 merged.append(right[right_index])
 right_index +=1 # Append the remaining elements, if any merged.extend(left[left_index:])
 merged.extend(right[right_index:])
 return merged# Test the functionarr = [64,34,25,12,22,11,90]
print("Original array:", arr)
print("Sorted array:", merge_sort(arr))

###1.6 快速排序快速排序是一种高效的排序算法，它通过反复地将列表分成两半来将元素按顺序排列。具体来说，每次分割都会找到一个元素的正确位置，并将其放在父列表的起始位置。

def quick_sort(arr):
 if len(arr) <=1:
 return arr pivot = arr[len(arr) //2]
 # Create lists for elements less than and greater than the pivot left = [x for x in arr if x < pivot]
 middle = [x for x in arr if x == pivot]
 right = [x for x in arr if x > pivot]
 # Recursively sort the sublists return quick_sort(left) + middle + quick_sort(right)

# Test the functionarr = [64,34,25,12,22,11,90]
print("Original array:", arr)
print("Sorted array:", quick_sort(arr))

### 总结在本章，我们介绍了各种常见的排序算法及其实现。这些算法包括冒泡排序、选择排序、插入排序、归并排序和快速排序。每个算法都有其特点和优缺点，选择哪种算法取决于具体的应用场景和需求。

### 参考* [Wikipedia: Sorting algorithm]( />* [GeeksforGeeks: Sorting algorithms]( />* [Stack Overflow: Sorting algorithms](