当前位置： 首页 > news >正文

算法基础之八大排序

news 2025/6/24 0:01:26

文章目录

    • 概要
    • 1. 冒泡排序（Bubble Sort）
    • 2. 选择排序（Selection Sort）
    • 3. 插入排序（Insertion Sort）
    • 4. 希尔排序（Shell Sort）
    • 5. 归并排序（Merge Sort）
    • 6. 快速排序（Quick Sort）
    • 7. 堆排序（Heap Sort）
    • 8. 计数排序（Counting Sort）
  • 小结

概要

排序算法是编程中最基础也是最重要的算法之一。通过学习和理解不同的排序算法，我们可以在实际开发中选择合适的算法来解决问题。本文将介绍八大常用排序算法，并分别用 Python、C++ 和 Java 三种语言实现。

时间复杂度

1. 冒泡排序（Bubble Sort）

算法描述: 冒泡排序是一种简单的排序算法，通过不断交换相邻元素，使得较大的元素“浮”到数组的末尾。

时间复杂度

  • 最佳情况：O(n)
  • 平均情况：O(n²)
  • 最坏情况：O(n²)

空间复杂度： O(1)
稳定性： 稳定

实现步骤

  1. 比较相邻元素，前大则交换

  2. 对每一对相邻元素重复操作

  3. 每次遍历后范围缩小1

  4. 重复直到无交换发生

代码实现

python版本

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

C++版本

void bubbleSort(int arr[], int n) {for (int i = 0; i < n-1; i++) {for (int j = 0; j < n-i-1; j++) {if (arr[j] > arr[j+1]) {// Swap elementsint temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}
}

Java版本

public class BubbleSort {public static void bubbleSort(int[] arr) {int n = arr.length;for (int i = 0; i < n-1; i++) {for (int j = 0; j < n-i-1; j++) {if (arr[j] > arr[j+1]) {// Swap elementsint temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}}
}

2. 选择排序（Selection Sort）

算法描述： 选择排序通过分为有序区和无序区，逐步从无序区中找到最小元素，放到有序区的末尾。

时间复杂度：

  • 最佳情况：O(n²)
  • 平均情况：O(n²)
  • 最坏情况：O(n²)

空间复杂度： O(1)

稳定性： 不稳定

代码实现
python版本

# Python
def bubble_sort(arr):n = len(arr)for i in range(n-1):swapped = Falsefor j in range(n-1-i):if arr[j] > arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j]swapped = Trueif not swapped:breakreturn arr

C++版本

// C++
void bubbleSort(int arr[], int n) {for (int i = 0; i < n-1; ++i) {bool swapped = false;for (int j = 0; j < n-1-i; ++j) {if (arr[j] > arr[j+1]) {swap(arr[j], arr[j+1]);swapped = true;}}if (!swapped) break;}
}

Java版本

// Java
public static void bubbleSort(int[] arr) {int n = arr.length;for (int i = 0; i < n-1; i++) {boolean swapped = false;for (int j = 0; j < n-1-i; j++) {if (arr[j] > arr[j+1]) {int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;swapped = true;}}if (!swapped) break;}
}

3. 插入排序（Insertion Sort）

算法思想： 将未排序元素逐个插入已排序序列的合适位置

时间复杂度：

  • 平均：O(n²)

  • 最坏：O(n²)

  • 最好：O(n)

稳定性： 稳定

python版本

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

C++版本

// C++
void insertionSort(int arr[], int n) {for (int i = 1; i < n; ++i) {int key = arr[i];int j = i-1;while (j >= 0 && arr[j] > key) {arr[j+1] = arr[j];j--;}arr[j+1] = key;}
}

Java版本

// Java
public static void insertionSort(int[] arr) {for (int i = 1; i < arr.length; ++i) {int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key) {arr[j+1] = arr[j];j--;}arr[j+1] = key;}
}

4. 希尔排序（Shell Sort）

算法思想： 改进的插入排序，通过间隔分组进行预处理
时间复杂度： O(n log n) ~ O(n²)
稳定性： 不稳定

python版本

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

C++版本

// C++
void shellSort(int arr[], int n) {for (int gap = n/2; gap > 0; gap /= 2) {for (int i = gap; i < n; ++i) {int temp = arr[i];int j;for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)arr[j] = arr[j - gap];arr[j] = temp;}}
}

Java版本

// Java
public static void shellSort(int[] arr) {int n = arr.length;for (int gap = n/2; gap > 0; gap /= 2) {for (int i = gap; i < n; i++) {int temp = arr[i];int j;for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)arr[j] = arr[j - gap];arr[j] = temp;}}
}

5. 归并排序（Merge Sort）

算法思想： 分治法，递归拆分后合并有序子序列
时间复杂度： O(n log n)
稳定性： 稳定

python版本

# Python
def merge_sort(arr):if len(arr) > 1:mid = len(arr)//2L = arr[:mid]R = arr[mid:]merge_sort(L)merge_sort(R)i = j = k = 0while i < len(L) and j < len(R):if L[i] < R[j]:arr[k] = L[i]i += 1else:arr[k] = R[j]j += 1k += 1while i < len(L):arr[k] = L[i]i += 1k += 1while j < len(R):arr[k] = R[j]j += 1k += 1return arr

C++版本：

// C++
void merge(int arr[], int l, int m, int r) {int n1 = m - l + 1;int n2 = r - m;int L[n1], R[n2];for (int i = 0; i < n1; i++)L[i] = arr[l + i];for (int j = 0; j < n2; j++)R[j] = arr[m + 1 + j];int i = 0, j = 0, k = l;while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];i++;} else {arr[k] = R[j];j++;}k++;}while (i < n1) arr[k++] = L[i++];while (j < n2) arr[k++] = R[j++];
}void mergeSort(int arr[], int l, int r) {if (l < r) {int m = l + (r - l)/2;mergeSort(arr, l, m);mergeSort(arr, m+1, r);merge(arr, l, m, r);}
}

