排序算法汇总

**排序算法汇总**

排序算法是一类用于对数据进行排序的算法。排序是计算机科学中一个非常重要的概念，几乎所有的应用程序都需要排序功能。下面我们将介绍一些常见的排序算法及其实现。

###1. 冒泡排序冒泡排序是一种简单的排序算法，它通过反复地遍历列表来进行排序。

**代码示例**

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# 测试arr = [64,34,25,12,22,11,90]
print(bubble_sort(arr)) # 输出: [11,12,22,25,34,64,90]

**时间复杂度**: O(n^2)

###2.选择排序选择排序是一种简单的排序算法，它通过找到列表中最小或最大元素来进行排序。

**代码示例**

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# 测试arr = [64,34,25,12,22,11,90]
print(selection_sort(arr)) # 输出: [11,12,22,25,34,64,90]

**时间复杂度**: O(n^2)

###3. 插入排序插入排序是一种简单的排序算法，它通过将元素插入到已排序列表中来进行排序。

**代码示例**

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# 测试arr = [64,34,25,12,22,11,90]
print(insertion_sort(arr)) # 输出: [11,12,22,25,34,64,90]

**时间复杂度**: O(n^2)

###4. 归并排序归并排序是一种高效的排序算法，它通过将列表分成小块，然后合并这些块来进行排序。

**代码示例**

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 = []
 while left and right:
 if left[0] < right[0]:
 result.append(left.pop(0))
 else:
 result.append(right.pop(0))
 result.extend(left)
 result.extend(right)
 return result# 测试arr = [64,34,25,12,22,11,90]
print(merge_sort(arr)) # 输出: [11,12,22,25,34,64,90]

**时间复杂度**: O(n log n)

###5. 快速排序快速排序是一种高效的排序算法，它通过选择一个元素作为基准点，然后将列表分成两部分来进行排序。

**代码示例**

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)

# 测试arr = [64,34,25,12,22,11,90]
print(quick_sort(arr)) # 输出: [11,12,22,25,34,64,90]

**时间复杂度**: O(n log n)

###6. 希尔排序希尔排序是一种改进的插入排序算法，它通过将列表分成小块，然后使用插入排序来进行排序。

**代码示例**

def shell_sort(arr):
 gap = len(arr) //2 while gap >0:
 for i in range(gap, len(arr)):
 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# 测试arr = [64,34,25,12,22,11,90]
print(shell_sort(arr)) # 输出: [11,12,22,25,34,64,90]

**时间复杂度**: O(n log n)

###7. 堆排序堆排序是一种高效的排序算法，它通过将列表构建成一个最大堆，然后逐步地将元素取出并放入已排序列表中来进行排序。

**代码示例**

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)

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[0], arr[i] = arr[i], arr[0]
 heapify(arr, i,0)
 return arr# 测试arr = [64,34,25,12,22,11,90]
print(heap_sort(arr)) # 输出: [11,12,22,25,34,64,90]

**时间复杂度**: O(n log n)

### 总结上述是常见的排序算法及其实现。每种算法都有其特点和优缺点。选择哪种算法取决于具体的需求和场景。

* 冒泡排序、选择排序和插入排序都是简单的排序算法，但它们的时间复杂度较高。
* 归并排序是一种高效的排序算法，它通过将列表分成小块然后合并这些块来进行排序。它的时间复杂度是 O(n log n)。
* 快速排序是一种高效的排序算法，它通过选择一个元素作为基准点，然后将列表分成两部分来进行排序。它的时间复杂度也是 O(n log n)。
* 希尔排序是一种改进的插入排序算法，它通过将列表分成小块然后使用插入排序来进行排序。它的时间复杂度是 O(n log n)。
* 堆排序是一种高效的排序算法，它通过将列表构建成一个最大堆然后逐步地将元素取出并放入已排序列表中来进行排序。它的时间复杂度也是 O(n log n)。

每种算法都有其特点和优缺点，选择哪种算法取决于具体的需求和场景。