基数排序是利用空间性能换取时间性能的一种排序算法,它的时间复杂度为O(nlog(r)m)   空间复杂度为O(n+r),是一种稳定的排序算法 直接上代码。 int getMaxDigit(int arr[],int n) { int i,max = *arr; for (i = 0; i < n; i++) { if (arr[i] > max) { max = arr[i]; } } for (i = 0; max; i++) { max /= 10; } return i; } void Radix…

2020年02月20日 1条评论 494点热度 3人点赞 阅读全文

堆排序是利用堆的性质进行排序的排序方式,时间复杂度O (nlgn),空间复杂度O(1),是一种原地排序算法。 首先 你需要知道什么是树,什么是二叉树,以及什么是完全二叉树 堆是一种特殊的完全二叉树,堆分为大顶堆和小顶堆,大顶堆要求每个节点的子节点(如果有),必须小于父节点,整个树的根节点是最大的,小顶堆相反,每个子节点比父节点大,根节点是最小的节点。 我们以大顶堆为例,以下是几个大顶堆。 按顺序给第一个堆的每个节点编上号如下图 所以就可以用一个数组进行储存; int arr[] = {10,5,7,3,4}; 假如…

2020年02月19日 1条评论 430点热度 1人点赞 阅读全文

在阅读本文章之前请确保你已经掌握了递归思想。 归并排序采用了一种分治的思想。时间复杂度为O(n log n)空间复杂度为O(n),是一种稳定的排序算法,它的速度仅次于快速排序。整个过程分为划分和合并两个部分 归并排序的步骤: 1.检查数组的元素数,如果元素数大于等于2就可以视为两个数组。(划分) 2.将数组划分为两部分,分别对两部分分别进行归并排序。(划分并排序,递归) 3.对排序好的两部分进行合并得到最终的有序数组。(合并) 还是举个栗子,我有一组数8 7 6 5 4 3 2 1: 这个过程也是一个自顶向下逐步划…

2020年01月13日 1条评论 299点热度 4人点赞 阅读全文

1.插入排序 插入排序,顾名思义是将一个数取出再插入到数组中合适位置,通过多次插入使得数组呈有序状态的一种排序算法. 时间复杂度:O(n^2),被称为最稳定的排序算法,它适用于数据量较少的排序. 算法步骤(从小到大): 将数组视作两部分,一部分有序一部分无序,初始时有序部分为左边第一个元素. 选择有序部分后一个元素将其取出,将其与有序部分最后一个元素比较,有序部分最后一个元素大于该元素,就将有序部分最后一个元素后移,然后该元素继续与有序部分前一个元素对比,直到找到有序部分某个元素小于该元素或到达有序部分最前端,就插…

2020年01月07日 0条评论 238点热度 2人点赞 阅读全文

在阅读本文章前请确定你已经掌握递归的思想 快速排序是一种高效的排序方式,它的时间复杂度最差情况是O(n2) ,理想情况O(nlog2n),正是因为它的高效,该排序方法被认为是目前最好的一种内部排序方法,对于初学者来说理解可能有难度. 快速排序的大致步骤: 1.选取一个划分标准(一般选择最左边的值). 2.通过某种算法(暂时忽略这个算法的实现)将数组以标准值划分为两部分,左边的都小于或等于标准值,右边的都大于或等于标准值. 3.分别将标准值两边看做两个新数组,将新数组进行上述过程。 4.直到划分到元素总数小于2就返回…

2020年01月07日 0条评论 459点热度 4人点赞 阅读全文

贪吃蛇都玩过,一个极其无聊而又透露着智障气息的游戏。 现在用我们的知识就能实现它,在开始之前,需要先记录几个有用的函数。 //光标移动函数,可以将光标移动到命令行窗口的指定坐标 #incldue<windows.h> void gotoxy(int x, int y) { COORD pos = { x,y }; HANDLE hOut = GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleCursorPosition(hOut, pos); } //随机数生成函数,…

2019年11月22日 0条评论 262点热度 2人点赞 阅读全文