Java版本

// Java
public static void mergeSort(int[] arr, int l, int r) {if (l < r) {int m = (l + r) / 2;mergeSort(arr, l, m);mergeSort(arr, m + 1, r);int[] L = Arrays.copyOfRange(arr, l, m + 1);int[] R = Arrays.copyOfRange(arr, m + 1, r + 1);int i = 0, j = 0, k = l;while (i < L.length && j < R.length) {if (L[i] <= R[j]) arr[k++] = L[i++];else arr[k++] = R[j++];}while (i < L.length) arr[k++] = L[i++];while (j < R.length) arr[k++] = R[j++];}
}

6. 快速排序（Quick Sort）

算法思想： 分治法，选取基准元素进行分区排序
时间复杂度：

  • 平均：O(n log n)

  • 最坏：O(n²)

稳定性： 不稳定

python版本

在这里插入代码片# Python
def quick_sort(arr):if len(arr) <= 1:return arrpivot = 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)

C++版本：

// C++
int partition(int arr[], int low, int high) {int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;swap(arr[i], arr[j]);}}swap(arr[i+1], arr[high]);return i+1;
}void quickSort(int arr[], int low, int high) {if (low < high) {int pi = partition(arr, low, high);quickSort(arr, low, pi-1);quickSort(arr, pi+1, high);}
}

Java版本

// Java
public static void quickSort(int[] arr, int low, int high) {if (low < high) {int pi = partition(arr, low, high);quickSort(arr, low, pi-1);quickSort(arr, pi+1, high);}
}private static int partition(int[] arr, int low, int high) {int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}int temp = arr[i+1];arr[i+1] = arr[high];arr[high] = temp;return i+1;
}

7. 堆排序（Heap Sort）

算法思想： 利用堆数据结构进行选择排序
时间复杂度： O(n log n)
稳定性： 不稳定

python版本

# Python
def heapify(arr, n, i):largest = il = 2 * i + 1r = 2 * i + 2if l < n and arr[l] > arr[largest]:largest = lif r < n and arr[r] > arr[largest]:largest = rif 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[i], arr[0] = arr[0], arr[i]heapify(arr, i, 0)return arr

C++版本：

// C++
void heapify(int arr[], int n, int i) {int largest = i;int l = 2*i + 1;int r = 2*i + 2;if (l < n && arr[l] > arr[largest])largest = l;if (r < n && arr[r] > arr[largest])largest = r;if (largest != i) {swap(arr[i], arr[largest]);heapify(arr, n, largest);}
}void heapSort(int arr[], int n) {for (int i = n/2 - 1; i >= 0; i--)heapify(arr, n, i);for (int i = n-1; i > 0; i--) {swap(arr[0], arr[i]);heapify(arr, i, 0);}
}

Java版本

