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

C数据结构：排序

news 来源：原创 2024/9/20 15:22:07

冒泡排序

选择排序

堆排序

插入排序

希尔排序

快速排序

hoare版本

挖坑法

前后指针法

快速排序优化

三数取中法

小区间优化

快速排序非递归

栈版本

队列版本

归并排序

归并排序非递归

编辑

计数排序

各排序时间、空间、稳定汇总

冒泡排序

void BubbleSort(int* a, int n)
{for (int i = 0; i < n; i++){int flag = 0;for (int j = 0; j < n - i - 1; j++){if (a[j] > a[j + 1]){Swap(&a[j], &a[j + 1]);flag = 1;}}if (flag == 0)break;}
}

冒泡排序相信你已经写了不少了

冒泡排序的思想是两两比较，如果要排升序那么要找到最大的，一直比较直到找到最大的冒到最后，然后进行n次这样的流程即完成排序

这里对冒泡排序有两个优化点

1. 第二个循环里我们可以写 j < n - 1，但优化过后就是 j < n - i - 1

要-1是因为防止下面的a[j + 1]数组越界，而-i则是因为已经排过了i次，那么后面就有i个数是已经排好的，所以不需要进入下面的if语句进行比较

2. 用了一个flag变量，主要是看是否有进入过if语句，若没有进入过if语句说明数据已经是排好的，那么即可直接break退出循环

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

空间复杂度：O(1)

由于时间复杂度过高，在实际应用中并无意义，只有在教学中有意义

稳定性：稳定

选择排序

void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;int maxi = 0, mini = 0;while (begin < end){int maxi = begin, mini = begin;for (int i = begin + 1; i <= end; i++){if (a[i] > a[maxi])maxi = i;if (a[i] < a[mini])mini = i;}Swap(&a[begin], &a[mini]);Swap(&a[end], &a[maxi]);if (begin == maxi)maxi = mini;begin++;end--;}
}

选择排序的思想是先找小或找大，找到了就放在最后或者第一个，缩小区间循环往复

但这里写的选择排序是一次找两个，遍历一次即找大又找小

时间复杂度：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[parent], &a[child]);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--;}
}

堆排序是选择排序的一种。

堆排序的思想是利用向下调整（向上调整也可以）先建大堆（or小堆），这样我们就能找到最大或者最小的那个数据，交换到末尾即放置好第一个数的位置，并接着向下调整保持堆的特性

具体细节参考

C数据结构：堆（实现、排序）-CSDN博客

时间复杂度：O(N * logN)

空间复杂度：O(1)

由于堆的高度是 O(logN)，每个非叶子节点的调整时间复杂度是 O(log N)

数组中有 O(N) 个非叶子节点，因此构建堆的总时间复杂度是 O(N * logN)

但实际上，由于树的结构，这个操作通常被优化为 O(N)

稳定性：不稳定

插入排序

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

插入排序的思想就像插入扑克牌排序一样，我们需要从小到大一个个排好序

end之前表示已经排好序的数组（最开始1个数也算排好），end+1就表示我们要在[0，end]这个区间里插入end+1的这个值，此过程循环n-1次即可

所以while循环控制的是一次一个数插入的过程，tmp表示要插入的数，若tmp < a[end]（升序）即我们需要在前面这个有序区间内往前走（end--），若tmp > a[end]则找到了我们需要插入的位置，这个位置就是end+1

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

空间复杂度：O(1)

它虽然和冒泡排序看起来差不多，但它还是比冒泡排序快很多的

但是相比堆排、快排、希尔排序、归并排序这些就没法比了

稳定性：稳定

希尔排序

