C#经典十大排序算法（完结）（代号TOG）

C#冒泡排序算法

简介

冒泡排序算法是一种基础的排序算法，它的实现原理比较简单。核心思想是通过相邻元素的比较和交换来将最大（或最小）的元素逐步"冒泡"到数列的末尾。

详细文章描述

https://mp.weixin.qq.com/s/z_LPZ6QUFNJcwaEw_H5qbQ

代码实现

/// <summary> /// 递归方式实现冒泡排序 ///</summary> /// <param name="arr">arr</param> /// <param name="arrLength">arrLength</param> public static void RecursiveBubbleSort(int[] arr, int arrLength) { if (arrLength == 1) return; for (int i = 0; i < arrLength - 1; i ) { if (arr[i] > arr[i 1]) { //交换arr[i]和arr[i 1]的值 int temp = arr[i]; arr[i] = arr[i 1]; arr[i 1] = temp; } } RecursiveBubbleSort(arr, arrLength - 1); } public static void RecursiveBubbleSortRun { int arr = { 1, 8, 9, 5, 6, 2, 3, 4, 7 }; int arrLength = arr.Length; RecursiveBubbleSort(arr, arrLength); Console.WriteLine("排序后结果：" string.Join(", ", arr)); }

C#选择排序算法

简介

选择排序算法的基本思想是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。

详细文章描述

https://mp.weixin.qq.com/s/B1QdqyP8HQgOv8tlSujtog

代码实现

/// <summary> /// 选择排序算法 ///</summary> public static void SelectionSortAlgorithmMain { int array = { 64, 25, 12, 22, 11, 99, 3, 100 }; Console.WriteLine("原始数组: "); PrintArray(array); SelectionSortAlgorithm(array); Console.WriteLine("排序后的数组: "); PrintArray(array); } static void SelectionSortAlgorithm(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; } } // 将最小元素与未排序部分的第一个元素交换位置 int temp = arr[minIndex]; arr[minIndex] = arr[i]; arr[i] = temp; } } static void PrintArray(int[] arr) { int n = arr.Length; for (int i = 0; i < n; i) { Console.Write(arr[i] " "); } Console.WriteLine; }

C#插入排序算法

简介

插入排序算法是一种简单、直观的排序算法，其原理是将一个待排序的元素逐个地插入到已经排好序的部分中。

详细文章描述

https://mp.weixin.qq.com/s/YEregZ_GOGgEltGUJadycw

代码实现