// Java
public static void heapSort(int[] arr) {int n = arr.length;for (int i = n/2 - 1; i >= 0; i--)heapify(arr, n, i);for (int i = n-1; i > 0; i--) {int temp = arr[0];arr[0] = arr[i];arr[i] = temp;heapify(arr, i, 0);}
}private static void heapify(int[] arr, int n, int i) {int largest = i;int l = 2*i + 1;int r = 2*i + 2;if (l < n && arr[l] > arr[largest]) largest = l;if (r < n && arr[r] > arr[largest]) largest = r;if (largest != i) {int swap = arr[i];arr[i] = arr[largest];arr[largest] = swap;heapify(arr, n, largest);}
}

8. 计数排序（Counting Sort）

适用场景： 整数排序且值范围不大
时间复杂度： O(n + k)
稳定性： 稳定

python版本

# Python
def counting_sort(arr):max_val = max(arr)count = [0] * (max_val + 1)for num in arr:count[num] += 1idx = 0for i in range(len(count)):while count[i] > 0:arr[idx] = iidx += 1count[i] -= 1return arr

C++版本：

// C++
void countingSort(int arr[], int n) {int maxVal = *max_element(arr, arr + n);int count[maxVal + 1] = {0};for (int i = 0; i < n; i++)count[arr[i]]++;int idx = 0;for (int i = 0; i <= maxVal; i++) {while (count[i]-- > 0) {arr[idx++] = i;}}
}

Java版本

// Java
public static void countingSort(int[] arr) {int maxVal = Arrays.stream(arr).max().getAsInt();int[] count = new int[maxVal + 1];for (int num : arr) count[num]++;int idx = 0;for (int i = 0; i <= maxVal; i++) {while (count[i]-- > 0) {arr[idx++] = i;}}
}

小结

排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性
冒泡排序O(n²)O(n²)O(1)稳定
选择排序O(n²)O(n²)O(1)不稳定
插入排序O(n²)O(n²)O(1)稳定
希尔排序O(n log n)O(n²)O(1)不稳定
归并排序O(n log n)O(n log n)O(n)稳定
快速排序O(n log n)O(n²)O(log n)不稳定
堆排序O(n log n)O(n log n)O(1)不稳定
计数排序O(n + k)O(n + k)O(k)稳定

注：k为计数排序的值域范围

应用场景建议：

  • 小规模数据：插入排序

  • 通用高效：快速排序

  • 内存敏感：堆排序

  • 稳定需求：归并排序

  • 整数排序：计数排序

http://www.lryc.cn/news/533282.html

相关文章：

  • 使用TensorFlow和Keras构建卷积神经网络：图像分类实战指南
  • 音频进阶学习十一——离散傅里叶级数DFS
  • 20.＜Spring图书管理系统①（登录+添加图书）＞
  • 关于图像锐化的一份介绍
  • Django开发入门 – 0.Django基本介绍
  • 多智能体协作架构模式：驱动传统公司向AI智能公司转型
  • CentOS服务器部署Docker+Jenkins持续集成环境
  • 【prompt实战】AI +OCR技术结合ChatGPT能力项目实践（BOL提单识别提取专家）
  • 【Android】Android开发应用如何开启任务栏消息通知
  • 上传文件报错：the request was rejected because no multipart boundary was found
  • 大模型—Dify本地化部署实战
  • 功能架构元模型
  • 常用工具类——Collections集合框架
  • e2studio开发RA2E1(9)----定时器GPT配置输入捕获
  • 25/2/7 ＜机器人基础＞雅可比矩阵计算 雅可比伪逆
  • 网络爬虫js逆向之异步栈跟栈案例
  • 使用Ollama本地部署deepseek
  • Rust错误处理：从灭火器到核按钮的生存指南
  • Golang：Go 1.23 版本新特性介绍
  • 电脑运行黑屏是什么原因？原因及解决方法
  • redis之AOF持久化过程
  • Elasticsearch：向量搜索的快速介绍
  • Docker在安装时遇到的问题（第一部分）
  • 使用 OpenGL ES 在 iOS 上渲染一个四边形：从基础到实现
  • Spring Boot 2 快速教程：WebFlux处理流程（五）
  • Vue 鼠标事件合集，关于鼠标右键的处理方法（改写鼠标右键方法、自定义鼠标右键）
  • 两种交换排序算法--冒泡，快速
  • 语音交友app系统源码功能及技术研发流程剖析
  • 零基础Vue入门7——状态管理Pinia
  • Bash (Bourne-Again Shell)、Zsh (Z Shell)