void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++){int end = i;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，然后按照这个间隔分成gap组，根据这个组内来进行排序，这样就从原本的杂乱无章变成稍微有序。此时接着将gap缩小，那么数组将会越来越有序，最后就变成了有序的数组了

第二次由于已经是有序了，所以不需要排

以此类推，当全部的gap组排好之后，我们的第一躺希尔排序就完成了

如果你觉得这样排序那么多次，效率并没有什么提升，就大错特错了

拿插入排序来比较，插入排序如果想排好上面的一次组数据（9，7，3），那么它需要一个下标来沿途经过整个数组一个个比较，当到达7的时候才能够交换，然后接着跟沿途的其他数据一个个比较，最后才能找到3和3交换，这么一个过程就将近遍历了一整个数组

而我们的希尔排序的gap就可以让它快速的跳跃中间的数据，依次效率有了极大的提升。就上图的这10个数据可能看的不太明显，只需要比较几次。但是我们的计算机的效率是很高的，大多数电脑一秒钟可以跑上亿的数据，所以若是在实际中我们需要排个几百万上亿个数据的时候，我们的gap就可以跳过很多数据的比较。

代码实现中我们可以发现其实它跟插入排序基本一致，就多了一个循环，然后把内部的部分数据改成gap就完成了

内层的两个循环是进行一躺gap组的排序，可以将杂乱无章的数组变成逐渐有序的数组

最外层的循环是控制gap的，gap越小，进行一躺排序就会越有序，当最后gap为1的时候，它其实就是我们上面的插入排序，所以gap为1的时候排序就已经完成了

gap / 3 + 1的原因是个人认为/3的效率比较高，但是只是/3会有可能到不了1的情况，例如：

2 / 3 = 0，接下来我们一直/3都到不了0

所以我们需要+1

最开始Shell提出取 gap / 2，后来Knuth提出gap / 3 + 1，无论是哪一种具体是谁快还没有得到证明

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

空间复杂度：O(1)

稳定性：不稳定

快速排序

void QuickSort(int* a, int left, int right)
{if (left >= right)return;int keyi = PartSort1(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);
}

PartSort是部分排序，在快排中是个选key的过程

key是一个值，通常把它选成数组中最左边的第一个数

我们进行一次PartSort时就可以把key的位置给确定好，算是排好了一个数，而且这个数大概率是在中间或者中间的旁边，而且它的左右两边都会是比它小或者比它大的数

PartSort有三种版本，这里我把它分成了PartSort1 ，PartSort2 ，PartSort3

PartSort1：hoare版本

PartSort2：挖坑法

PartSort3：前后指针法

keyi位置则代表已经排好了的位置，这时候我们再次划分区间，将keyi的左边和右边划分，再继续递归进行新一轮的部分排序选keyi，一直递归下去即可完成我们的递归

时间复杂度：O(N*logN)

空间复杂度：O(logN)（递归深度为logN）

稳定性：不稳定

具体PartSort如下：

hoare版本

int PartSort1(int* a, int left, int right)
{int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;int begin = left, end = right;while (begin < end){while (begin < end && a[end] >= a[keyi]){end--;}while (begin < end && a[begin] <= a[keyi]){begin++;}Swap(&a[begin], &a[end]);}Swap(&a[begin], &a[keyi]);return begin;
}

GetMidi属于快速排序优化，下面有解释，暂不考虑

该函数需要传一个指针，和一段区间 [left，right]

首先选定一个keyi（下标），这个下标对应数组中的值则为key

然后给定两个下标，记作begin和end，一个指向左，一个指向右

我们需要做的是先从右边开始（end），它找比key还要小的数字，左边（begin）找比key还要大的数字，找到之后将它们交换（升序）

若是begin和end相遇，则该位置则为key的最终位置（因为大的已经放到了右边，小的已经放到了左边）将key和相遇位置交换即可

我们必须要从右边开始找小，然后再从左边找大，因为这样才能保证最终位置是比key要小的，这样才能将相遇位置的值换到左边，保证了keyi位置左边都比key小，右边都比key大

最后我们返回key的位置即可

挖坑法

int PartSort2(int* a, int left, int right)
{int mid = GetMidi(a, left, right);Swap(&a[mid], &a[left]);int hole = left;//key记录挖坑位置的值int key = a[hole];while (left < right){while (left < right && a[right] >= key)right--;a[hole] = a[right];hole = right;while (left < right && a[left] <= key)left++;a[hole] = a[left];hole = left;}a[hole] = key;return hole;
}

优点是比hoare方法好理解

还是跟hoare一样先找一个keyi，但是这里是一个坑（hole）

然后一样从右边开始找小，找到后填在我们挖的这个坑里，找到小的那个地方就又变成一个坑了

接着左边找大，找到了填到坑里然后自己变成坑，以此循环往复

最后将剩下的那个坑用我们最开始挖的填上即可

前后指针法

int PartSort3(int* a, int left, int right)
{int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;int prev = left;int cur = left + 1;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur)Swap(&a[cur], &a[prev]);cur++;}Swap(&a[prev], &a[keyi]);return prev;
}

用了两个指针来走（下标，并不是C语言中真正意义上的指针）

在if语句中，由于是&&运算符，若cur位置的值小于keyi位置上的值，才会进行下一步的判断，那么判断++prev的时候就会让prev往前走

所以当cur位置的值小于keyi位置上的值，prev和cur同时++，否则，cur++

&&后面的条件判断其实是为了减少Swap的次数，因为相同位置的prev和cur交换并没有任何意义

最后让prev和keyi交换即可

三个方法选其一即可

