快速排序前后指针法
- 快速排序的前后指针法（也称为Hoare分区方案）是另一种实现方式。在这个方法中，通过两个指针从数组的两端分别向中间移动，交换不符合排序条件的元素，最终将数组分为两个部分，左边部分小于基准元素，右边部分大于基准元素。
代码实现：
int PartSort3(int* a, int begin, int end) { int midi = GetMidi(a, begin, end); Swap(&a[begin], &a[midi]); int prev = begin; int cur = prev + 1; int keyi = begin; while (cur <= end) { if (a[cur] < a[keyi] && ++prev != cur) Swap(&a[prev], &a[cur]); ++cur; } Swap(&a[keyi], &a[prev]); keyi = prev; return prev; } 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 = PartSort3(a, begin, end); QuickSort(a, begin, keyi - 1); QuickSort(a, keyi + 1, end); } }
优点：
- 原地排序： 前后指针法是一种原地排序算法，不需要额外的空间来存储临时数据，只需要一个常数级的辅助空间。
- 相对较好的性能： 在平均情况下，快速排序的前后指针法具有较好的性能，时间复杂度为O(n log n)。
- 不需要额外的空间： 与挖坑法相比，前后指针法在实际的操作中，不需要额外的元素用于填坑，从而减少了一些操作。
缺点：
- 不稳定性： 前后指针法是一种不稳定的排序算法，相等元素的相对位置可能发生变化，如果需要稳定性，可能需要额外的处理。
- 最坏情况下的性能： 在最坏情况下，即已经有序的序列，前后指针法的性能可能较差。这时的时间复杂度为O(n^2)，因为每次分区只能使序列中的一个元素有序。
- 对于小规模数据性能较差： 在小规模数据的排序中，前后指针法的递归调用会增加额外的开销，性能可能不如一些简单的排序算法，如插入排序。
快速排序–非递归实现
- 我们这里使用栈来解决这个问题~~
- 先入栈，然后再进行分割
- 注意： 如果是先入右后入左，那么出的时候就要先出左后出右
- 栈不为空就继续，然后分割排左边和右边
代码实现：
#include"Stack.h" // 快速排序 非递归实现 void QuickSortNonR(int* a, int begin, int end) { ST s; StackInit(&s); // 先入右后入左 StackPush(&s, end); StackPush(&s, begin); while (!StackEmpty(&s)) { // 先出左后出右 int left = StackTop(&s); StackPop(&s); int right = StackTop(&s); StackPop(&s); // 排序 int keyi = PartSort3(a, left, right); // [left keyi-1] keyi [keyi+1 right] if (left < keyi - 1) { StackPush(&s, keyi - 1); StackPush(&s, left); } if (keyi + 1 < right) { StackPush(&s, right); StackPush(&s, keyi + 1); } } StackDestroy(&s); }
归并排序
- 归并排序（Merge Sort）是一种分治算法，它的基本思想是将待排序的数组分成两个相等大小的子数组，然后分别对这两个子数组进行排序，最后将排序好的子数组合并成一个有序的数组。
代码实现：
void _MergeSort(int* a, int begin, int end, int* tmp) { if (begin >= end) return; // 分割 // 这里右移一位相当于 /2 int mid = (begin + end) >> 1; // 递归 _MergeSort(a, begin, mid, tmp); _MergeSort(a, mid + 1, end, tmp); // [begin mid][mid+1 end] 归并 int begin1 = begin, end1 = mid; int begin2 = mid + 1, end2 = end; int i = begin; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] <= a[begin2]) { tmp[i++] = a[begin1++]; } else { tmp[i++] = a[begin2++]; } } while (begin1 <= end1) { tmp[i++] = a[begin1++]; } while (begin2 <= end2) { tmp[i++] = a[begin2++]; } // 拷贝回原数组 for (int i = begin; i <= end; ++i) { a[i] = tmp[i]; } //memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin) + 1); } // 归并排序递归实现 void MergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail!\n"); return; } _MergeSort(a, 0, n - 1, tmp); free(tmp); }
优点：
- 稳定性： 归并排序是一种稳定的排序算法，即对于相等的元素，它们在排序后的相对位置保持不变。
- 适用于链表： 归并排序对于链表等非随机访问结构的数据也非常有效，因为它不涉及随机访问，只涉及指针操作。
- 适用于外部排序： 归并排序在外部排序（需要对外部存储进行排序的情况）中表现良好，因为它可以很容易地通过合并有序的外部文件来实现。
- 稳定的时间复杂度： 归并排序的时间复杂度是稳定的，不受输入数据的影响，总是O(n log n)。
缺点：
- 额外空间需求： 归并排序需要额外的内存空间来存储临时数组，这使得它的空间复杂度相对较高，是O(n)。
- 非原地排序： 归并排序是一种非原地排序算法，即它需要额外的空间来存储临时数组，而不是在原始数组上进行排序。这对于内存受限的情况可能不太理想。
- 常数因子较大： 归并排序的常数因子较大，因此在实际应用中可能被一些其他排序算法（如快速排序）超越。
归并排序非递归实现
- 思想和上面的归并排序差不多~~
代码实现：
void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); int gap = 1; // 每组数据个数 while (gap < n) { for (int i = 0; i < n; i += 2 * gap) { // [i, i+gap-1] [i+gap,i+2*gap-1] int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap - 1; // 归并过程中右半区间可能就不存在 if (begin2 >= n) break; // 归并过程中右半区间算多了, 修正一下 if (end2 >= n) { end2 = n - 1; } int index = i; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } // 拷贝回去 for (int j = i; j <= end2; ++j) { a[j] = tmp[j]; } } gap *= 2; } free(tmp); }
非比较排序【计数排序】
- 计数排序（Counting Sort）是一种非比较性的整数排序算法，它通过确定每个元素在输出序列中的位置来实现排序。
代码实现：
void CountSort(int* a, int n) { int max = a[0], min = a[0]; for (int i = 0; i < n; i++) { if (a[i] > max) max = a[i]; if (a[i] < min) min = a[i]; } int range = max - min + 1; int* count = (int*)malloc(sizeof(int) * range); if (count == NULL) { perror("malloc fail!\n"); return; } memset(count, 0, sizeof(int) * range); //统计次数 for (int i = 0; i < n; i++) { count[a[i] - min]++; } int i = 0; for (int j = 0; j < range; j++) { while (count[j]--) { a[i++] = j + min; } } free(count); }
优点：
- 线性时间复杂度： 计数排序是一种具有线性时间复杂度的排序算法，其时间复杂度为O(n + k)，其中n是输入元素的数量，k是输入范围的大小。在输入范围较小的情况下，计数排序通常比其他O(n log n)的排序算法更快。
- 稳定性： 计数排序是一种稳定的排序算法，即相等元素的相对顺序在排序后仍然保持不变。
- 适用于整数排序： 计数排序适用于整数排序，尤其是在知道输入范围不太大的情况下。它不依赖于比较操作，因此在某些情况下可能比基于比较的排序算法更高效。
缺点：
- 空间复杂度： 计数排序的主要缺点是它需要额外的空间来存储计数数组。如果输入范围很大，可能需要较大的额外空间，这可能导致空间复杂度较高。
- 仅适用于整数： 计数排序仅适用于整数排序，因为它依赖于将元素映射到计数数组的索引。对于浮点数或其他数据类型，需要进行额外的转换。
- 对输入范围的限制： 计数排序要求输入的元素必须在已知范围内，否则需要进行范围的确定和调整，增加了实现的复杂性。
基数排序
- 基数排序是一种非比较性的排序算法，它根据关键字的每一位来排序数据。
代码实现：
这里就先不实现，之后会开一个新文章来进行阐述，并且使用C++来写~~
优点：
- 稳定性： 基数排序是一种稳定的排序算法，即相等元素的相对顺序在排序后保持不变。
- 适用范围广： 基数排序对于数据的分布没有特殊的要求，适用于各种数据类型，包括整数、字符串等。
- 适用于大量数据： 在某些情况下，基数排序的性能可能比一些常见的比较性排序算法（如快速排序、归并排序）更好，尤其是当数据量非常大时。
- 不受输入数据范围限制： 基数排序不受输入数据范围的限制，可以处理负数和小数。
缺点：
- 空间复杂度较高： 基数排序的空间复杂度取决于数据的位数，如果数据位数很大，可能需要较大的辅助空间来存储中间结果。
- 不适用于小范围数据： 当数据范围比较小而位数较大时，基数排序可能不是最优选择，因为它需要较大的辅助空间。
- 只能处理正整数或字符串： 基数排序主要用于整数或字符串的排序，对于其他数据类型可能需要转换为整数或字符串形式，增加了额外的开销。
- 效率受制于位数： 基数排序的效率受制于位数，如果位数很大，可能需要进行多轮排序，导致时间复杂度较高。
排序算法复杂度及稳定性分析
