数据结构——排序算法

1、排序的概念

排序是指的是将一组数据（如数字、单词、记录等）按照某种特定的顺序（升序或降序）进行排列的过程。排序算法是实现排序的程序或方法，它们在软件开发和数据处理中扮演着至关重要的角色。

排序算法可以根据不同的标准进行分类，如：

内部排序与外部排序：内部排序是指数据全部加载到内存中进行排序，而外部排序则涉及处理大量数据，这些数据可能太大而无法一次性放入内存。
比较排序与非比较排序：比较排序是基于比较操作来决定元素之间的相对顺序，如快速排序、归并排序等。非比较排序不通过比较来确定元素的顺序，如计数排序、基数排序等。
稳定性：稳定的排序算法能够保持相等元素的原始顺序，而非稳定排序算法可能会改变相等元素的顺序。
时间复杂度：算法执行所需的时间与输入数据量的关系。常见的时间复杂度有O(n)、O(n log n)、O(n^2)等。
空间复杂度：算法执行过程中需要的额外空间量。
在线排序与离线排序：在线排序是指数据一个接一个地处理，而离线排序则是在所有数据都可用的情况下进行。

2、常见的排序算法

接下来我们一一实现：

直接插入排序

void InsertSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){int end = i;int tem = a[end + 1];while (end >= 0){if (tem < a[end]){a[end + 1] = a[end];end--;}elsebreak;}a[end + 1] = tem;}
}

排序思想是认为第一个元素是有序的，然后从第二个元素开始排序，先把元素保存到tem中，然后从后往前遍历数组，找到比tem大的就向后挪一位，遍历完后把tem放到下标为ennd+1的位置上，继续排下一个数

看一下动图演示:

直接插入排序的

时间复杂度：O(N^2)

空间复杂度：O(1)

稳定性：稳定

希尔排序

void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 2;for (int i = 0; i < n - gap; i++){int end = i;int tem = a[end + gap];while (end >= 0){if (tem < a[end]){a[end + gap] = a[end];end -= gap;}elsebreak;}a[end + gap] = tem;}}
}

希尔排序（Shell Sort）是插入排序的一种更高效的改进版本，由Donald Shell于1959年提出。它是基于插入排序的一种分组比较排序算法，也被称为“缩小增量排序”。希尔排序的核心思想是将原始数据集分割成若干个子序列进行插入排序，这些子序列由原始数据集中的元素按照增量序列划分而来。随着增量序列的减小，整个数据集逐渐被整合成一个有序的序列。

动图演示：

选择增量序列：增量序列的选择对希尔排序的性能有很大影响。常见的增量序列有希尔原始序列（N/2，N/4，...，1），Hibbard增量序列（1, 3, 7, ..., 2^k - 1），Knuth序列（1, 4, 13, ..., (3^k - 1)/2）等。
分组：按照当前增量将数组分为若干子序列。例如，如果当前增量是5，那么索引为0, 5, 10, ...的元素将分为一组，索引为1, 6, 11, ...的元素将分为另一组，以此类推。
对各组进行插入排序：在每个子序列上应用插入排序算法，使得每个子序列有序。
减小增量，重复上述步骤：随着增量的减小，子序列的间隔逐渐减小，最终当增量为1时，整个数组将作为一个序列进行一次插入排序，此时数组应该是基本有序的，所以最后一步的插入排序会非常快。
完成排序：当增量减小到1时，整个数组将作为一个序列进行最后一次插入排序，此时数组已经基本有序，所以排序会很快完成。

时间复杂度：希尔排序的时间复杂度依赖于增量序列的选择。最坏情况下的时间复杂度为O(n^2)，但是对于中等大小的数组，实际运行时间可能接近于O(n log^2 n)。最佳情况下，如果增量序列选择得当，时间复杂度可以达到O(n log n)。有人算出希尔排序的时间复杂度接近于O(N^1.3)，我们记住就行了。

空间复杂度：O(1)

稳定性：不稳定

选择排序

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++){if (a[i] < a[mini])mini = i;if (a[i] > a[maxi])maxi = i;}swap(&a[begin], &a[mini]);if (maxi == begin)maxi = mini;swap(&a[end], &a[maxi]);begin++;end--;}
}

选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理是每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

上面是对选择排序的优化，同时选取最大和最小的值进行比较，然后放在队头和队尾

if语句是为了当前数组中最大的数在最小的位置上，会发生重复交换，如果加个if语句可以避免这种情况，如果不理解的小伙伴可以把if语句去掉，调试一下去发现问题，肯定会理解的更加透彻！

冒泡排序

代码展示：

