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

深入解析常见排序算法及其 C# 实现

ds 2025/5/1 17:20:15

在程序设计中，排序是一个非常常见且重要的操作。掌握各种排序算法对于提高算法的效率、解决实际问题非常有帮助。本文将详细介绍常见的排序算法，包括 冒泡排序、选择排序、插入排序、归并排序、快速排序、计数排序 和 基数排序，并提供 C# 语言的实现代码。

1. 冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法，通过反复比较相邻元素并交换它们的位置，直到整个数组排好序。

原理：

  • 比较数组中的每对相邻元素，如果它们的顺序错误，就交换它们的位置。

  • 重复这一过程，直到没有更多的交换发生，此时数组已排好序。

时间复杂度：

  • 最坏情况：O(n²)

  • 最好情况（数组已排序）：O(n)

C# 实现：
using System;class Program
{static void BubbleSort(int[] arr){int n = arr.Length;for (int i = 0; i < n - 1; i++){bool swapped = false;for (int j = 0; j < n - i - 1; 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;  // 如果没有交换，说明数组已经排序好了}}static void Main(){int[] arr = { 64, 34, 25, 12, 22, 11, 90 };BubbleSort(arr);Console.WriteLine("Sorted array:");foreach (var item in arr){Console.Write(item + " ");}}
}

2. 选择排序（Selection Sort）

选择排序是一种简单的排序算法，通过每次选择未排序部分的最小（或最大）元素并将其放到已排序部分的末尾。

原理：

  • 从未排序部分中选择最小的元素，将其与当前未排序部分的第一个元素交换。

  • 重复此过程，直到整个数组排序完成。

时间复杂度：

  • 最坏情况：O(n²)

  • 最好情况：O(n²)

C# 实现：
using System;class Program
{static void SelectionSort(int[] arr){int n = arr.Length;for (int i = 0; i < n - 1; i++){int minIndex = i;for (int j = i + 1; j < n; j++){if (arr[j] < arr[minIndex])  // 找到未排序部分的最小值{minIndex = j;}}if (minIndex != i){// 交换最小值和当前元素int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}}}static void Main(){int[] arr = { 64, 25, 12, 22, 11 };SelectionSort(arr);Console.WriteLine("Sorted array:");foreach (var item in arr){Console.Write(item + " ");}}
}

3. 插入排序（Insertion Sort）

插入排序通过将每个元素插入到已排序部分的适当位置，逐步构建有序序列。

原理：

  • 从数组的第二个元素开始，依次将每个元素插入到前面已排序部分的适当位置。

  • 重复此过程，直到整个数组排好序。

时间复杂度：

  • 最坏情况：O(n²)

  • 最好情况（数组已排序）：O(n)

C# 实现：
using System;class Program
{static void InsertionSort(int[] arr){int n = arr.Length;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;  // 插入当前元素到合适的位置}}static void Main(){int[] arr = { 64, 34, 25, 12, 22, 11, 90 };InsertionSort(arr);Console.WriteLine("Sorted array:");foreach (var item in arr){Console.Write(item + " ");}}
}

4. 归并排序（Merge Sort）

归并排序是一种典型的分治算法，通过递归将数组分割成两部分，分别排序后再合并成一个有序数组。

原理：

  • 递归地将数组分成两部分，直到每部分只有一个元素。

  • 然后合并这些部分，最终得到有序数组。

时间复杂度：

  • 最坏情况：O(n log n)

  • 最好情况：O(n log n)

C# 实现：
using System;class Program
{static void Merge(int[] arr, int left, int right){if (left < right){int mid = (left + right) / 2;Merge(arr, left, mid);  // 排序左半部分Merge(arr, mid + 1, right);  // 排序右半部分MergeArrays(arr, left, mid, right);  // 合并两部分}}static void MergeArrays(int[] arr, int left, int mid, int right){int n1 = mid - left + 1;int n2 = right - mid;int[] leftArr = new int[n1];int[] rightArr = new int[n2];for (int i = 0; i < n1; i++) leftArr[i] = arr[left + i];for (int i = 0; i < n2; i++) rightArr[i] = arr[mid + 1 + i];int k = left, i = 0, j = 0;while (i < n1 && j < n2){if (leftArr[i] <= rightArr[j]){arr[k] = leftArr[i];i++;}else{arr[k] = rightArr[j];j++;}k++;}while (i < n1){arr[k] = leftArr[i];i++;k++;}while (j < n2){arr[k] = rightArr[j];j++;k++;}}static void Main(){int[] arr = { 64, 34, 25, 12, 22, 11, 90 };Merge(arr, 0, arr.Length - 1);Console.WriteLine("Sorted array:");foreach (var item in arr){Console.Write(item + " ");}}
}

5. 快速排序（Quick Sort）

快速排序通过选择一个基准元素，并将数组分成两部分，分别排序后再合并。

原理：

  • 选择一个基准元素，将数组分为比基准元素小的部分和比基准元素大的部分。

  • 递归地排序这两部分。

时间复杂度：

  • 最坏情况：O(n²)

  • 最好和平均情况：O(n log n)

C# 实现：
using System;class Program
{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);  // 排序右部分}}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 temp1 = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp1;return i + 1;}static void Main(){int[] arr = { 64, 34, 25, 12, 22, 11, 90 };QuickSort(arr, 0, arr.Length - 1);Console.WriteLine("Sorted array:");foreach (var item in arr){Console.Write(item + " ");}}
}

6. 计数排序（Counting Sort）

计数排序是一种非比较排序算法，适用于元素值

较小且数据范围有限的场景。

原理：

  • 通过统计数组中每个元素的出现次数，来确定每个元素在排序后的数组中的位置。

时间复杂度：

  • O(n + k)，其中 n 是数组的长度，k 是元素值的范围。

C# 实现：
using System;class Program
{static void CountingSort(int[] arr){int max = arr[0];foreach (var num in arr) if (num > max) max = num;int[] count = new int[max + 1];foreach (var num in arr) count[num]++;int index = 0;for (int i = 0; i <= max; i++){while (count[i] > 0){arr[index++] = i;count[i]--;}}}static void Main(){int[] arr = { 4, 2, 2, 8, 3, 3, 1 };CountingSort(arr);Console.WriteLine("Sorted array:");foreach (var item in arr){Console.Write(item + " ");}}
}

7. 基数排序（Radix Sort）

基数排序是一种非比较的排序算法，通过逐位排序来完成排序操作。

原理：

  • 从最低位开始，按位进行排序，逐步向高位排序，直到所有位数排序完成。

时间复杂度：

  • O(nk)，其中 n 是元素数量，k 是元素的位数。

C# 实现：
using System;class Program
{static void CountingSortForRadix(int[] arr, int exp){int n = arr.Length;int[] output = new int[n];int[] count = new int[10];for (int i = 0; i < n; i++){count[(arr[i] / exp) % 10]++;}for (int i = 1; i < 10; i++){count[i] += count[i - 1];}for (int i = n - 1; i >= 0; i--){output[count[(arr[i] / exp) % 10] - 1] = arr[i];count[(arr[i] / exp) % 10]--;}for (int i = 0; i < n; i++){arr[i] = output[i];}}static void RadixSort(int[] arr){int max = arr[0];foreach (var num in arr) if (num > max) max = num;for (int exp = 1; max / exp > 0; exp *= 10){CountingSortForRadix(arr, exp);}}static void Main(){int[] arr = { 170, 45, 75, 90, 802, 24, 2, 66 };RadixSort(arr);Console.WriteLine("Sorted array:");foreach (var item in arr){Console.Write(item + " ");}}
}

总结：

每种排序算法都有其适用的场景。冒泡排序、选择排序和插入排序适用于小规模数据，时间复杂度为 O(n²)。归并排序、快速排序和基数排序适用于大规模数据，时间复杂度为 O(n log n) 或 O(nk)。计数排序适用于数据范围较小的情况。理解这些算法的原理并掌握其实现将帮助你在实际开发中解决不同的排序问题。

http://www.xdnf.cn/news/3139.html

相关文章：

  • 系统思考培训助力总经理
  • AI预测3D新模型百十个定位预测+胆码预测+去和尾2025年4月29日第67弹
  • RISE with SAP 的合同及许可解析
  • 【电子对抗训练革命】新一代便携式雷达模拟器技术解密
  • Spring事务开发经验 回滚和不回滚？
  • ADS1299模拟前端(AFE)代替芯片——LHE7909
  • C事件驱动网络库​​libevent的http详解
  • Java实现使用EasyExcel按模板导出文件
  • 【Unity】使用LitJson保存和读取数据的例子
  • SQL注入
  • Leetcode 3533. Concatenated Divisibility
  • 【C到Java的深度跃迁：从指针到对象，从过程到生态】第四模块·Java特性专精 —— 第十七章 IO流：超越FILE*的维度战争
  • SpringBoot之SpringAl实现AI应用-快速搭建
  • LeetCode -160.相交链表
  • “假读“操作在I2C接收流程中的原因
  • DECAP CELL
  • Qt入门——什么是Qt?
  • 【Linux】第十三章 访问Linux文件系统
  • React：封装一个编辑文章的组件
  • python如何流模式输出
  • Missashe考研日记-day30
  • JR6001语音模块详解（STM32）
  • 1.3 点云数据获取方式——ToF相机
  • Linux电源管理(3)_关机和重启的过程
  • 【今日三题】小红的ABC(找规律) / 不相邻取数(多状态dp) / 空调遥控(排序+二分/滑动窗口)
  • 面向人工智能、量子科技、人形机器人等产业，山东启动制造业创新中心培育认定
  • Android Studio 中实现方法和参数显示一行
  • Git 多账号切换及全局用户名设置不生效问,GIT进行上传无权限问题
  • 科研入门规划
  • computed计算值为什么还可以依赖另外一个computed计算值？