前言：
排序算法是一种将一组数据按照特定顺序排列的算法。数据结构排序算法的选择取决于数据的特征、规模和性能需求。
接下来我们就要实现排序~~
我们需要实现的一些功能：
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<stdbool.h> #include<time.h> // 打印 void Print_a(int* a, int sz); // 交换 void Swap(int* p1, int* p2); // 插入排序 void InsertSort(int* a, int n); // 冒泡排序 void BubbleSort(int* a, int n); // 希尔排序 void ShellSort(int* a, int n); // 堆排序 void AdjustDwon(int* a, int n, int root); void HeapSort(int* a, int n); // 选择排序 void SelectSort(int* a, int n); // ------------------------------------------------------ // 快速排序hoare版本 int PartSort1(int* a, int begin, int end); // 快速排序挖坑法 int PartSort2(int* a, int begin, int end); // 快速排序前后指针法 int PartSort3(int* a, int begin, int end); // 排序函数 void QuickSort(int* a, int begin, int end); //------------------------------------------------------ // 快速排序 非递归实现 void QuickSortNonR(int* a, int begin, int end); // 归并排序递归实现 void MergeSort(int* a, int n); // 归并排序非递归实现 void MergeSortNonR(int* a, int n); // 非比较排序 void CountSort(int* a, int n);
冒泡排序
- 冒泡排序是一种基本的排序算法，其核心思想是通过多次交换相邻元素的位置，使得每一轮循环都将最大（或最小）的元素移动到序列的最后。这个过程就像气泡逐渐上升到表面一样，因而得名"冒泡排序"。
代码实现：
void bubbleSort(int* a,int n) { for (int i = 0; i < n-1; i++) { for (int j = 0; j < n - 1 - i; j++) { if (a[j] > a[j + 1]) { Swap(&a[j], &a[j + 1]); } } } }
优点：
- 简单易懂： 冒泡排序的思想非常简单，容易理解和实现，适合初学者学习排序算法的基本概念。
- 原地排序： 冒泡排序是一种原地排序算法，不需要额外的空间来存储临时数据，只需要一个常数级的辅助空间。
- 稳定性： 冒泡排序是一种稳定的排序算法，相等元素的相对位置不会发生变化。
缺点：
效率低： 冒泡排序的平均时间复杂度为O(n^2)，在处理大规模数据时性能较差，比较和交换的操作太过频繁。
不适合大规模数据： 冒泡排序的性能不如一些更高效的排序算法，如快速排序、归并排序等，特别是在数据规模较大的情况下。
对基本有序的序列效率低下： 在实际应用中，如果序列已经基本有序，冒泡排序仍然需要进行多次比较和交换，效率不高。
插入排序
- 插入排序是一种简单直观的排序算法，其核心思想是将一个元素插入到已经排好序的数组（或子数组）中的合适位置，以达到整体有序的效果。插入排序的工作方式类似于整理扑克牌的过程：手里的牌是已经有序的部分，新摸到的牌则需要插入到适当的位置，保持有序性。
代码实现：
void InsertSort(int* a, int n) { for (int i = 0; i < n - 1; i++) { // 记录每次i的位置 int end = i; // 将i+1的位置保存 int tmp = a[end + 1]; // 一次排序 while (end >= 0) { // 如果后面的数字小于前面的那一个就进行往后覆盖， // 然后end--，继续排序 if (tmp < a[end]) { a[end + 1] = a[end]; --end; } else { // 如果大于或者等于了就跳出 break; } } // 因为--end了，所以就要在end+1的位置放刚刚保存的值tmp a[end + 1] = tmp; } }
优点：
- 简单易理解： 插入排序的实现非常简单，易于理解和实现，适用于小规模数据或部分有序的数据。
- 稳定性： 插入排序是一种稳定的排序算法，相等元素的相对位置不会发生变化。
- 适应性好： 如果数据已经基本有序，插入排序的性能会比较好，因为大部分元素都已经在正确的位置上，只需少量的比较和移动。
- 原地排序： 插入排序是一种原地排序算法，不需要额外的空间来存储临时数据。
缺点：
- 效率低： 插入排序的平均时间复杂度为O(n^2)，在数据规模较大时，性能不如一些更高效的排序算法，如快速排序、归并排序等。
- 对大规模数据排序效率低下： 插入排序在处理大规模数据时性能较差，因为它需要大量的比较和移动操作。
- 不适合链表结构： 插入排序需要频繁地移动元素，对于链表结构来说，由于不支持随机访问，插入排序效率较低。
希尔排序
- 希尔排序（Shell Sort）是一种插入排序的改进版本，也称为缩小增量排序。它通过比较相距一定间隔的元素，逐步减小这个间隔，直到间隔为1时完成最后一轮排序。希尔排序的核心思想是先使数组中任意间隔为h的元素有序，然后逐步减小h，最终使整个数组有序。
代码实现：
void ShellSort(int* a, int n) { int gap = n; // gap > 1时是预排序，目的让他接近有序 // gap == 1是直接插入排序，目的是让他有序 while (gap > 1) { // gap = gap / 2; // log 2 N gap = gap / 3 + 1; // log 3 N //每次排gap次 for (int j = 0; j < n - gap; j++) { //插入排序 int end = j; int tmp = a[end + gap]; while (end >= 0) { if (tmp < a[end]) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } } }
优点：
- 相对于插入排序的改进： 希尔排序是插入排序的改进版本，通过引入间隔（gap）的概念，减少了数据的搬移次数，提高了效率。
- 适用于中等规模数据： 希尔排序相对于一些简单的排序算法，对中等规模的数据表现较好，比如对于几千甚至几万个元素的排序。
- 不稳定性： 相比较于一些稳定排序算法（如归并排序、插入排序），希尔排序的不稳定性可能在某些情况下是一个优势，特别是在排序过程中需要对元素进行位置交换的场景。
缺点：
- 不适用于大规模数据： 希尔排序的性能相对较好，但在处理非常大规模数据时，效率可能不如一些更为高级的排序算法，比如快速排序、归并排序等。
- 不稳定性： 尽管不稳定性在某些情况下可以是优势，但在某些应用场景下，需要保持相等元素的相对位置不变，这时候希尔排序的不稳定性可能成为一个缺点。
选择排序
- 选择排序（Selection Sort）是一种简单直观的排序算法，其基本思想是通过不断选择未排序序列中的最小（或最大）元素，将其与未排序序列的第一个元素交换，从而逐步构建有序序列。
代码实现：
// 选择排序 void SelectSort(int* a, int n) { int begin = 0, end = n - 1; while (begin < end) { // 两头找 int mini = begin, maxi = begin; for (int i = begin + 1; i <= end; i++) { // 如果i的位置比mini小就更新一下 if (a[i] < a[mini]) { mini = i; } //如果i的位置比maxi大就更新一下 if (a[i] > a[maxi]) { maxi = i; } } // 走到这里就说明小的要和左边交换一下 Swap(&a[mini], &a[begin]); // 注意：这里Eugene左边的和maxi相等了要更新一下maxi if (begin == maxi) { maxi = mini; } // 然后交换maxi和end Swap(&a[end], &a[maxi]); ++begin; --end; } }
优点：
- 简单易理解： 选择排序的实现非常简单，易于理解和实现，适合初学者学习排序算法的基本概念。
- 原地排序： 选择排序是一种原地排序算法，不需要额外的空间来存储临时数据，只需要一个常数级的辅助空间。
- 不稳定性： 选择排序是一种不稳定的排序算法，相等元素的相对位置可能发生变化，但在某些情况下，不稳定性可能是一个优势。
缺点：
- 效率低： 选择排序的平均时间复杂度为O(n^2)，在处理大规模数据时性能较差，由于每次只能确定一个元素的位置，比较和交换的操作过于频繁。
- 对基本有序的序列效率低下： 在实际应用中，如果序列已经基本有序，选择排序仍然需要进行大量的比较和交换，效率不高。
- 不适合大规模数据： 选择排序的性能不如一些更高效的排序算法，如快速排序、归并排序等，特别是在数据规模较大的情况下。
堆排序
- 堆排序是一种基于二叉堆数据结构的排序算法。它利用了堆的性质来进行排序，其中堆分为最大堆和最小堆两种类型。在最大堆中，父节点的值大于或等于其子节点的值；在最小堆中，父节点的值小于或等于其子节点的值。
- 这里在堆排序章节已经讲过了，这里就不细讲了~~
代码实现：
void AdjustDwon(int* a, int n, int root) { int parent = root; int child = parent * 2 + 1; while (child < n) { if (child + 1 < n && a[child + 1] > a[child]) ++child; if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } void HeapSort(int* a, int n) { for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDwon(a, n, i); } int end = n - 1; while (end > 0) { Swap(&a[0], &a[end]); AdjustDwon(a, end, 0); --end; } }
优点：
- 稳定性： 堆排序是一种不稳定的排序算法，因为在构建初始堆和进行堆调整的过程中可能破坏相同元素的相对顺序。然而，如果对于相同的元素，可以使用索引来保持其相对顺序，就可以避免这个问题。
- 原地排序： 堆排序是一种原地排序算法，不需要额外的存储空间来存储待排序的数据，只需要常数级别的辅助空间。
- 时间复杂度： 堆排序的平均、最好和最坏情况下的时间复杂度都是 O(n log n)，其中 n 是待排序元素的数量。这使得堆排序在大数据集上表现良好。
缺点：
- 非自适应性： 堆排序的时间复杂度在各种情况下都是 O(n log n)，无论输入数据的初始顺序如何。因此，它对于部分有序的数据或者小规模数据集的排序效率可能不如一些自适应性较强的算法。
- 不稳定： 在排序过程中，堆排序可能破坏相同元素的相对顺序，因此是一种不稳定的排序算法。如果对稳定性有要求，可能需要考虑其他算法。
- 不适用于链式存储结构： 堆排序通常需要对数组进行直接访问，而不适用于链式存储结构。因此，如果数据结构采用链表形式存储，需要将其转换为数组再进行排序，这可能引入额外的开销。
快速排序–交换排序
三数取中
nt GetMidi(int* a, int left, int right) { //int midi = (begin + end) / 2; int mid = (left + right) >> 1; if (a[left] < a[mid]) { if (a[mid] < a[right]) return mid; else if (a[left] > a[right]) return left; else return right; } else // a[left] > a[mid] { if (a[mid] > a[right]) return mid; else if (a[left] < a[right]) return left; else return right; } }
快速排序hoare版本
- 快速排序是一种常用的排序算法，Hoare版本是其中一种实现方式，由Tony Hoare提出。
代码实现：
int PartSort1(int* a, int begin, int end) { // 三数取中 int midi = GetMidi(a, begin, end); Swap(&a[midi], &a[begin]); // 要在最左边开始 int left = begin, right = end; int keyi = begin; while (left < right) { // 右边找小 while (left < right && a[right] >= a[keyi]) { --right; } // 左边找大 while (left < right && a[left] <= a[keyi]) { ++left; } // 找到了，就交换 Swap(&a[left], &a[right]); } // 交换的左边的和keyi，然后更新一下keyi Swap(&a[left], &a[keyi]); return left; } void QuickSort(int* a, int begin, int end) { if (begin >= end) return; // 小区间 if (end - begin + 1 < 10) { InsertSort(a + begin, end - begin + 1); } else { int keyi = PartSort1(a, begin, end); QuickSort(a, begin, keyi - 1); QuickSort(a, keyi + 1, end); } }
优点：
- 原地排序： 快速排序是一种原地排序算法，不需要额外的空间来存储临时数据，只需要一个常数级的辅助空间。
- 平均情况下具有较好的性能： 在平均情况下，快速排序的时间复杂度为O(n log n)，这使得它在实践中具有较好的性能。
- 适用于大规模数据： 快速排序在处理大规模数据时通常表现良好，尤其是相对于一些平均时间复杂度较高的排序算法而言。
- 对基本有序的数据排序效果好： 在一些情况下，快速排序对基本有序的数据排序效果较好。
缺点：
- 不稳定性： 快速排序是一种不稳定的排序算法，相等元素的相对位置可能发生变化，如果需要稳定性，可能需要额外的处理。
- 对于极端情况的性能： 在最坏情况下，即已经有序的序列，快速排序的时间复杂度为O(n^2)，这时性能可能较差。为了避免这种情况，通常会使用一些优化策略，比如随机化选择枢轴。
- 对于小规模数据性能较差： 在小规模数据的排序中，快速排序的递归调用会增加额外的开销，性能可能不如一些简单的排序算法，如插入排序。
快速排序挖坑法
- 快速排序的挖坑法（也称为Lomuto分区方案）是快速排序的一种实现方式。在挖坑法中，选择一个基准元素，通过不断交换元素将数组分成两个部分，左边的部分都小于基准元素，右边的部分都大于基准元素。接着，对左右两个部分分别递归进行同样的操作。
代码实现：
int PartSort2(int* a, int begin, int end) { int midi = GetMidi(a, begin, end); Swap(&a[midi], &a[begin]); int key = a[begin]; int holei = begin; while (begin < end) { // 右边找小 while (begin < end && a[end] >= key) { --end; } a[holei] = a[end]; holei = end; // 左边找大 while (begin < end && a[begin] <= key) { ++begin; } a[holei] = a[begin]; holei = begin; } a[holei] = key; return holei; } void QuickSort(int* a, int begin, int end) { if (begin >= end) return; // 小区间 if (end - begin + 1 < 10) { InsertSort(a + begin, end - begin + 1); } else { int keyi = PartSort2(a, begin, end); QuickSort(a, begin, keyi - 1); QuickSort(a, keyi + 1, end); } }
优点：
- 原地排序： 挖坑法是一种原地排序算法，不需要额外的空间来存储临时数据，只需要一个常数级的辅助空间。
- 简单直观： 挖坑法实现相对较简单，容易理解和实现，适用于教学和学习排序算法。
缺点：
- 不稳定性： 挖坑法是一种不稳定的排序算法，相等元素的相对位置可能发生变化，如果需要稳定性，可能需要额外的处理。
- 最坏情况下的性能： 在最坏情况下，即已经有序的序列，挖坑法的性能可能较差。这时的时间复杂度为O(n^2)，因为每次分区只能使序列中的一个元素有序。
- 对于小规模数据性能较差： 在小规模数据的排序中，挖坑法的递归调用会增加额外的开销，性能可能不如一些简单的排序算法，如插入排序。
排序 | 冒泡 插入 希尔 选择 堆 快排 归并 非递归 计数 基数 排序（二）:https://developer.aliyun.com/article/1426989
