还在为只会冒泡排序而发愁吗?排序算法万字超基础详解,带你走进不同的排序思维(三种基础排序算法+四种进阶排序算法)
还在为只会冒泡排序而发愁吗?排序算法万字超基础详解,带你走进不同的排序思维(三种基础排序算法+四种进阶排序算法)
一.插入排序
1.概念介绍
插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，直到整个数组有序。 插入排序的基本步骤如下：
- 将待排序的数组分为已排序部分和未排序部分。
- 从未排序部分的第一个元素开始，将其与已排序部分的元素进行比较。
- 如果找到了合适的位置，将该元素插入到已排序部分中，使已排序部分保持有序。
- 重复步骤 2 和 3，直到整个数组都被排序。
插入排序的时间复杂度为O(n^2)，空间复杂度为O(1)。在数据规模较小或基本有序的情况下，插入排序的性能较好。但对于大规模数据，其效率可能较低。
2.动态+静态解析
?
随机给定一个乱序数组 4 5 9 2 8 6 3 7 6 1 那么对于单趟排序,我们可以给定一个end变量,这是我们将下标为end+1的元素赋给一个变量tmp,比较aend和aend+1之间的大小,如果满足某种关系就让aend覆盖aend+1,然后把变量tmp回填 那么对于这个乱序数组我们演示一下,排成升序数组 第一次end指向4 4 5 9 2 8 6 3 7 6 1 e 不用交换,跳出循环 第二次end指向5 4 5 9 2 8 6 3 7 6 1 e 5和9不用交换,跳出循环 第三次end指向9 4 5 9 2 8 6 3 7 6 1 e 9和2交换(实质是吧变量2给tmp,然后9覆盖2,tmp再回填) 4 5 2 9 6 3 7 6 1 e 然后还没有结束,此时end-- 4 5 2 9 6 3 7 6 1 e 5和2再交换 4 2 5 9 6 3 7 6 1 e 4和2再交换 2 4 5 9 6 3 7 6 1 e 此时end<0,跳出循环
3.代码实现
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;
}
}二.冒泡排序
1.概念介绍
冒泡排序（Bubble Sort）也是一种简单的排序算法。它重复地走访要排序的数列，一次比较两个数据元素，如果顺序不对则进行交换，并一直重复这样的走访操作，直到没有要交换的数据元素为止。 冒泡排序的基本步骤如下：
- 比较相邻的元素，如果顺序错误就交换它们。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。
- 在这一点上，最后的元素应该是整个数组中最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
冒泡排序的时间复杂度为O(n^2)，空间复杂度为O(1)。它在最坏情况下的性能较差，但在实际应用中对于小型数据集或简单的排序任务可能仍然有用。
2.动态+静态解析
?
给定一个乱序数组7,1,9,5,2,6,4降序排列 首先要比较相邻两个元素的大小，然后如果满足前一个数大于后一个数则交换 第一趟 7>1，交换得1,7,9,5,2,6,4 第二次1,7,9,5,2,6,4 第三次1,7,5,9,2,6,4 ....... 最后直到变为1,7,5,2,6,4,9 第二趟 直到1,5,2,6,4,7,9 以此类推 直到六趟后整个数组变为 1,2,4,5,6,7,9 至此数组有序且降序 根据以上，我们不难发现，一个长度为n的数组，最多经过n-1趟后，数组有序 每一趟最多排序n-1-i(趟数)次
3.代码示例
void bubbleSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < n - i - 1; j++)
{
if (a[j] > a[j + 1])
{
Swap(&a[j], &a[j + 1]);
}
}
}
}4.番外
那么我们不难发现其实冒泡排序和插入排序的时间复杂度都为O(n^2),但是在实际应用中插入排序的效率是要高出冒泡排序的,是因为我们的时间复杂度是基于最坏情况进行计算的,但插入排序每次基本都不是最坏情况,它的局部有序率较高,而冒泡排序每次执行基本都是最坏情况
三.选择排序
1.概念介绍
选择排序（Selection Sort）是一种简单的排序算法。它的基本思想是每次从未排序的部分中选择最小（或最大）的元素，将其与未排序部分的第一个元素交换位置，然后再对剩余的未排序部分进行选择和交换，直到整个数组都排序完成。 选择排序的基本步骤如下：
- 在未排序部分中找到最小（或最大）的元素。
- 将找到的最小（或最大）元素与未排序部分的第一个元素交换位置。
- 重复步骤 1 和 2，直到整个数组都排序完成。
选择排序的时间复杂度为O(n^2)，空间复杂度为O(1)。它在数据规模较小时表现较好，但对于大规模数据排序效率较低。
2.动态+静态解析
?
我们再随便给一个乱序数组 7 5 1 3 4 9 6 2 8 0 那么首先我们准备4个变量 begin end maxi(最大值下标) mini(最小值下标) 7 5 1 3 4 9 6 2 8 0 首先begin和end指向数组收尾, maxi和mini初始位置与begin一致 7 5 1 3 4 9 6 2 8 0 b e 遍历数组找到最大值和最小值的下标5 , 9 然后最小值与begin所指向的元素交换 最大值与end所指向的元素交换 0 5 1 3 4 7 6 2 8 9 b e 然后begin右移,end左移 0 5 1 3 4 7 6 2 8 9 b e .... 到倒数第二步的时候我们要注意 0 1 2 3 6 5 4 7 8 9 b e 此时最大值下标与begin重合,最小值下标与end重合,如果我们在进行两次交换,就相当于没换 所以我们在进行第二次交换的时候要判断,如果最大值下标与begin重合,那么就用最小值下标覆盖即可
3.代码示例
void selectSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
int maxi = begin;
int mini = begin;
for (int i = begin + 1; i <= end; i++)
{
if (a[mini] > a[i])
mini = i;
if (a[maxi] < a[i])
maxi = i;
}
Swap(&a[mini], &a[begin]);
if (maxi == begin)
maxi = mini;
Swap(&a[maxi], &a[end]);
begin++;
end--;
}
}四.希尔排序
1.概念介绍
希尔排序（Shell's Sort）是插入排序的一种，又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。该方法由D.L.Shell于1959年提出，因此得名希尔排序。 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
2.动态+静态解析
?
其实希尔排序也可以说是对插入排序的一种升华,我们有提到插入排序的效率师大于冒泡排序的因为它有较好的局部有序,那么希尔排序就是对这一优势的放大 将一个乱序数组分为N组,每组中每个元素的间隔为gap 7 5 1 3 4 9 6 2 8 0 假设gap为3 我们就可以把这个乱序数组分为3组 7 3 6 5 4 2 1 9 8 0 最后多余的数可以放在最后一组 那么希尔排序的思想就是我们先让这三组数据有序(利用插入排序的思想) 3 6 7 2 4 5 0 1 8 9 那么最后整体再来一次插入排序,即可使整个数组有序 因为此时数组的局部有序率极高,所以最后一次插入排序的时间复杂度很低
3.代码示例
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;
}
}
}4.番外
那么我们看完希尔排序的思路后一定会有两种疑问 1.希尔排序的时间复杂度是多少? 希尔排序的时间复杂度至今为止并没有给出完整的理论证明,只是基于统计学以及大量的试验,学者发现希尔排序的时间复杂度曲线与O(n^1.3)较为接近,而现在大部分人在计算希尔排序的时间复杂度的时候,会将其粗略的记为O(nlogn),但其实两者的差距不是那么明显,不过前者是要略大于后者 2.gap到底取多少更合适? 同样对于gap的最优取值,依旧没有理论支撑,有两种方法,第一种gap初始化为n,每次循环取其一半,也就是gap /= 2,这样最后一次循环gap正好为1,可以进行一次完整的插入排序 第二种方法令gap为n, 每次取其三分之一,也就是gap = gap/3, 但是这种方法最后一次循环不一定为1,所以要写成gap= gap/3+1 这两种方法谁的效率更高并没有理论证明,但是大量实验表明,第二种方法的效率优于第一种
五.堆排序
1.概念介绍
堆排序（Heap Sort）是一种高效的排序算法，它利用了“二叉堆”这种数据结构来进行排序。 堆是一种特殊的树状结构，分为最大堆和最小堆。在最大堆中，每个父节点的值都大于或等于其子节点的值；而在最小堆中，每个父节点的值都小于或等于其子节点的值。 堆排序的基本思想是：将待排序的序列构建成一个最大堆，然后将最大值（即堆的根节点）与序列的最后一个元素交换位置，并将剩余元素重新构建为一个最大堆。重复这个过程，直到整个序列有序。 堆排序的时间复杂度为 O(n \log n)，空间复杂度为 O(1)。它是一种不稳定的排序算法，适用于排序整数、浮点数或其他可比较的数据类型。 堆排序的优点包括：时间复杂度较低：堆排序的时间复杂度为 O(n \log n)，在平均情况下比其他一些排序算法（如冒泡排序、插入排序）快得多。 空间复杂度低：堆排序的空间复杂度为 O(1)，它不需要额外的存储空间来保存排序后的结果，只使用了固定的辅助空间。 适用于大型数据集：堆排序可以有效地处理大型数据集，因为它的时间复杂度和空间复杂度都比较低。堆排序的缺点包括： 不稳定：堆排序是一种不稳定的排序算法，这意味着在排序过程中可能会改变相同值元素的相对顺序。 难以理解和实现：堆排序的概念和操作相对复杂，对于初学者来说可能比较难以理解和实现。总的来说，堆排序是一种高效的排序算法，但在选择排序算法时需要根据具体情况考虑其优缺点。如果对排序的稳定性要求较高，则可能需要选择其他排序算法。 堆排序的平均性能为O(nlogn)。它的时间复杂度和空间复杂度都比较低，适用于排序整数、浮点数或其他可比较的数据类型。在最坏情况下，堆排序的时间复杂度为O(nlog2n)。因此，堆排序的平均性能较接近于最坏性能。
2.静态解析
这里我们采用向下调整法 比如这里有一个大堆,要把它排成升序数组 7 4 5 1 4 3 s 首尾交换,把大数据放后面 3 4 5 1 4 7 s 让后向下调整,把下一个大数据调到堆顶 5 4 3 1 4 7 s 首尾交换,把大数据放后面 4 4 3 1 5 7 s 1 4 3 4 5 7 s 4 1 3 4 5 7 s 3 1 4 4 5 7 s 1 3 4 4 5 7 s
3.代码示例
void adjustDown(int* a, int parent, int n)
{
int children = 2 * parent + 1;
while (children < n)
{
if (children + 1 < n && a[children] < a[children + 1])
children++;
if (a[parent] < a[children])
{
Swap(&a[parent], &a[children]);
parent = children;
children = 2 * parent + 1;
}
else break;
}
}
void heapSort(int* a, int n)
{
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
adjustDown(a, i, n);
}
printArray(a, 10);
int end = n;
while (end > 0)
{
Swap(&a[end - 1], &a[0]);
end--;
adjustDown(a, 0, end);
}
}六.快速排序
1.概念介绍
快速排序（Quick Sort）是一种分治的排序算法。它通过选择一个基准元素，将数组分成两部分，一部分的元素都比基准小，另一部分的元素都比基准大，然后对这两部分分别进行排序，最后合并两部分得到排序后的数组。 快速排序的基本思想是：
- 选择一个基准元素（通常是数组的第一个元素或随机元素）。
- 将数组中比基准小的元素放在基准的左边，比基准大的元素放在基准的右边。
- 对基准左边和右边的子数组分别进行快速排序。
- 重复步骤 1-3，直到子数组的规模为 1 或 0。
快速排序的时间复杂度在平均情况下为O(nlogn)，空间复杂度为O(logn)。它是一种高效的排序算法，但在最坏情况下可能退化为O(n^2)。
2.动态+静态解析
?
2.1霍尔法
给定一个基准值下标key,一般是0 然后定义左右两个指针left = 0, right = n-1 7 4 5 1 4 3 l r 让右指针先走找到一个比key小的值,然后再让左指针走,找到一个比key大的值,然后让aleft与aright交换 7 4 5 1 4 3 lr 如果两指针相遇,则让相遇处的元素与基准值交换 3 4 5 1 4 7 lr 这时我们就能保证比基准值大就在基准值右侧,反之在左侧 然后我们把除了基准值的分成左右两部分 3 4 5 1 4 和 空 如果该部分为空或只有一个元素则返回,否则递归 3 4 5 1 4 l r 1 3 5 4 4 lr 1 和 5 4 4 5 4 4 lr 4 4 5 lr ......
2.2挖坑法
给定一个乱序数组: 5 2 7 3 1 4 8 6 L R 找一个基准数,假设为5,拿出来, 5 2 7 3 1 4 8 6 L R 先让R走,直到找到比5小的数, 2 7 3 1 4 8 6 L R 交换, 4 2 7 3 1 8 6 L R 然后L走, 4 2 7 3 1 8 6 L R 直到找到比5大的数, 4 2 7 3 1 8 6 L R 交换, 4 2 3 1 7 8 6 L R 重复, 4 2 1 3 7 8 6 LR 直到LR相遇,将基准数填到相遇处。 4 2 1 3 5 7 8 6 LR 分成左右两部分,再分别将左右两部分按上述方法排序， 4 2 1 3 L R 3 2 1?developer/article/2404662/undefined LR 3 2 1 4 LR 3 2 1 L R ...... 直到仅剩一个数无法在分组。 右边同理。
2.3前后指针法
给定一个乱序数组: 5 2 7 3 1 4 8 6 P C 定义前后两个指针,设定一个基准值,下标为key 如果C指向的元素比key指向的元素小且P的下一位不是C(这样可以保证基准值先开始不会参与交换),就和P交换,然后P向右走 5 2 7 3 1 4 8 6 P C 然后让cur一直向右走直到遍历完 5 2 7 3 1 4 8 6 PC 5 2 7 3 1 4 8 6 P C 5 2 3 7 1 4 8 6 P C 5 2 3 1 7 4 8 6 P C 5 2 3 1 4 7 8 6 P C 5 2 3 1 4 7 8 6 P C 4 2 3 1 5 7 8 6 P C
3.代码实现
3.1霍尔法
void quickSortByHoare(int* a, int begin, int end)
{
if (begin >= end)
return;
int left = begin;
int right = end;
//三数取中法取key
int key = Midi(a, left, right);
Swap(&a[left], &a[key]);
while (left < right)
{
while (left < right && a[right] >= a[key])
right--;
while (left < right && a[left] <= a[key])
left++;
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[key]);
key = left;
quickSortByHoare(a, 0, key - 1);
quickSortByHoare(a, key + 1, end);
}3.2挖坑法
void quickSortByDigging(int* a, int begin, int end)
{
if (begin >= end)
return;
int left = begin;
int right = end;
int key = left;
int tmp = a[key];
while (left < right)
{
while (left < right && a[key] <= a[right])
right--;
if (left < right)
a[left] = a[right];
while (left < right && a[key] >= a[left])
left++;
if (left < right)
a[right] = a[left];
}
a[left] = tmp;
key = left;
quickSortByDigging(a, 0, key - 1);
quickSortByDigging(a, key + 1, end);
}3.3前后指针法
void quickSortByPoints(int* a, int begin, int end)
{
if (begin >= end)
return;
int prev = begin;
int cur = prev + 1;
int key = begin;
while (cur <= end)
{
if (a[cur] < a[key] && ++prev != cur)
Swap(&a[cur], &a[prev]);
cur++;
}
Swap(&a[prev], &a[key]);
key = prev;
quickSortByPoints(a, 0, key - 1);
quickSortByPoints(a, key + 1, end);
}4.思路优化
4.1key的优化
把快速排序看成一个二叉树结构,树的高度一般为logN,时间复杂度为O(NlogN)
但对于一个有序数列或接近于有序的数列,key如果每次都取最左边或最右边.那么树的高度就会接近于N,时间复杂度就会变为O(N^2),这时快速排序的效率会大大减少,那么归根结底还是key的取法有问题,所以下面我们针对key的取法进行优化
4.1.1随机数取key
int key = rand() % (right - left);
key += left;4.1.2三数取中法
int Midi(int* a, int left, int right)
{
int mid = (left + right) / 2;
if (a[left] < a[mid])
{
if (a[mid] < a[right])
return mid;
else if (a[left] < a[right])
return right;
else return left;
}
else
{
if (right < a[mid])
return mid;
else if (a[left] < a[right])
return left;
else return right;
}
}4.2递归的优化
我们都知道递归需要频繁的创建函数栈帧,那么如果递归深度太高就有可能导致栈溢出,而操作系统提供给我们的栈的大小大约为8000000字节,所以我们可以考虑自己建一个栈来实现递归的效果
不会手撕栈的可以看我这篇文章/developer/article/2395516
void quickSortByStack(int* a, int begin, int end)
{
Stack st;
initStack(&st);
pushStack(&st, end);
pushStack(&st, begin);
while (!isEmpty(&st))
{
int left = topStack(&st);
popStack(&st);
int right = topStack(&st);
popStack(&st);
int prev = left;
int cur = prev + 1;
int key = left;
while (cur <= right)
{
if (a[cur] < a[key])
Swap(&a[cur], &a[prev]);
cur++;
}
Swap(&a[prev], &a[key]);
key = prev;
//left, key - 1 key key + 1, right
if (left < key - 1)
{
pushStack(&st, key - 1);
pushStack(&st, left);
}
if (key + 1 < right)
{
pushStack(&st, right);
pushStack(&st, key + 1);
}
}
destroyStack(&st);
}七.归并排序
1.概念介绍
归并排序（Merge sort）是建立在归并操作上的一种有效、稳定的排序算法，该算法是采用分治法(Divide and Conquer）的一个非常典型的应用。 以下是归并排序的基本思想：
- 分解：将待排序的序列分成两个子序列。
- 排序：分别对两个子序列进行排序。
- 合并：将排好序的子序列合并成一个有序序列。
归并排序的过程可以通过递归的方式实现。下面是归并排序的递归算法实现步骤：
- 基本情况：如果待排序的序列长度为 1 或 0，则该序列已经是有序的。
- 分解：将序列分解成两个子序列，一般取中间位置为分界点。
- 递归调用：对两个子序列分别进行归并排序。
- 合并：将两个排好序的子序列合并成一个有序序列。合并的过程是将两个子序列中的元素两两比较，按照顺序将它们放入新的序列中。
归并排序的时间复杂度为 O(nlogn)，空间复杂度为 O(n)。它的优点是稳定且效率高，在各种排序算法中表现优异。但由于需要额外的存储空间来存放中间结果，所以在空间复杂度上相对较高。
2.动态解析+静态解析
2.1递归法
- 创建一个临时数组，在临时数组中进行归并，防止归并时将原顺序打乱，整体归并完之后再将数据拷贝回原数组。
- 将区间划分为begin , mid 两段子区间，进行后序遍历递归，当划分到只有一个元素时返回。
- 进行归并。使用begin1和end1控制左区间，begin2和end2控制右区间，比较两个区间中的值将其插入到temp数组中，当其中一个区间归并结束时停止。
- 将未排完序的数组接着全放入temp数组中。
- 最后将temp中的值拷贝到原数组中。
2.2非递归法
- 模拟最后一层递归中排列间距为1的子序列，例0,0和1,1……，即最后一层的归并，然后再进行间距为2的子序列,直到归并完成;
- 寻找规律推出左、右区间的公式: i , i+gap-1,然后就是正常的递归合并.
- i 的变化是i+=2*gap,表示每次跳过两个区间,进入下一段区间.
- 当gap每次*=2 , 表示进入了下一层递归 , 直到gap >= n 时停止.
- 将临时数组拷贝回原数组.
3.代码实现
3.1递归法
void _MergeSort(int* a, int begin, int end, int* temp)
{
if (begin >= end)
return;
//将区间分为左右两半
int mid = (begin + end) / 2;
//[begin,end]--->[begin , mid ] [mid+1,end]
//开始递归拆开
_MergeSort(a, begin, mid, temp);
_MergeSort(a, mid+1, end, temp);
//合并
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
//i要从相对位置起
int i = begin1;
//如果两个区间有一个结束，就停止比较归并
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
temp[i++] = a[begin1++];
}
else
{
temp[i++] = a[begin2++];
}
}
//使用两个while将未归并完的数组进行追加
while (begin1 <= end1)
{
temp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
temp[i++] = a[begin2++];
}
//拷贝回去要使用相对位置
memcpy(a+begin, temp+begin, (end-begin+1)*sizeof(int));
}
void MergeSort(int* a, int n)
{
int* temp = (int*)malloc(sizeof(int) * n);
//使用一个子函数进行排序
_MergeSort(a, 0, n - 1, temp);
free(temp);
}3.2非递归法
void MergeSortNonR(int* a, int n)
{
int* temp = (int*)malloc(sizeof(int) * n);
int gap = 1;
//i 是要两组两组的跳过
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;
//i要从相对位置起
int j = begin1;
//如果两个区间有一个结束，就停止比较归并
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
temp[j++] = a[begin1++];
}
else
{
temp[j++] = a[begin2++];
}
}
while (begin1 <= end1)
{
temp[j++] = a[begin1++];
}
while (begin2 <= end2)
{
temp[j++] = a[begin2++];
}
}
memcpy(a, temp, n * sizeof(int));
gap *= 2;
}
}