数据结构七种排序算法

以下是七种常见的排序算法及其基本原理：

1. 冒泡排序（Bubble Sort）：
- 基本原理：比较相邻的两个元素，如果顺序错误则交换位置，每次循环将最大的元素移动到末尾。
- 代码示例：

   def bubble_sort(arr):
       n = len(arr)
       for i in range(n-1):
           for j in range(n-i-1):
               if arr[j] > arr[j+1]:
                   arr[j], arr[j+1] = arr[j+1], arr[j]
       return arr

2. 选择排序（Selection Sort）：
- 基本原理：每次从未排序的部分选择最小的元素，放到已排序部分的末尾。
- 代码示例：

   def selection_sort(arr):
       n = len(arr)
       for i in range(n-1):
           min_idx = i
           for j in range(i+1, n):
               if arr[j] < arr[min_idx]:
                   min_idx = j
           arr[i], arr[min_idx] = arr[min_idx], arr[i]
       return arr

3. 插入排序（Insertion Sort）：
- 基本原理：将未排序的元素逐个插入到已排序部分的正确位置。
- 代码示例：

   def insertion_sort(arr):
       n = len(arr)
       for i in range(1, n):
           key = arr[i]
           j = i - 1
           while j >= 0 and arr[j] > key:
               arr[j+1] = arr[j]
               j -= 1
           arr[j+1] = key
       return arr

4. 希尔排序（Shell Sort）：
- 基本原理：将待排序的元素按照一定的间隔分组，对每组使用插入排序，逐渐缩小间隔直至为1。
- 代码示例：

   def shell_sort(arr):
       n = len(arr)
       gap = n // 2
       while gap > 0:
           for i in range(gap, n):
               temp = arr[i]
               j = i
               while j >= gap and arr[j-gap] > temp:
                   arr[j] = arr[j-gap]
                   j -= gap
               arr[j] = temp
           gap //= 2
       return arr

5. 归并排序（Merge Sort）：
- 基本原理：将待排序的序列递归地分成两半，对每半进行排序，然后将两个有序的半合并成一个有序序列。
- 代码示例：

   def merge_sort(arr):
       if len(arr) <= 1:
           return arr
       mid = len(arr) // 2
       left = merge_sort(arr[:mid])
       right = merge_sort(arr[mid:])
       return merge(left, right)

   def merge(left, right):
       result = []
       i = j = 0
       while i < len(left) and j < len(right):
           if left[i] < right[j]:
               result.append(left[i])
               i += 1
           else:
               result.append(right[j])
               j += 1
       result.extend(left[i:])
       result.extend(right[j:])
       return result

6. 快速排序（Quick Sort）：
- 基本原理：选择一个基准元素，将小于基准的元素放在左边，大于基准的元素放在右边，然后递归地对左右两部分进行快速排序。
- 代码示例：

   def quick_sort(arr):
       if len(arr) <= 1:
           return arr
       pivot = arr[len(arr) // 2]
       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]
       return quick_sort(left) + middle + quick_sort(right)

7. 堆排序（Heap Sort）：
- 基本原理：将待排序的序列构建成一个大顶堆，然后依次取出堆顶元素并调整堆，直到堆为空。
- 代码示例：

   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)
       return arr

   def heapify(arr, n, i):
       largest = i
       left = 2 * i + 1
       right = 2 * i + 2
       if left < n and arr[left] > arr[largest]:
           largest = left
       if right < n and arr[right] > arr[largest]:
           largest = right
       if largest != i:
           arr[i], arr[largest] = arr[largest], arr[i]
           heapify(arr, n, largest)