本人认为hoare版本可能效率比其他的高一丢丢，挖坑好理解，前后指针代码简洁

快速排序优化

三数取中法

前面的hoare，挖坑，前后指针都使用了GetMini函数，它是可以增加快排的效率的

设想一下，若是一个数组里面的值全是2，已有序，但我们不知情的情况下使用了快排来进行排序会发生什么？

这时候快排的效率会变得极低，时间复杂度变成O(N^2)

这是快排比较难受的一点，主要原因就是因为我们的keyi每次都是在最左边，从而无法划分左右区间进行递归，这样自然效率就很低

所以就其核心，我们要尽量让keyi的位置尽量在中间，那么就需要用到三数取中法

int GetMidi(int* a, int left, int right)
{int midi = (left + right) / 2;if (a[left] < a[midi]){if (a[midi] < a[right]){return midi;}else if (a[left] < a[right]){return right;}else{return left;}}else{if (a[midi] > a[right]){return midi;}else if (a[left] < a[right]){return left;}else{return right;}}
}

这段代码看起来很长，但其实很简单易懂

就是先取到这段区间的中间值midi，用a[left]，a[right]，a[midi]三个值进行比较，取出大小在中间的那个即可，即使它不是整段区间的最中间的那个，但至少不是最差的那个

小区间优化

其实在数据很大的时候，我们这样递归下去的时间才会很快，若是数据量比较小的情况下我们还要递归很多的数据非常的划不来

所以我们可以制定一个标准值，当这段区间到达这个标准值时就不让它递归了，而是直接使用其他的排序来完成这段的排序（这里直接使用插入排序）

void QuickSort(int* a, int left, int right)
{if (left >= right)return;if (right - left + 1 <= 10){InsertSort(a, right - left + 1);}else{int keyi = PartSort1(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);}
}

快速排序非递归

这里是需要引入我们之前已经写好的栈和队列进来，才能完成我们下面的非递归方法

栈版本

void QuickSortNonR1(int* a, int left, int right)
{Stack st;StackInit(&st);StackPush(&st, right);StackPush(&st, left);while (!StackEmpty(&st)){int begin = StackTop(&st);StackPop(&st);int end = StackTop(&st);StackPop(&st);int keyi = PartSort1(a, begin, end);if (keyi + 1 < end){StackPush(&st, end);StackPush(&st, keyi + 1);}if (keyi - 1 > begin){StackPush(&st, keyi - 1);StackPush(&st, begin);}}StackDestroy(&st);
}

我们可以用一个栈来模拟递归的过程

快排是以一个keyi为基准，划分两段区间从而进行排序，那么我们可以在每次PartSort选出keyi之后将区间入栈，下一轮需要的时候就可以直接出栈

首先我们先将最开始的左右区间入栈

先入的右区间，这样下面取出来的时候可以先取出左再取右

接下来拿到begin和end，对这段区间进行PartSort选出keyi

选出了keyi后又划分出了区间，我们再次将这两个区间入栈

以此往复，就模拟实现了递归的快速排序

最后不要忘记了将栈销毁放置内存泄漏

队列版本

void QuickSortNonR2(int* a, int left, int right)
{Queue q;QueueInit(&q);QueuePush(&q, left);QueuePush(&q, right);while (!QueueEmpty(&q)){int begin = QueueFront(&q);QueuePop(&q);int end = QueueFront(&q);QueuePop(&q);int keyi = PartSort1(a, begin, end);if (begin < keyi){QueuePush(&q, begin);QueuePush(&q, keyi - 1);}if (end > keyi){QueuePush(&q, keyi + 1);QueuePush(&q, end);}}QueueDestroy(&q);
}

和上面的栈版本类似

都是先入一段区间，拿到这段区间的begin和end，然后进行PartSort选出keyi，接着入两段区间继续PartSort

最后也是不要忘记了将队列释放掉即可

栈版本和队列版本最主要的区别就是一个是深度优先一个是广度优先

栈是深度，队列是广度

栈是先将最开始的[left, keyi - 1]排好，再排[keyi + 1, end]

而队列是[left, keyi - 1]和[keyi + 1, end]同时往下排

归并排序

void _MergeSort(int* a, int* tmp, int begin, int end)
{if (begin >= end)return;int mid = (begin + end) / 2;int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;_MergeSort(a, tmp, begin1, end1);_MergeSort(a, tmp, begin2, end2);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++];}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("mallloc fail");return;}_MergeSort(a, tmp, 0, n - 1);free(tmp);
}

归并排序的算法采用的是分治法，它需要开一段长度和排序数组已有大小的空间来配合完成排序

它的思想是：将已有的子序列合并，得到完全有序的序列

