照片网站源码,腾讯有做淘宝客网站吗,iis7 添加网站,创意作品文章目录 六大比较类排序算法#xff08;插入排序、选择排序、冒泡排序、希尔排序、快速排序、归并排序#xff09;前言1. 插入排序算法描述代码示例算法分析 2. 选择排序算法描述优化代码示例算法分析 3. 冒泡排序算法描述代码示例算法分析与插入排序对比 4. 希尔排序算法描… 文章目录 六大比较类排序算法插入排序、选择排序、冒泡排序、希尔排序、快速排序、归并排序前言1. 插入排序算法描述代码示例算法分析 2. 选择排序算法描述优化代码示例算法分析 3. 冒泡排序算法描述代码示例算法分析与插入排序对比 4. 希尔排序算法描述代码示例算法分析 5. 快速排序5.1 挖坑法算法描述单轮操作代码示例算法分析优化三数取中小区间优化 5.2 左右指针法算法描述代码示例 5.3 前后指针法算法描述代码示例 6. 归并排序算法描述代码示例 总结对比 六大比较类排序算法插入排序、选择排序、冒泡排序、希尔排序、快速排序、归并排序
前言 排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减地排列起来地操作。 稳定性假定在待排序地记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i] r[j]且 r[i] 在 r[j] 之前而在排序后的序列中。r[i] 仍在 r[j] 之前。则称这种排序算法是稳定的。否则称为不稳定的。 内部排序数据元素全部放在内存中的排序。我们下面讲的排序都是属于内部排序 外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。 1. 插入排序 算法描述 直接插入排序是一种简单的插入排序法其基本思想是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列。 插入排序的原理很好理解打过扑克牌的人应该都能懂这种思想。 当我们在插入第 i (i1) 个元素时前面的 array[0], array[1],…, array[i-1] 已经排好序初始时已排序部分只包含第一个元素未排序部分包含剩余元素此时用 array[i] 的排序码依次与它前面的 array[i-1], array[i-2],… 的排序码顺序进行比较找到插入位置时就就将 array[i] 插入。原来位置上的元素顺序后移一位。 下面是动图演示 代码示例
// 插入排序
void InsertSort(int* a, int n) { // n表示数组的大小for (int i 0; i n - 1; i) {int end i; int tmp a[end 1]; // 待排序元素while (end 0) {if (a[end] tmp) { // 依次向前比较a[end 1] a[end]; // 向后移移位--end;}else { break;}}a[end 1] tmp; // 插入操作}
}算法分析 元素集合越接近有序直接插入排序算法的时间复杂度效率越高 时间复杂度 O ( N 2 ) O(N^2) O(N2) 最坏情况下为 O ( N 2 ) O(N^2) O(N2)此时待排序列为逆序或者说接近逆序 最好情况下为 O ( N ) O(N) O(N)此时待排序列为升序或者说接近升序。 空间复杂度 O ( 1 ) O(1) O(1) 稳定性稳定 2. 选择排序 算法描述 选择排序的基本思想是每次从待排序列中选出一个最小值或最大值然后放在序列的起始或末尾位置直到全部待排数据排完即可。 下面是动图演示 优化 实际上我们可以一趟选出两个值一个最大值一个最小值然后将其放在序列开头和末尾这样可以使选择排序的效率快一倍。 代码示例
void SelectSort(int* a, int n) {int begin 0, end n - 1; // 保存开头和末尾的下标while (begin end) {int mini begin, maxi begin; // 记录区间内最小值和最大值的下标for (int i begin; i end; i) { // 该循环用于找到区间内的最大和最小值if (a[i] a[mini]) {mini i; }if (a[i] a[maxi]) {maxi i;}}// Swap函数在外部需要自己写一下Swap(a[begin], a[mini]); // 把最小的放在开头Swap(a[end], a[maxi]); // 把最大的放在末尾begin;--end;}
}这就完了吗当然没有还有一点小瑕疵我们来看这两行
Swap(a[begin], a[mini]); // 把最小的放在开头
Swap(a[end], a[maxi]); // 把最大的放在末尾这里万一我最大的数就是开头的数呢就有可能在第一次交换的时候和最小值交换走那么下一行交换的时候 a[maxi] 就不是最大值了所以在第一次交换的时候我们需要判断一下 begin 和 maxi 的位置是否重叠。完整代码如下
void SelectSort(int* a, int n) {int begin 0, end n - 1;while (begin end) {int mini begin, maxi begin;for (int i begin; i end; i) {if (a[i] a[mini]) {mini i;}if (a[i] a[maxi]) {maxi i;}}Swap(a[begin], a[mini]); // 把最小的放在开头// 如果 begin 和 maxi 的位置重叠maxi 的位置要修正一下if (begin maxi) {maxi mini; // 也就是说值换了那么对应的下标也得改}Swap(a[end], a[maxi]); // 把最大的放在末尾begin;--end;}
}算法分析 时间复杂度最坏情况 O ( N 2 ) O(N^2) O(N2) 最好情况 O ( N 2 ) O(N^2) O(N2) 空间复杂度 O ( 1 ) O(1) O(1) 稳定性不稳定 3. 冒泡排序 算法描述 冒泡排序通过比较相邻的元素并交换它们的位置来实现排序。即从列表的第一个元素开始比较相邻的两个元素。如果前一个元素比后一个元素大则交换它们的位置。对列表中的每一对相邻元素重复上述步骤直到列表的末尾。这样最大的元素会被 “冒泡” 到列表的最后。忽略已经排序好的最后一个元素重复上述步骤直到整个列表排序完成。 下面是动图演示 代码示例
void BubbleSort(int* a, int n) {for (int i 0; i n - 1; i) {int flag 0;for (int j 1; j n - i; j) {if (a[j - 1] a[j]) {Swap(a[j - 1], a[j]); // 前面比后面大就交换flag 1;}}// 没有发生交换说明已经有序不需要再比较了if (flag 0) {break;}}
}算法分析 时间复杂度最坏情况 O ( N 2 ) O(N^2) O(N2) 最好情况 O ( N ) O(N) O(N)通过设置一个变量 flag 来实现) 空间复杂度 O ( 1 ) O(1) O(1) 稳定性稳定 与插入排序对比 当一个数组很接近有序的时候比如 [1, 2, 3, 5, 4, 6] 这个时候采用插入排序循环的执行次数只需要 N N N 次 而冒泡排序需要 ( N − 1 ) ( N − 2 ) (N-1)(N-2) (N−1)(N−2) 次。可见对于接近有序的数组插入排序比冒泡排序的局部适应性更强。 4. 希尔排序 算法描述 希尔排序又称缩小增量法它的基本思想是将待排序的元素分为多个子序列然后对每个子序列进行插入排序。这些子序列是原始序列中相隔一定增量的元素组成的。然后逐渐减小增量重复这个过程最终将增量减小到 1完成最后一轮的插入排序此时序列已经基本有序只需进行少量的比较和交换操作大大提高了排序效率。 也就是说我们需要指定一个 gap间隔从第一个数开始每各一个这个 gap 的距离直到最后的这些数为一组在同一个组内的数它们进行插入排序的操作。然后进行了这一轮 “预排序” 之后再逐渐缩小这个 gap直到 gap 为 1最后这个数组就有序了。而我们会发现
gap 越大大的数可以越快地到后面小的数可以越快地到前面。但是这样预排序完数组也越不接近有序。gap 越小排完之后地数组越接近有序。特别地当 gap 为 1 的时候这就变成了一个普通的插入排序。
而刚刚我们也提到过说插入排序对接近有序的数组它的效率就越高那么这个希尔排序就可以看作是插入排序的升级版它通过设置一个 gap 先预排序让数组接近有序然后再插入排序这样就能提高效率。
还有一个问题这个 gap 到底该怎么设计呢通常我们可以让初始的 gap 设置为数组长度的一半这样会更好然后每次预排序完之后让 gap 整除 2或者 3 也不是不行但最后都要保证 gap 能到 1因为这样最后排完的数组才能够是有序的。
下面是它的动图演示 代码示例
void ShellSort(int* a, int n) {int gap n; // 一开始设置成n这样一进循环就是长度的一半了while (gap 1) {gap / 2; // 可以保证 gap 最后一次为 1// gap / 3 1; // gap 整除 3 不一定能到 1所以要加 1// 把间隔为 gap 的同时排for (int i 0; i n - gap; i) {int end i;int tmp a[end gap];while (end 0) {if (a[end] tmp) {a[end gap] a[end];end - gap;}else {break;}}a[end gap] tmp;}}
}算法分析 希尔排序实际上是直接插入排序的优化 先进行预排序让数组接近有序直接插入插入排序 当 gap 1 时都是预排序让数组接近有序。 当 gap 1 时就是直接插入排序。 时间复杂度 第一层的 while 循环时间复杂度 O ( l o g 2 N ) O(log_2N) O(log2N) 或者 O ( l o g 3 N ) O(log_3N) O(log3N)。 第二层的 for 循环当 gap 很大时下面的预排序时间复杂度 O ( N ) O(N) O(N)当 gap 很小时数组已经接近有序了这时候差不多也是 O ( n ) O(n) O(n)。 综合计算有数据得出平均的时间复杂度为 O ( N 1.3 ) O(N^{1.3}) O(N1.3) 空间复杂度 O ( 1 ) O(1) O(1)稳定性不稳定 5. 快速排序 快速排序的基本思想是选择一个基准元素将数组划分为两个子数组比基准元素小的元素放在左边比基准元素大的元素放在右边然后分别对左右子数组进行排序最终实现整个数组的有序排列。 而实现上面所说的操作我们可以有以下几种方法 5.1 挖坑法 算法描述 我们把数组的最左边的数看作为一个 “坑位”把这个值保存在一个变量 key 中。 定义两个变量 left 和 right 起始位置分别是数组的开头和结尾这个时候最左边的 left 就是 “坑位”。让 right 先往左走每次走一个单位去寻找比 key 更小的单位找到了就停下。 然后把这个值赋给 “坑位” 上也就是 left 对应的位置此时 right 变成新的 “坑位”。 这时再让 left 往右走去寻找比 key 更大的值找到了就停下。 然后把这个值赋给 “坑位”也就是 right 所对应的位置此时 left 形成新的 “坑位”。 再让 right 往左走…就这样循环往复直到 left 和 right 相遇此时相遇点一定是 “坑位”最后把 key 的值赋给坑位上就算完成了第一趟排序。 注意如果将最左边的数看作是 “坑位” 的话那么需要让 right 先走如果最右边的数是 “坑位” 的话那么需要最左边的数先走。 下面是动图演示 单轮操作
void PartQuickSort(int* a, int n) {int begin 0, end n - 1;int pivot begin; // 最左边的作为坑位int key a[begin]; // 将坑位上的值保存在 key 中while (begin end) {//右边找小放到左边while (begin end a[end] key) {--end;}//小的放到左边的坑自己形成了新的坑位a[pivot] a[end];pivot end;//左边找大放到右边while (begin end a[begin] key) {begin;}//大的放到右边的坑自己形成了新的坑位a[pivot] a[begin];pivot begin;}pivot begin;a[pivot] key;
}在完成第一轮操作之后我们会发现 key 的左边全是比 key 小的值而 key 的右边全是比 key 大的值。而我们要让整个数组有序我们希望 key 的左右两部分都是有序的。
这就可以用到分治的思想——去递归地调用自身让 key 的左右两个子区间进行同样的操作直到区间只有一个数或者没有了为止。这样一来 key 左右两个区间就是有序的那么整个数组就有序了。 代码示例
void QuickSort(int* a, int left, int right) { // 由于之后需要递归调用子区间所以要改一下形参if (left right) {return;} // 递归结束条件int begin left, end right;int pivot begin;int key a[begin];while (begin end) {//右边找小放到左边while (begin end a[end] key) { // 注意这里左边的条件是为了防止两变量错过--end;}//小的放到左边的坑自己形成了新的坑位a[pivot] a[end];pivot end;//左边找大放到右边while (begin end a[begin] key) {begin;}//大的放到右边的坑自己形成了新的坑位a[pivot] a[begin];pivot begin;}pivot begin;a[pivot] key;//[left, pivot - 1] pivot [pivot 1, right]QuickSort(a, left, pivot - 1); // 递归左边QuickSort(a, pivot 1, right); // 递归右边
}算法分析 时间复杂度 快速排序的时间复杂度为 O ( N l o g 2 N ) O(Nlog_2N) O(Nlog2N)其中 N N N 为待排序数组的长度。最坏情况下快速排序的时间复杂度为 O ( N 2 ) O(N^2) O(N2)但这种情况出现的概率很小可以通过一些优化措施来避免。 空间复杂度 快速排序的空间复杂度取决于递归栈的深度在最坏情况下递归栈的深度为 O ( N ) O(N) O(N)因此快速排序的空间复杂度为 O ( N ) O(N) O(N)。但是在一些实现中可以使用非递归的方式来实现快速排序从而避免递归栈带来的空间开销。 稳定性 快速排序是一种不稳定的排序算法。因为在排序过程中可能会交换相同元素的位置从而导致相同元素的相对顺序被改变。例如对于数组 [3, 2, 2, 1]如果选择第一个元素 3 作为基准元素那么经过第一次划分后数组变成了 [1, 2, 2, 3]其中两个 2 的相对顺序被改变了因此是不稳定的。 优化三数取中小区间优化
上面说到快速排序在最坏的情况下时间复杂度会下降到 O ( N 2 ) O(N^2) O(N2)那是什么时候是最坏的呢 结论快速排序在**有序不论顺序还是逆序**的情况下最坏时间复杂度为 O ( N 2 ) O(N^2) O(N2) 因为在有序的情况下这个所谓的 “坑位” 并不会移动至靠近中间的位置也就是说这样的话每次做完单趟排序的时候也只会让一个数变得有序。如下图所示 为了解决这个问题提出了一个解决方法——三数取中。
即比较左中右三个数的大小让值最中间的数作为坑这样的话就避免了坑在最左边或者最右边的极端情况。
int GetMidIndex(int* a, int left, int right) {int mid (left right) 1; // 这里是右移运算符也相当于整除2if (a[left] a[mid]) {if (a[mid] a[right]) {return mid;}else if (a[left] a[left]) {return left;}else return{return right;}}else {if (a[mid] a[right]) {return mid;}else if (a[left] a[right]) {return left;}else {return right;}}
}void QuickSort(int* a, int left, int right) {if (left right) {return;}int index GetMidIndex(a, left, right);Swap(a[left], a[index]);//...下同
}还有一种优化——小区间优化
就是说当递归的时候这个区间已经很小了这个时候再去递归调用的效率就可能比不上其他的排序方法了。这里以 10 10 10 为例当区间小于 10 10 10 的时候我们就采用直接插入排序如果区间大于 10 10 10 我们就正常递归即可。
void QuickSort(int* a, int left, int right) {//...上同//[left, pivot - 1] pivot [pivot 1, right]//QuickSort(a, left, pivot - 1);//QuickSort(a, pivot 1, right);if (pivot - 1 - left 10) {QuickSort(a, left, pivot - 1);}else {InsertSort(a left, pivot - 1 - left 1);}if (pivot - 1 - left 10) {QuickSort(a, pivot 1, right);}else {InsertSort(a pivot 1, right - (pivot 1) 1);}
}5.2 左右指针法 算法描述
同样我们可以定义数组最左边的值为 key再定义两个变量 left 和 right 起始位置分别是数组的开头和结尾右边的 right 先走去找比 key 更小的值找到了就停下。然后左边的 left 去找比 key 更大的值找到了然后停下。
这时交换 left 和 right 对应的值。
然后 right 再走…直到 left 和 right 相遇此时将相遇的位置对应的值与 key 位置的值交换。这样一来key 左边的值也都是比 key 小的右边的是比 key 大的。、 注意同样的如果定义对左边的数为 key那么右边的 right 先走反之 left 先走。 下面是动图演示 代码示例
void QuickSort2(int* a, int left, int right) {if (left right) {return;}int index GetMidIndex(a, left, right);Swap(a[left], a[index]);int begin left, end right;int keyi begin;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]);QuickSort2(a, begin, keyi - 1);QuickSort2(a, keyi 1, end);
}这个方法和挖坑法的区别就在于第一趟排序排完之后左右序列的顺序不同。 时间复杂度 O ( N l o g 2 N ) O(Nlog_2N) O(Nlog2N) 5.3 前后指针法 算法描述
还是选出一个最左边或最右边的数作为 key。定义两个变量 prev 和 cur。起始时 prev 指向开头cur 指向 prev1也就是开头的后一位。若 cur 指向的内容小于 key则 prev 向后移动一位然后交换 prev 和 cur 所指向的内容然后 cur若 cur 所指向的内容大于 key则 cur 直接 。如此进行下去直到 cur 到达 end 位置。此时 key 和 prev 所指向的内容交换即可。
这样也能使得 key 左序列的值小于 key右边序列的值大于 key。之后再递归调用即可。
下面时动图演示 代码示例
void QuickSort3(int* a, int left, int right) {if (left right) {return;}int index GetMidIndex(a, left, right);Swap(a[left], a[index]);int keyi left;int prev left, cur left 1;while (cur right) {if (a[cur] a[keyi] prev ! cur){Swap(a[prev], a[cur]);}cur;}Swap(a[prev], a[keyi]);QuickSort3(a, left, prev - 1);QuickSort3(a, prev 1, right);
}时间复杂度 O ( N l o g 2 N ) O(Nlog_2N) O(Nlog2N) 6. 归并排序 算法描述
归并排序的核心思想是将一个大问题分解成若干个小问题分别解决这些小问题然后将结果合并起来最终得到整个问题的解。具体到排序问题归并排序的步骤如下
分解将待排序的数组分成两个子数组每个子数组包含大约一半的元素。解决递归地对每个子数组进行排序。合并将两个已排序的子数组合并成一个有序的数组。
通过不断地分解和合并最终整个数组将被排序。 这样看可能不直观下面是动图演示 代码示例
注意这里需要用到两个函数因为要用到开辟新的内存所以不能用在递归中需要单独提出来。
void _MergeSort(int* a, int left, int right, int* tmp) { // 此函数用来递归if (left right) {return;}int mid (left right) 1;_MergeSort(a, left, mid, tmp);_MergeSort(a, mid 1, right, tmp);int begin1 left, end1 mid;int begin2 mid 1, end2 right;int index left;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 i left; i right; i) {a[i] tmp[i];}
}void MergeSort(int* a, int n) {int* tmp (int*)malloc(sizeof(int) * n);_MergeSort(a, 0, n - 1, tmp);free(tmp);
}时间复杂度 O ( N l o g 2 N ) O(Nlog_2N) O(Nlog2N) 稳定性稳定 总结对比
排序方法平均情况最好情况最坏情况辅助空间稳定性插入排序 O ( n 2 ) O(n^2) O(n2) O ( n ) O(n) O(n) O ( n 2 ) O(n^2) O(n2) O ( 1 ) O(1) O(1)稳定选择排序 O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2) O ( 1 ) O(1) O(1)不稳定冒泡排序 O ( n 2 ) O(n^2) O(n2) O ( n ) O(n) O(n) O ( n 2 ) O(n^2) O(n2) O ( 1 ) O(1) O(1)稳定希尔排序 O ( n log n ) O(n\operatorname{log}n) O(nlogn) ~ O ( n 2 ) O(n^2) O(n2) O ( n 1.3 ) O(n^{1.3}) O(n1.3) O ( n 2 ) O(n^2) O(n2) O ( 1 ) O(1) O(1)不稳定快速排序 O ( n log n ) O(n\operatorname{log}n) O(nlogn) O ( n log n ) O(n\operatorname{log}n) O(nlogn) O ( n 2 ) O(n^2) O(n2) O ( log n ) O(\operatorname{log}n) O(logn) ~ O ( n ) O(n) O(n)不稳定归并排序 O ( n log n ) O(n\operatorname{log}n) O(nlogn) O ( n log n ) O(n\operatorname{log}n) O(nlogn) O ( n log n ) O(n\operatorname{log}n) O(nlogn) O ( n ) O(n) O(n)稳定 注快速排序加了三数取中之后基本不会出现最坏的情况。 有任何问题还请大佬们指出
