摘要:时,数组已近接近有序。希尔排序的时间复杂度不好去计算,因为的取值方法很多,导致很难去计算。我们以冒泡排序的一次遍历为例遍历的规则是两两进行比较,如果前者大于后者就交换,否则就继续往下走。
同时 还有两个比较基础的概念:
插入排序的思想十分的简单:
把待排序的元素插入到一个 有序序列 的 正确的位置,直到所有的记录插入完全为止,得到一个新的有序序列。
其实我们在玩扑克牌的时候就是这个思想
为了能更好的理解插入排序,我们从他的一次循环看起:(以升序为例)
假设数组a为一个前(end+1)个数有序数组,我们要把第end+1个数插入数组中
循环的基本思路是: 如果a[end]比temp(待插入的数)要小,就说明还要继续往下寻找,这是执行a[end+1]=a[end]
,并将end- -,循环的条件时end >=0
直到找到比 temp要小的数 或者 end==0 时还没有找到,这时就要跳出循环执行:a[end+1]=temp
注意: 这里如果end==0
时还没有找到的时候,出循环的时候end为-1,但是a[end+1]
实际上还是第一个元素
这是直接插入排序的一次单次循环,实际上我们发现直接插入排序一个重要的前提是要有一个有序的数组。
在排序的最开始 我们可以认定第一个数为一个大小为1的有序数组,来启动上述介绍的单次循环,循环结束我们就得到了一个前两个元素有序的数组 …直到前n-1个元素(数组大小为n)有序,将最后一个元素插入,这是最后一次循环。 所以我们还要在上面单次循环的基础上在加一个循环来完成排序
代码
void InsertSort(int* a, int n){ for (int i = 0; i < n - 1; i++) { int end = i; int temp = a[i + 1]; while (end >= 0) { if (a[end] > temp) { a[end + 1] = a[end]; end--; } else break; } a[end + 1] = temp; }}
总结
O(N^2)
O(1)
希尔排序实际上是在插入排序的基础上做出了一些改进,希尔排序又叫缩小增量法。
其基本思想是:
将数组按一定间隔分成若干个组,对每个组里面的元素进行直接选择排序,然后缩小间隔,在对重新分的组挨个进行选择排序…直到最后间隔为1(实际上直接插入排序是间隔为1的希尔排序)
代码
void ShellSort(int* a, int n){ int gap = n ; while (gap > 1) { gap = gap / 3 + 1; //注意这里是以三倍的速度缩小gap,这里+1是因为要保证最后一次gap为1 for (int i = 0; i < n -gap; i++) { int end = i; int temp = a[i + gap]; while (end >= 0) { if (a[end] > temp) { a[end + gap] = a[end]; end -= gap; } else break; } a[end + gap] = temp; } }}
总结
O(N^1.25)
这是通过大量实验得到的经验公式O(1)
基本思路:
每次遍历整个数组从数组中选择出最大的数(或最小的数),最放到数组的末尾(或数组的首尾),直到全部待排序的数据元素排完
我们以一个数组为例:
void SelectSort(int* a, int n){ int begin = 0; int end = n - 1; while (begin < end) { int min = begin; int max = end; for (int i = begin+1; i < end;i++) { if (a[i] > a[max]) max = i; if (a[i] < a[min]) min = i; } swap(&a[begin], &a[min]); if (begin != max) swap(&a[end], &a[max]); else swap(&a[end], &a[min]); begin++; end--; }}
总结:
O(N^2)
O(1)
可以参考一下以前的博客:数据结构:堆 的详解
代码:
void AjustDown(int* a, int n, int parents){ int child = 2 * parents + 1; while (child < n) { if (child + 1 < n && a[child + 1] > a[child]) child++; if (a[child] > a[parents]) swap(&a[child], &a[parents]); parents = child; child = 2 * parents + 1; }}void HeapSort(int* a, int n){ for (int i = n/2-1 ; i >= 0; i--) { AjustDown(a,n,i); } for (int i = n-1; i >0 ; i--) { swap(&a[0], &a[i]); AjustDown(a, i, 0); }}
总结:
O(N*logN)
O(1)
基本思想: 就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置,在视觉上的效果像:较大键值的记录向序列的尾部移动,键值较小的记录向序列的前部移动。
[0,n-2]
,也就是n-1次比较。
看完一次循环大家或许就理解了冒泡排序名字的由来,最大的数像气泡一样向上移动,在往下思考这次遍历过后,实际上最后一个已经是有序的了,所以还要进行n-1次这样的遍历,所以时间复杂的是O((n-1)+(n-2)+(n-3)+(n-4).....+0)=O(n^2)
代码
void BubbleSort(int* a, int n){ for (int i = 0; i < n - 1; i++) { int k = 0; for (int j = 0; j < n - 1 - i; j++) //每一次遍历结束,下一次要遍历的个数都会减少一个 { if (a[j] > a[j + 1]) { int temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; k = 1; } } if (k == 0) break; }}
总结:
O(N^2)
最好情况是:O(N)
O(1)
快排的思路:
任取待排序元素序列中的某元素作为基准值,按照该基准值将排序分成两个子序列,左子序列的元素均小于基准值,右子序列的元素均大于基准值,,然后在左、右子序列重复上述过程,直到所有元素都有序为止
下面介绍快排的三个版本:
思路:
看完这个思路之后,我们直到整体思路就是,从左边找比基准值大的与右边找到的比基准值小的进行交换,但是在这里要思考清楚一个问题:
既然最后一步是将相遇的值与key的值交换,也就是说明左右相遇时指向的值一定比key小,这是为什么?
我们从两个情况去考虑:
我们以第一次循环为例:
这里我们就实现了把数组分成了两个子序列(左子序列的元素均小于基准值,右子序列的元素均大于基准值),然后我们把这两个子序列看成一个新的序列,对其指向执行相同的程序,并一直递归下去,直到 传进去的数组的 大小为 0 (没有左子序列 或 右子序列 也就是key比该序列的所有元素都要大或小) 或 1(没有执行程序的必要)。实际上执行的思路入下图所示
代码
void QuickSort1(int* a, int n) //hoare版本{ if (n == 1 || n == 0) return; int key = 0; int left = 0; //这里必须从0开始,如果从1开始,当数组只有两个的时候代码会出现问题 int right = n - 1; while (left < right) //这里必须是小于号保证出循环left一定等于right { while (left<right && a[right] > a[key]) right--; while (left<right && a[left] <= a[key]) //注意这里的大于等于号 因为key在左边,为了让key往左走必须大于等于 left++; swap(&a[left], &a[right]); } swap(&a[left], &a[key]); key = left; QuickSort1(a, key); QuickSort1(a + key + 1, n - key - 1);}
思路:
我们以一次循环作为基础:
-最后一步左右重合,将temp中的值填入坑内
代码
void QuickSort2(int* a, int n) //快排——挖坑法{ if (n == 1 || n == 0) return; int key = 0; int left = 0; int right = n - 1; int temp = a[key]; while (left < right) { while (left<right && a[right]>temp) right--; a[left] = a[right]; //填左边的坑 while (left<right && a[left]<= temp) left++; a[right] = a[left]; //填右边的坑 } a[left] = temp; //最后左右相遇时,填坑 key = left; QuickSort2(a, key); QuickSort2(a + key + 1, n - key - 1);}
基本思路: 设置两个指针(prev,cur),还是在数组的头或尾找一个基准值,prev指向第一个元素,cur指向第二个元素,然后cur开始遍历数组,找到比基准值小的值就与prev下一个元素交换,直到cur遍历完数组。
我们以一次循环作为基础:
如果没有遇到比基准值小的数cur就直接往后走,找到比基准值小的数就开始交换。
其实我们还可以把数组的最后一个数设为基准值,这时程序也要相应的做出一点改变
这时prev的其实位置就必须时数组第一个数的前一个位置,也就是下表为-1的位置,cur起始位置时数组的 首元素,其他的步骤与上面的一样。
代码
void QuickSort3(int* a, int n) //快排——双指针法{ if (n == 1 || n == 0) return; int key = 0; int prev = 0; int cur = 1; while (cur < n) { if (a[cur] < a[key]) swap(&a[++prev], &a[cur]); cur++; } swap(&a[prev], &a[key]); key = prev; QuickSort3(a, key); QuickSort3(a + key + 1, n - key - 1);}
把递归转换成非递归有两种方法:
因为递归是把大事化成若干个小问题去解决,循环正好是反过来人为的从小问题开始解决。但是有时候递归在把大问题化成小问题的时候,小问题是建立在大问题的基础上的,不解决大问题就无法得到小问题,所以用循环就无法从小问题开始解决,这时就要用到栈的结构,栈的结构正好将这种情况完美解决,从 入栈时的大->小 ,到 出栈进入循环时的 小->大
本体思路:
注意:
这里要注意入栈和出栈时的左右边界的顺序,左边界先入栈,右边界后入栈,取栈顶元素时就要先取右边界并出栈,再取左边界
代码
int Partsort(int* a, int left,int right) //单趟排序{ int key = left; int temp =Choose_Key(a,left,right); swap(&a[temp], &a[left]); 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]); return left;}void QuickSortNonR(int* a, int n) //快排的非递归写法{ Stack ps; StackInit(&ps); StackPush(&ps, 0); // 入左边界 StackPush(&ps, n - 1); // 入右边界 while (!StackEmpty(&ps)) { int end = StackTop(&ps); //右边界先出栈 一定要和上面入栈的顺序相反!!!! StackPop(&ps); int begin = StackTop(&ps); //左边界出栈 StackPop(&ps); int keyi = Partsort(a, begin, end); if (keyi + <
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/121090.html
摘要:内部排序数据元素全部放在内存中的排序。这部分主要是内部排序。排序讲解都以升序为例。当到达时,所有元素在统一组内排好序。当时都是预排序,目的是让数组更接近于有序。之后也是以基准值为界限,递归排序基准值左右区间。 目录 前言 常见排序算法的实现 1.插入排序 2.希尔排序 3.选择排序 4.堆排...
摘要:参数含义上图是函数各个参数的含义,让我们一个个来看。使用方式头文件要使用函数我们首先需要引用一个头文件的实现函数给函数规定了特定的参数。因此我们设计函数时要严格遵守其参数设定。 目录 1.参数含义 1.首元素地址base 2.元素个数num 3.元素大小size 4.自定义比较函数compa...
摘要:向后移动位简单选择排序基本思想常用于取序列中最大最小的几个数时。代码实现循环次数选出最小的值和位置交换位置堆排序基本思想对简单选择排序的优化。 概述 常见的八大排序算法,它们之间的关系如下: showImg(https://segmentfault.com/img/remote/1460000011395738?w=880&h=671); 直接插入排序 希尔排序 简单选择排序 堆排序...
摘要:本篇博客我要来和大家一起聊一聊数据结构初阶中的最后一篇博客八大经典排序算法的总结,其中会介绍他们的原来,还有复杂度的分析以及各种优化。快速排序递归版本快速排序是于年提出的一种二叉树结构的交换排序方法。 ...
阅读 2173·2021-11-16 11:44
阅读 2877·2021-11-02 14:44
阅读 3144·2021-09-26 09:47
阅读 3064·2021-09-22 10:02
阅读 3595·2021-09-02 15:41
阅读 1519·2019-08-29 16:57
阅读 1669·2019-08-26 13:38
阅读 3108·2019-08-23 18:13