兄弟们,应上篇数据结构的各位要求,今天我开始工作了,开始肝算法,剑指offer还在路上,我真想开车去接它,奈何码神没有驾照的开车,算了,弄排序算法吧,有点长,耐心看啊,原创不易,你们懂的,先上一张图
可以看出排序算法,还是比较多的,算了,不多说了,你我肝完就是出门自带4年实习经验的!
冒泡我一般也将它称为枚举就是把所有都走一遍嘛,效率比较低,一般在算法竞赛中如果实在没有比较好的,可以用,那就先讲一个简单的枚举吧!
枚举字典序
首先可能有的同学不知道什么是字典序,请看:
(1,2,3),(1,3,2)…这就是字典序的体现,官方解释是这样的:
字典排序(lexicographical order)是一种对于随机变量形成序列的排序方法。其方法是,按照字母顺序,或者数字小大顺序,由小到大的形成序列。
比如说有一个随机变量X包含{1 2 3}三个数值。
其字典排序就是{1 2 3} {1 3 2} {2 1 3} {2 3 1} {3 1 2} {3 2 1}
如果是字母:先比较第一个字符i和b,b 例如:abcdd
//冒泡排序,我也将它称为枚举#include #include using namespace std;void print(int n, int *a, int cur){ if (cur == n)//递归边界 { for (int i = 0; i < n; i++) { printf("%d", a[i]); } printf("/n"); } else for (int i = 1; i <= n; i++) { int OK = 1; for (int j = 0; j < cur; j++) { if (a[j] == i)//判断i是否出现过 OK = 0; if (OK)//i没有出现过下一个 { a[cur] = i; print(n, a, cur + 1);//递归 } } }}int main(){}
下面我们来看一下正宗的冒泡排序,总体思想是:俩俩比较,如果反序交换,直到没有反序的记录为止,代码实现比较简单,是俩个for循环的嵌套
#include #include //调用算法库,使用交换函数swap#include using namespace std;int main(){ int a[10]; for (int i = 0; i < 10; i++) { cin >> a[i]; } for (int i = 0; i < 10; i++) { for (int j = i + 1; j < 10; j++) { if (a[i] < a[j]) swap(a[i], a[j]); } } for (int i = 0; i < 10; i++) { printf("%d ", a[i]); } return 0;}
总体来说比较简单,但是耗时,耗内存,反正就是不好,来优化一下,为什么不好?归根结底还是做了许多重复的运算,大量的比较,
总体思路是这样的:再某一次比较后,发现所有的数据都变成了顺序,直接退出循环,不再继续循环
//将for改为 bool flag = true; for (int i = 0; i < 10 && flag; i++) { flag = false; for (int j = 10 - 1; j >= i; j--) { if (a[j] > a[i]) { swap(a[j], a[j + 1]); flag = true; } } }
算法复杂度:俩个for,就是O(n^2)了,有点大
选择排序
先来和冒泡排序比较一下,他俩的主要区别就是冒泡排序的数据在不断的交换,而快速排序先交换数据的别名,再交换本身。打个比喻就是,一个是幻想天上掉馅饼,背水一战,的炒股短线选手,而另一个则是看中时机的炒股老手,俗称股神。
好了,比较也比较完了,我们来看简单的代码实现吧
#include #include #include using namespace std;int main(){ int a[10]; for (int i = 0; i < 10; i++) { cin >> a[i]; } for (int i = 0; i < 10; i++) { int min = i; for (int j = i + 1; j < 10; j++) { if (a[min] > a[j]) min = j;//交换下标位置 } if (i != min) swap(a[i], a[min]); } for (int i = 0; i < 10; i++) { printf("%d ", a[i]); } return 0;}
如果来分析算法复杂度的话,你会惊讶的发现时间复杂度仍旧是O(n^2),但是我要说的是它仍旧优于冒泡排序,why?
冒泡排序和选择排序是排序算法中比较简单和容易实现的算法。冒泡排序的思想为:每一次排序过程,通过相邻元素的交换,将当前没有排好序中的最大(小)移到数组的最右(左)端。而选择排序的思想也很直观:每一次排序过程,我们获取当前没有排好序中的最大(小)的元素和数组最右(左)端的元素交换,循环这个过程即可实现对整个数组排序。
选择排序的平均时间复杂度比冒泡排序的稍低:
同样数据的情况下,2种算法的循环次数是一样的,但选择排序只有0到1次交换,而冒泡排序只有0到n次交换
和冒泡排序相似,但是优于冒泡,总体是一个分治的思想,交换轴点元素
还是排列一串数字,进行代码实现:
#include using namespace std;void quickSort(int *arr,int begin,int end){//begin为左,end为右 //如果区间不只一个数 if(begin < end) { int temp = arr[begin]; //将区间的第一个数作为基准数 int i = begin; //从左到右进行查找时的“指针”,指示当前左位置 int j = end; //从右到左进行查找时的“指针”,指示当前右位置 //不重复遍历 while(i < j) { //当右边的数大于基准数时,略过,继续向左查找 //不满足条件时跳出循环,此时的j对应的元素是小于基准元素的 while(i<j && arr[j] > temp) j--; //将右边小于等于基准元素的数填入右边相应位置 arr[i] = arr[j]; //当左边的数小于等于基准数时,略过,继续向右查找 //(重复的基准元素集合到左区间) //不满足条件时跳出循环,此时的i对应的元素是大于等于基准元素的 while(i<j && arr[i] <= temp) i++; //将左边大于基准元素的数填入左边相应位置 arr[j] = arr[i]; } //将基准元素填入相应位置 arr[i] = temp; //此时的i即为基准元素的位置 //对基准元素的左边子区间进行相似的快速排序 quickSort(arr,begin,i-1); //对基准元素的右边子区间进行相似的快速排序 quickSort(arr,i+1,end); } //如果区间只有一个数,则返回 else return;}int main(){ int num[12] = {23,45,17,11,13,89,72,26,3,17,11,13}; int n = 12; quickSort(num,0,n-1); cout << "排序后的数组为:" << endl; for(int i=0;i<n;i++) cout << num[i] << " "; cout << endl; return 0;}
算一下复杂度吧,最坏O(n^2),平均O(nlogn)几乎没有最坏的情况发生,所以效率还是比较高的,想一想如果就只要最大的值怎么弄?
#include using namespace std;int Partition(int *a, int i, int j){ int tmp = a[j]; int index = i; if (i < j) { for (int k = i; k < j; k++) { if (a[k] >= tmp) { swap(a[index++], a[k]); } } swap(a[index], a[j]); return index; }}int Search(int a[], int i, int j, int k){ int m = Partition(a, i, j); if (k == m - i + 1) return a[m]; else if (k < m - i + 1) { return Search(a, i, m - 1, k); } //后半段 else { //核心后半段:再找第 k-(m-i+1)大的数就行 return Search(a, m + 1, j, k - (m - i + 1)); }}int main(){ int a[7] = { 8,7,6,1,2,3,4 }; int k = 3; cout << Search(a, 2, 6, k);}
话说,码神最近在玩斗地主,你们说手机斗地主和真人斗地主最大的区别,或者是说好处是什么?我感觉就是在手机上不用插牌了,省时间,这利用的就是插入排序的原理,可以说是“斗地主排序”
基本操作:将一个记录插入到已经排好的有序表中,从而得到一个新的,记录数据+1的有序表
基操,看代码:
void insertionSort(int *arr, int len) { if (len<2) { return ; } for (int i=1; i<len; i++) { int insertValue = arr[i];//暂存需要插入元素 int j = i-1; //从右向左比较元素 for (; j>=0 && insertValue<array[j]; j--) { arr[j+1] = arr[j]; } arr[j+1] = insertValue; }}
老规矩,分析时间复杂度,最好的情况是顺序都是排列好的,此时只需要比较,时间复杂度为O(n),最坏的情况为O(n^2),平均下来是n ^ 2/4,所以平均时间复杂度也是O(n ^ 2).
如果说谁是第一个将排序算法复杂度突破O(n^2)的,那么我想希尔是第一个,可以说希尔排序是对插入排序的改进,区别在于,希尔排序可以说是一个不断分组的排序
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,具体算法描述:
选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;
按增量序列个数k,对序列进行k 趟排序;
每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。
实现如下:
//希尔排序void ShellSort(int* arr, int n){ int gap = n; while (gap>1) { //每次对gap折半操作 gap = gap / 2; //单趟排序 for (int i = 0; i < n - gap; ++i) { int end = i; int tem = arr[end + gap]; while (end >= 0) { if (tem < arr[end]) { arr[end + gap] = arr[end]; end -= gap; } else { break; } } arr[end + gap] = tem; } }}
时间复杂度,牛逼的人们,通过大量的计算发现是O(n^3/2),小于O
(n^2),由于是跳跃式的排序所以不是稳定排序
可参考上面
何为堆,如果已经学过堆的话,就是那个堆,与栈相对的堆,
基本思路:将代排的序列构造成一个大堆,此时,整个序列的最大值就是堆顶的根结点,将它移走,也就是将其与堆数组的末尾元素交换,此时末尾元素就是最大值,然后将剩余的n-1个序列重新构造成一个堆,这样就会得到n个元素的次最大值,如此递归反复就会得到一个有序序列
varlen; // 因为声明的多个函数都需要数据长度,所以把len设置成为全局变量 function buildMaxHeap(arr) { // 建立大顶堆 len = arr.length; for(vari = Math.floor(len/2); i >= 0; i--) { heapify(arr, i); }} function heapify(arr, i) { // 堆调整 varleft = 2 * i + 1, right = 2 * i + 2, largest = i; if(left < len && arr[left] > arr[largest]) { largest = left; } if(right < len && arr[right] > arr[largest]) { largest = right; } if(largest != i) { swap(arr, i, largest); heapify(arr, largest); }} function swap(arr, i, j) { vartemp = arr[i]; arr[i] = arr[j]; arr[j] = temp;} function heapSort(arr) { buildMaxHeap(arr); for(vari = arr.length - 1; i > 0; i--) { swap(arr, 0, i); len--; heapify(arr, 0); } return arr;}
时间可以说是主要耗在了初始建堆和在重建堆的反复筛选上
1.构造堆:O(n)
2.重建堆:完全二叉树:数据结构,详解时间复杂度为O(nlogn)
又因为堆排序对原始记录的排序状态并不敏感,因此它无论是好是坏,时间复杂度都为O(nlogn),同希尔排序,都为不稳定性的排序
完全二叉树,是一棵神奇的树,可以说归并排序是完全体现了完全二叉树的性质
若将两个有序表合并成一个有序表,称为2-路归并。
#include using namespace std;void Merge(int[], int, int[], int, int, int) void MergeSort(int numbers[], int length, int temp[], int begin, int end){ //1. 同样判断传入的参数是否有效 if (numbers == nullptr || length <= 0 || begin < 0 || end >= length) throw new exception("Invalid input."); //2. 作为递归的结束条件,开始下标和结束下标相等时,说明子序列中只有一个元素,看作有序的 if (end - begin == 0) return; //3. 定义中间变量,将数组分半【如果有7个元素,下标0-6,则middle=3,数组分为长度为4和3的两段】 int middle = ((end - begin) / 2 ) + begin; //4. 递归,先递归左半边,再递归右半边,将左右子序列不断分为长度为1的子序列才停止递归 MergeSort(numbers, length, temp, begin, middle); MergeSort(numbers, length, temp, middle + 1, end); //5. 再慢慢归并 Merge(numbers, length, temp, begin, end, middle);}void Merge(int numbers[], int length, int temp[], int begin, int end, int middle){ //1. 判断是否有不符合要求的参数传入,有则抛出错误 if (numbers == nullptr || length <= 0 || begin < 0 || e
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/119369.html
前言 文章摘抄至《算法之美》,附带了Python模拟。 不久前,我去观看草地网球锦标赛,一位十分沮丧的运动员引起了我对球赛目前采用的名次确定方法的注意。这位运动员在比赛中早早落败,因此彻底失去了获得奖牌的机会。令他感到屈辱的是,获得第二名的是他知道的一名远不如自己的运动员。 普通观众可能会把这种哀叹归咎于失败的痛苦,但道奇森并不是一个同情心泛滥的人,他是牛津大学数学系讲师,因此,在听到运动...
本文是为了帮大家快速回顾了测试中知识点,这套面试手册整整花了一个月的时间整理出来,上传到Git上目前star数达到了27K+。内容涵盖了诸多技术栈的面试题和答案,相信可以帮助大家在最短的时间内用作面试复习,能达到事半功倍效果。 同时用XMind画了一张导图记录软件测试的学习笔记,有需要的朋友,帮作者关注点赞收藏三连一下,即可无偿下载一份! 测试开发手册完整版PDF☞☞☞ 软件测试核心知识点目录内容...
摘要:哪吒社区技能树打卡打卡贴函数式接口简介领域优质创作者哪吒公众号作者架构师奋斗者扫描主页左侧二维码,加入群聊,一起学习一起进步欢迎点赞收藏留言前情提要无意间听到领导们的谈话,现在公司的现状是码农太多,但能独立带队的人太少,简而言之,不缺干 ? 哪吒社区Java技能树打卡 【打卡贴 day2...
必须要看的前言 本文风格:以❤️简单易懂❤️的语言带你彻底搞懂KNN,了解什么是有监督学习算法。 认真看完这篇文章,彻底了解KNN、了解监督学习算法绝对是一样很简单的事情。 注:本篇文章非常详细,同时我也附加了Python代码,欢迎收藏后慢慢阅读。 目录 必须要看的前言监督学习算法KNN/K近邻算法1 算法原理1.1 实现过程1.2 距离的确定 2 算法的优缺点3 算法的变种3.1 变...
此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解. 目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容). 关...
阅读 2246·2021-11-17 09:33
阅读 564·2021-11-04 16:13
阅读 1192·2021-10-14 09:50
阅读 2074·2021-09-07 09:59
阅读 3439·2021-09-07 09:59
阅读 561·2019-08-30 15:53
阅读 3518·2019-08-30 14:18
阅读 3133·2019-08-30 14:14