//冒泡排序
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 + 1] < a[j]){swap(&a[j + 1], &a[j]);}}}
}

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

冒泡排序的基本思想是：通过相邻元素之间的比较和交换，每一轮比较后，最大的元素会“冒泡”到数列的最后位置。这个过程会重复进行，直到整个数列有序。

时间复杂度：O(N^2)

空间复杂度：O(1)

稳定性：稳定

堆排序

void AdjustDown(int* a, int n, int parent)
{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--){AdjustDown(a, n, i);}int end = n - 1;while (end >= 0){swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
}

堆排序使用了二叉树的思想，用向下调整建堆，如果我们建的是小堆，然后交换堆顶和堆最后一个元素，这样最小的元素就到了最后，然后依次向下调整，就形成了升序，

快速排序

快速排序（Quick Sort）是一种高效的排序算法，由C. A. R. Hoare在1960年提出。它的基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分的所有记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。快速排序的核心是分治法（Divide and Conquer）策略。

void QuickSortHoare(int* a, int left, int right)
{if (left >= right)return;int begin = left, end = right;int keyi = left;while (left < right){while (left<right && a[right]>=a[keyi])right--;while (left < right && a[left] <= a[keyi])left++;swap(&a[left], &a[right]);}swap(&a[keyi], &a[left]);keyi = left;QuickSortHoare(a, begin, keyi - 1);QuickSortHoare(a, keyi+1, end);
}

快速排序还有改进的双指针法：

//快速排序  双指针版本
void QuickSortTowPorters(int* a, int left, int right)
{if (left >= right)return;int keyi = left;int prev = left;int cur = left + 1;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur)swap(&a[prev], &a[cur]);cur++;}swap(&a[keyi], &a[prev]);keyi = prev;QuickSortTowPorters(a, left, keyi - 1);QuickSortTowPorters(a, keyi+1, right);
}

这段代码是比较精简的，请看动图演示

归并排序

//归并排序
void _mergeSort(int* a, int begin, int end, int* tem)
{if (begin == end)return;int mid = (begin + end) / 2;_mergeSort(a, begin, mid, tem);_mergeSort(a, mid + 1, end, tem);int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2])tem[i++] = a[begin1++];elsetem[i++] = a[begin2++];}while (begin1 <= end1){tem[i++] = a[begin1++];}while (begin2 <= end2){tem[i++] = a[begin2++];}memcpy(a + begin, tem + begin, sizeof(int) * (end - begin + 1));
}void MergeSort(int* a, int n)
{int* tem = (int*)malloc(sizeof(int) * n);assert(tem);_mergeSort(a, 0, n - 1, tem);free(tem);tem = NULL;
}

归并排序（Merge Sort）是一种分治算法，其核心思想是将一个大问题分解成若干个较小的子问题来解决，然后将子问题的解合并起来得到原问题的解。在排序领域，归并排序通过不断地将数组分成两半，对每一半进行排序，然后将排序好的两半合并在一起，从而达到整个数组有序的目的。

归并排序的步骤可以分为两个主要部分：分裂（Divide）和合并（Merge）。

分裂（Divide）：
- 将数组从中间分成两个相等（或接近相等）的子数组。
- 对这两个子数组分别进行归并排序。
- 这个过程会递归进行，直到子数组的长度为1，此时子数组自然是有序的。
合并（Merge）：
- 将两个有序的子数组合并成一个更大的有序数组。
- 合并过程中，需要一个临时数组来存放合并后的有序数组。
- 比较两个子数组的前端元素，将较小的元素放入临时数组，然后移动对应的指针。
- 重复这个过程，直到所有元素都被合并到临时数组中。
- 将临时数组的内容复制回原数组（或者直接使用临时数组作为结果）。

以下是归并排序的非递归实现，比较难理解

//归并排序  非递归实现
void MergeSortNonR(int* a, int n)
{int* tem = (int*)malloc(sizeof(int) * n);assert(tem);int gap = 1;while (gap < n){for (int j = 0; j < n; j += 2 * gap){//重点，难点int begin1 = j, end1 = begin1 + gap - 1;int begin2 = begin1 + gap, end2 = begin2 + gap - 1;//处理越界问题if (begin1 > n || begin2 > n)break;if (end2 > n)end2 = n - 1;int i = j;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2])tem[i++] = a[begin1++];elsetem[i++] = a[begin2++];}while (begin1 <= end1){tem[i++] = a[begin1++];}while (begin2 <= end2){tem[i++] = a[begin2++];}memcpy(a + j, tem + j, sizeof(int) *(end2-j+1));}}
}

可以看一下动图展示：