先让将数组中的值采用”分治“，分到有序的时候（一个数也算有序），再回到上一次分治的时候将其变成有序，以此类推一直往上到最开始完整的区间即可

这个不断解决子问题的问题当然是用递归解决好了

”分“过程

”治“过程

在MergeSort中，我们需要先开一段长度为n的空间，将其传给_MergeSort函数来配合这块空间递归完成排序

MergeSort中就三个步骤，一开空间，二排序，三释放

在这个子函数_MergeSort中，我们也要传左区间和右区间

下面来进入子函数中看看

我们先定义几个变量，即将该数组[left，right]再次分成两个区间，由中间值mid来划分，分别标记为begin1，end1，begin2，end2

这里的end1必须为mid，不能是mid+1

begin2只能是mid+1，不能是mid

也就是end1必须为偶数，否则该排序会出问题

若按照错误方法来：例如：begin = 0，end = 3，那么mid = 1，begin1 = 0，end1 = 2，递归左右区间为[0，2]也就是begin = 0，end = 2，那么mid = 1，begin1 = 0，end1 = 2，这样又递归就会出现栈溢出的情况，所以必须要按照上面代码的方式走

我们需要取递归它的左右区间，从小问题开始解决

递归需要有个结束条件，那就是当这个区间不存在时结束递归

我们归并下来后按循环走，将两个小区间中最小的值放到我们前面传的tmp数组里然后i++，然后找第二小的，找到接着放进tmp数组第i个位置，i++循环往复

第一个循环走完其中某一个数组中的元素也就全部被拷贝进了tmp数组里，这时候我们只需要找到还没有全部走完的数组将其全部放到tmp数字第i个位置的后面即可

i必须从begin开始，不能是0

最后用memcpy函数将tmp数组中的值全部拷贝到a数组中即可

这样我们递归版本的归并排序就完成了

时间复杂度：O(N*logN)

空间复杂度：O(N)

稳定性：稳定

归并排序的缺点在于需要O(N)的空间复杂度

归并排序的使用更多的是使用在磁盘中的外排序问题，也就是当一个文件比较大我们的一个程序不足以支撑使用如此之多的数据来排序，那么这时候就可以使用归并排序分治

归并排序非递归

void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap){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 j = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));}gap *= 2;}free(tmp);
}

非递归相比于递归的好处就是不怕栈溢出的风险

大体思路和前面递归版本的归并排序一样

我们需要先开一段空间

下面我们要开始模拟递归的过程

我们定义了一个gap，这个gap是每组的间隔，模拟了从最开始的两个数据排序，这个gap我们从1开始到布满整个数组为止停止循环，这就是第一个while

下面的for循环就是为了完成每一组的排序

for循环下面的内容当然就是单组的排序了

还是和前面一样，先定义好左右区间

这里也是和上面的递归版本一样

将小的数放到tmp数组中，当第一个循环走完再去找没走完的那个区间，将剩余数据一个个放到tmp数组中即可

最后再将tmp数组中的数据全部拷贝到a数组中即完成单趟排序

for循环走完后也就代表这一趟间隔gap为1的已经走完了，也就是两个数据已经有序了，那么要到四个数据开始排序

所以不要忘了gap *= 2

以此类推，当gap >= n时就代表已经走完了

所以循环结束条件为gap < n

但是如果只做到这里是还没有完成排序的，它只能完成2^n个数据的排序，这里分区间的时候会存在越界的情况，所以当数据不为2^n个数时，我们需要调整区间

这里的越界只有两种情况，一种是end2越界，一种是begin2和end2都越界

若begin2和end2都越界了，那么这躺排序已经不需要右区间，而左区间本身就有序，所以我们直接break即可

若只有end2越界，那么[begin2，end2]中是还存在数据需要我们排序的，我们不能直接break，只需让end2等于数组最大下标即可

最后不能忘记了释放掉tmp数组，防止内存泄漏

这样非递归版本的归并排序就完成了

计数排序

void CountSort(int* a, int n)
{int max = a[0], min = a[0];for (int i = 1; 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*)calloc(range, sizeof(int));for (int i = 0; i < n; i++){count[a[i] - min]++;}int j = 0;for (int i = 0; i < n; i++){while (count[i]--){a[j++] = i + min;}}free(count);
}

计数排序又称鸽巢原理，它的思想本质是哈希

哈希的思想就是让某一个数据与其存储位置产生某种联系

计数排序里就采用了这种思想，它会对我们给的数组的每一个值用另一个数组的下标来计数

例如：5，5，3，6，那么另一个数组count取到的值count[3] = 1，count[5] = 2，count[6] = 1