public static void InsertionSort(int[] array) { int arrayLength = array.Length;//数组长度（时间复杂度为O(n^2)） for (int i = 1; i < arrayLength; i) { //定义临时变量 int temp = array[i]; int j = i - 1; while (j >= 0 && array[j] > temp) { array[j 1] = array[j]; j--; } array[j 1] = temp; } } public static void InsertionSortRun { int array = { 26, 15, 5, 3, 38, 36, 44, 27, 47, 2, 46, 4, 50, 19, 48 }; Console.WriteLine("排序前:" string.Join(", ", array)); InsertionSort(array); Console.WriteLine("排序后:" string.Join(", ", array)); }

C#希尔排序算法

简介

希尔排序简单的来说就是一种改进的插入排序算法，它通过将待排序的元素分成若干个子序列，然后对每个子序列进行插入排序，最终逐步缩小子序列的间隔，直到整个序列变得有序。希尔排序的主要思想是通过插入排序的优势，减小逆序对的距离，从而提高排序效率。

详细文章描述

https://mp.weixin.qq.com/s/_t9QVuj_rLcNomyv7LcGMA

代码实现

public static void ShellSort(int[] array) { int arrLength = array.Length; // 初始化增量（初始间隔）为数组长度的一半 int gap = arrLength / 2; // 不断缩小增量，直到增量为1 while (gap > 0) { // 对每个子序列进行插入排序 for (int i = gap; i < arrLength; i ) { int temp = array[i]; int j = i; // 在子序列内部进行插入排序 while (j >= gap && array[j - gap] > temp) { array[j] = array[j - gap]; j -= gap; } array[j] = temp; } // 缩小增量 gap /= 2; } } public static void ShellSortRun { int array = { 19, 20, 22, 32, 34, 50, 99, 49, 1, 11, 11, 55, 35, 93, 96, 71, 70, 38, 78, 48 }; Console.WriteLine("排序前数组：" string.Join(", ", array)); ShellSort(array); Console.WriteLine("排序后数组：" string.Join(", ", array)); }

C#归并排序算法

简介

归并排序是一种常见的排序算法，它采用分治法的思想，在排序过程中不断将待排序序列分割成更小的子序列，直到每个子序列中只剩下一个元素，然后将这些子序列两两合并排序，最终得到一个有序的序列。

详细文章描述

https://mp.weixin.qq.com/s/ToURWBfVIl7087Ago8fGdQ

代码实现

public static void MergeSort(int[] arr, int left, int right) { if (left < right) { // 计算中间索引 int mid = (left right) / 2; // 对左半部分数组进行归并排序 MergeSort(arr, left, mid); // 对右半部分数组进行归并排序 MergeSort(arr, mid 1, right); // 合并两个有序数组 Merge(arr, left, mid, right); } } public static void Merge(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 j = 0; j < n2; j) { rightArr[j] = arr[mid 1 j]; } // 合并两个有序数组 int k = left; // 初始化合并后的数组索引 int p = 0; // 初始化左半部分数组的索引 int q = 0; // 初始化右半部分数组的索引 while (p < n1 && q < n2) { if (leftArr[p] <= rightArr[q]) { arr[k] = leftArr[p]; p ; } else { arr[k] = rightArr[q]; q ; } k ; } // 复制左半部分数组的剩余元素 while (p < n1) { arr[k] = leftArr[p]; p ; k ; } // 复制右半部分数组的剩余元素 while (q < n2) { arr[k] = rightArr[q]; q ; k ; } } public static void MergeSortRun { int array = { 19, 27, 46, 48, 50, 2, 4, 44, 47, 36, 38, 15, 26, 5, 3 }; Console.WriteLine("排序前数组：" string.Join(", ", array)); MergeSort(array, 0, array.Length - 1); Console.WriteLine("排序后数组：" string.Join(", ", array)); }

C#快速排序算法

简介

快速排序是一种常用的排序算法，它基于分治的思想，通过将一个无序的序列分割成两个子序列，并递归地对子序列进行排序，最终完成整个序列的排序。

详细文章描述

https://mp.weixin.qq.com/s/7vms2Q4s7DBdFs31w4cfVA

代码实现

public class 快速排序算法 { public static void Sort(int[] array, int low, int high) { if (low < high) { //将数组分割为两部分，并返回分割点的索引 int pivotIndex = Partition(array, low, high); //递归对分割后的两部分进行排序 Sort(array, low, pivotIndex - 1); Sort(array, pivotIndex 1, high); } } private static int Partition(int[] array, int low, int high) { //选择最后一个元素作为基准元素 int pivot = array[high]; int i = low - 1; for (int j = low; j <= high - 1; j ) { //如果当前元素小于等于基准元素，则将它与i 1位置的元素交换 if (array[j] <= pivot) { i ; Swap(array, i, j); } } //将基准元素放置到正确的位置上 Swap(array, i 1, high); return i 1; //返回基准元素的索引 } private static void Swap(int[] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } public static void QuickSortRun { int array = { 2, 3, 5, 38, 19, 15, 26, 27, 36, 44, 47, 46, 50, 48, 4 }; Sort(array, 0, array.Length - 1); Console.WriteLine("排序后结果：" string.Join(", ", array)); } }

C#堆排序算法

简介

堆排序是一种高效的排序算法，基于二叉堆数据结构实现。它具有稳定性、时间复杂度为O(nlogn)和空间复杂度为O(1)的特点。

详细文章描述

https://mp.weixin.qq.com/s/zS_ESKzlg05ICqFPIaePkg

代码实现

public static void HeapSort(int[] array) { int arrayLength = array.Length; //构建最大堆 for (int i = arrayLength / 2 - 1; i >= 0; i--) Heapify(array, arrayLength, i); //依次取出堆顶元素，并重新调整堆 for (int i = arrayLength - 1; i >= 0; i--) { //将堆顶元素与当前最后一个元素交换 int temp = array[0]; array[0] = array[i]; array[i] = temp; //重新调整堆 Heapify(array, i, 0); } } private static void Heapify(int[] arr, int n, int i) { int largest = i; //假设父节点最大 int left = 2 * i 1; //左子节点 int right = 2 * i 2; //右子节点 //如果左子节点大于父节点，则更新最大值 if (left < n && arr[left] > arr[largest]) largest = left; //如果右子节点大于父节点和左子节点，则更新最大值 if (right < n && arr[right] > arr[largest]) largest = right; //如果最大值不是当前父节点，则交换父节点和最大值，并继续向下调整堆 if (largest != i) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; Heapify(arr, n, largest); } } public static void HeapSortRun { int array = { 19, 27, 46, 48, 50, 2, 4, 44, 47, 36, 38, 15, 26, 5, 3, 99, 888, 0, -1 }; Console.WriteLine("排序前数组：" string.Join(", ", array)); HeapSort(array); Console.WriteLine("排序后数组：" string.Join(", ", array)); }

C#计数排序算法

简介

计数排序是一种非比较性的排序算法，适用于排序一定范围内的整数。它的基本思想是通过统计每个元素的出现次数，然后根据元素的大小依次输出排序结果。

详细文章描述

https://mp.weixin.qq.com/s/PA5NNqcy3CM9PSncWCsmEg

代码实现

public static void CountingSort(int[] array) { int arrayLength = array.Length; if (arrayLength <= 1) return; int min = array[0]; int max = array[0]; //找出最大值和最小值 for (int i = 1; i < arrayLength; i ) { if (array[i] < min) min = array[i]; if (array[i] > max) max = array[i]; } //统计每个元素出现的次数 int count = new int[max - min 1]; //统计每个元素出现的次数 for (int i = 0; i < arrayLength; i ) { count[array[i] - min] ; } //根据count数组和min值确定每个元素的起始位置 for (int i = 1; i < count.Length; i ) { count[i] = count[i - 1]; } //存储排序结果 int temp = new int[arrayLength]; //根据count数组和min值确定每个元素在temp数组中的位置 for (int i = arrayLength - 1; i >= 0; i--) { int index = count[array[i] - min] - 1; temp[index] = array[i]; count[array[i] - min]--; } //将排序结果复制回原数组 for (int i = 0; i < arrayLength; i ) { array[i] = temp[i]; } } public static void CountingSortRun { int array = { 19, 27, 46, 48, 50, 2, 4, 44, 47, 36, 38, 15, 26, 5, 3, 99, 888}; Console.WriteLine("排序前数组：" string.Join(", ", array)); CountingSort(array); Console.WriteLine("排序后数组：" string.Join(", ", array)); }

C#桶排序算法

简介

桶排序是一种线性时间复杂度的排序算法，它将待排序的数据分到有限数量的桶中，每个桶再进行单独排序，最后将所有桶中的数据按顺序依次取出，即可得到排序结果。

详细文章描述

https://mp.weixin.qq.com/s/YzviDcm3-4E5Wf2jooylJQ

代码实现

public static void BucketSort(int[] array) { int arrLength = array.Length; if (arrLength <= 1) { return; } //确定桶的数量 int maxValue = array[0], minValue = array[0]; for (int i = 1; i < arrLength; i ) { if (array[i] > maxValue) maxValue = array[i]; if (array[i] < minValue) minValue = array[i]; } int bucketCount = (maxValue - minValue) / arrLength 1; //创建桶并将数据放入桶中 List<List<int>> buckets = new List<List<int>>(bucketCount); for (int i = 0; i < bucketCount; i ) { buckets.Add(new List<int>); } for (int i = 0; i < arrLength; i ) { int bucketIndex = (array[i] - minValue) / arrLength; buckets[bucketIndex].Add(array[i]); } //对每个非空的桶进行排序 int index = 0; for (int i = 0; i < bucketCount; i ) { if (buckets[i].Count == 0) { continue; } int tempArr = buckets[i].ToArray; Array.Sort(tempArr); foreach (int num in tempArr) { array[index ] = num; } } } public static void BucketSortRun { int array = { 19, 27, 46, 48, 50, 2, 4, 44, 47, 36, 38, 15, 26, 5, 3, 99, 888}; Console.WriteLine("排序前数组：" string.Join(", ", array)); BucketSort(array); Console.WriteLine("排序后数组：" string.Join(", ", array)); }

C#基数排序算法

简介

基数排序是一种非比较性排序算法，它通过将待排序的数据拆分成多个数字位进行排序。

详细文章描述

https://mp.weixin.qq.com/s/dCG-LLim4UGD1kIY2a3hmA

代码实现

public static void RadixSort(int[] array) { if (array == || array.Length < 2) { return; } //获取数组中的最大值，确定排序的位数 int max = GetMaxValue(array); //进行基数排序 for (int exp = 1; max / exp > 0; exp *= 10) { CountingSort(array, exp); } } private static void CountingSort(int[] array, int exp) { int arrayLength = array.Length; int output = new int[arrayLength]; int count = new int[10]; //统计每个桶中的元素个数 for (int i = 0; i < arrayLength; i ) { count[(array[i] / exp) % 10] ; } //计算每个桶中最后一个元素的位置 for (int i = 1; i < 10; i ) { count[i] = count[i - 1]; } //从原数组中取出元素，放入到输出数组中 for (int i = arrayLength - 1; i >= 0; i--) { output[count[(array[i] / exp) % 10] - 1] = array[i]; count[(array[i] / exp) % 10]--; } //将输出数组复制回原数组 for (int i = 0; i < arrayLength; i ) { array[i] = output[i]; } } private static int GetMaxValue(int[] arr) { int max = arr[0]; for (int i = 1; i < arr.Length; i ) { if (arr[i] > max) { max = arr[i]; } } return max; } public static void RadixSortRun { int array = { 19, 27, 46, 48, 99, 888, 50, 2, 4, 44, 47, 36, 38, 15, 26, 5, 3 }; Console.WriteLine("排序前数组：" string.Join(", ", array)); RadixSort(array); Console.WriteLine("排序后数组：" string.Join(", ", array)); }