凡科网免费网站怎么样,外贸多语言网站建设,站长工具域名查询社区,百度托管公司目录 冒泡排序【有点拉胯】动图演示:思路解析单趟算法图解代码详解性能优化复杂度分析 直接插入排序【还阔以】动图演示思路解析代码分析与讲解复杂度分析 希尔排序【有点强】动图演示思路讲解排序过程总览代码分析讲解复杂度分析 堆排序【太有石粒啦】动图演示堆的概念与结构向… 目录 冒泡排序【有点拉胯】动图演示:思路解析单趟算法图解代码详解性能优化复杂度分析 直接插入排序【还阔以】动图演示思路解析代码分析与讲解复杂度分析 希尔排序【有点强】动图演示思路讲解排序过程总览代码分析讲解复杂度分析 堆排序【太有石粒啦】动图演示堆的概念与结构向下调整算法【核心所在】代码考究精析升序建大堆 or 小堆?如何进一步实现排序复杂度分析 冒泡排序【有点拉胯】
动图演示: 思路解析
所谓冒泡就是像泡泡一样从水底冒泡到水面这个冒泡过程就是比较已经冒泡到水面的数据就不用再进行比较.也就是说把第一个元素与后面的元素比较如果说排升序第一个元素比后面的元素大就交换位置然后再与后面的元素进行比较比较完后此时我们就冒泡到了水面所需冒泡的元素就少了一个下一次冒泡的时候就应该少排序一个。.
单趟算法图解 代码详解性能优化
先看内部循环.
for (int j 0; j n - i - 1; j)
{if (a[j] a[j 1])swap(a[j], a[j 1]);
}
这里n - i 就是我们每一趟循环冒泡都会排好一个最大的数据(升序)那么那个数据就不需要再进行下一次的循环冒泡中-1则是为了防止数组下标越界设 n 10,第一次 j 9, 那么j最大下标是8,此时 j 1最大就是9 了。
我们再来看外部循环:
for (int i 0; i n - 1 ; i)i n - 1是因为设n 10, i 9,最大取到8,此时内部循环 j n - i -1最后一趟就是 j 1,也就是最后第一个元素0(j)与第二个元素(j1)的比较冒泡。下面第i趟冒泡排序可以参考 那这样的情况我们能不能优化一下呢 可以看到我们或许不需要一定把n趟排序循环完数组才有序可能是n/2趟n/4趟,n-2,n-3趟等数组就有序了。这种我们可以使用一个标志变量如果单趟冒泡排序的过程中发生了交换也就是进了if条件说明数组还没有序需要交换那么把标志变量改变如果进行单趟冒泡排序后标志变量没有改变说明数组已经有序这时候就可以直接跳出外层循环。
/*冒泡排序*/
void BubbleSort(int* a, int n)
{//[0,n - 1)for (int i 0; i n - 1; i){int changed 0;for (int j 0; j n - 1 - i; j){if (a[j] a[j 1]){swap(a[j], a[j 1]);changed 1;}}if (changed 0)break;PrintArray(a, n);} //[1,n)//for (int i 1; i n; i)//{// for (int j 0; j n - i; j)// {// if (a[j] a[j 1])// swap(a[j], a[j 1]);// }//}
}
复杂度分析
【时间复杂度】O(N2) 【空间复杂度】O(1)
我们通过上面的讲解了其运行过程就是每一个数与其后的n - i个数进行比较若是符合条件则进行交换不算我们优化之后的算法运行的次数就是 (N - 1) (N - 2) (N - 3) … 2 1结合起来运算就是一个等差数列那么其时间复杂度显而易见就是O(N2)对于最后的情况就是o(n),也就是数组已经有序的情况下我们做了标志变量如果第一次冒泡排序没有交换就可以直接结束循环此时我们只执行了n次。
直接插入排序【还阔以】
动图演示 思路解析
可以看到直接插入排序就是把有序区间的后的第一个数据与有序区间的数据进行依次比较这里设升序如果说比有序区间中的某个数据小就让这个数据之后的有序区间的数据整体往后面移动然后最后把这个数据插入到有序区间中比他大的那个数据的位置。 实际中我们玩扑克牌时就用了使用到了插入排序的思想。设想你发到一张牌为7现在想将其放入你刚才已经整理好了牌堆中这个牌堆就是有序序列这张牌就是待插入的数据。通过生活中的场景来看是不是更加形象一点呢
代码分析与讲解
理解算法后也不一定会写程序。也就是脑子会了手还不会。但是我们应该知道写程序不是一下把整个算法就写出来了我们应该从简单到复杂我们先不写整趟排序就考虑单趟排序的问题。首先单趟的逻辑就是我们需要把有序区间后的一个数据插入到有序区间中不妨设有序区间最后一个数据为end之后的数据是end 1然后我们开始比较end和end1如果说end1小于end那么end这个数据往后移动到end 1这个位置然后end - - 开始有序区间中的另一个数据和end 1进行比较但是注意的是随着有序区间的扩大我们end 1需要比较的数据就越多此时我们需要把这段逻辑放在一个循环里面结束条件是什么呢end 0, 等于0,是因为我们最坏可能比较到第一个元素也比end 1小.若是在中途比较的过程中发现有比待插入数据还要小或者相等的数就停止比较跳出这个循环。因为随着有序区间中数的后移end后一定会空出一个位置此时呢执行a[end 1] tmp;就可以将这个待插入数据完整地放入有序区中并且使这个有序区依旧保持有序
int end;
int tmp a[end 1]; //将end后的位置先行保存起来
while (end 0)
{if (tmp a[end]){a[end 1] a[end]; //比待插值来得大的均往后移动end--; //end前移}else{break; //若是发现有相同的或者小于带插值的元素则停下跳出循环}
}
a[end 1] tmp; //将end 1的位置放入保存的tmp值
接下来我们看外层循环
for (int i 0; i n - 1; i)
{int end i;//单趟插入逻辑...
}
或许有人疑问为什么i n - 1 而不是 i n这里主要是防止数组下标越界设n 10 , 如果 i n n最大为9下面的end 1就会访问到a[10],此时会越界所以是 i n - 1
下面是整体代码:
/*直接插入排序*/
void InsertSort(int* a, int n)
{//不可以 n否则最后的位置落在n-1tmp访问end[n]会造成越界for (int i 0; i n - 1; i){int end i;int tmp a[end 1]; //将end后的位置先行保存起来while (end 0){if (tmp a[end]){a[end 1] a[end]; //比待插值来得大的均往后移动end--; //end前移}else{break; //若是发现有相同的或者小于带插值的元素则停下跳出循环}}a[end 1] tmp; //将end 1的位置放入保存的tmp值}}
复杂度分析
【时间复杂度】O(N^2) 【空间复杂度】O(1)
最好的情况就是o(n)也就是数组本身就有序的情况:1 2 3 4 5 6 7 8 9 10,此时只需要遍历一次数组而已。最坏的情况就是o(n^2),这里设要排升序数组为降序:10 9 8 7 6 5 4 3 2 1,此时就需要全部都往后面移动一位。
希尔排序【有点强】
动图演示 思路讲解
希尔排序就是直接插入排序的优化我们在上面分析直接插入排序的时间复杂度时最差的时候就是降序的时候那么现在对降序的数组进行分组对每组进行直接插入排序那么每组的数据就是比原先没分组的数据少这时候我们直接插入排序的时候交换的次数变少了而且保证了整个数组基本有序。对原本的数据进行一个分组对每组使用直接插入排序排序。增量【gap】随着排序次数的增加而减少当gap1时整个序列恰好被分为一组就对预排序后的数组最后一次进行直接插入排序。
排序过程总览 我们看到这里有10个数, gap 10 / 2 , gap 5,也就是每个数字之间的间隔为5。然后把他们分组每组的元素间隔5个元素若是前者比后者大则交换。 以上就是三次排序的过程当gap 1的时候也就是全部数据为一组即间隔为一对他们进行直接插入排序
代码分析讲解
还是一样我们从简单到复杂先分析单趟排序的过程。对于希尔排序我上面说过其实他就是直接插入排序的优化只不过多了一个分组来排的逻辑。而这个分组有那些元素就是通过gap 间隔增量来控制。我们开始设 n 10, gap n / 3 ,也就是间隔3个元素的数据为一组分了组就简单了我们就对每个分组的元素进行直接插入排序那么怎么获得每个分组的元素了因为他们是间隔gap 个元素为一组现在设end为分组第一个元素所以就是end gap 个元素注意:在实现后移的过程中也是移动gap步对于end也是同理注意:那在跳出循环之后的tmp也是要放在a[end gap]的地方
int gap 3;
int end;
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;
说完了单趟我们就要用循环来控制每一趟排序了。way1:第一种方法就是我们把每个分组的元素以组为单位把每一组的数据排好再排下一组此时我们需要排gap组. 这种方法不推荐都有4层循环了。way2:把每一组的第一个元素排完然后排下一组这种就只有3层循环i控制每一组的第一个元素和第2个元素的排序
下面为2中方法图解:
再说说为什么gap gap / 3,gap gap / 5行不行gap / 5当然可以但是他们每组元素的间隔太远了我们进行预排序的目的是把数组接近有序这样在最后一次直接插入排序的时候我们需要往后移动的次数就少了。
如图这样的预排序之后
那有人说那我直接gap / 2,2个间隔为一组这样是缩短了距离但是组数变多了也不好所以我们这种选择gap / 3.但是在gap / 3之后可能在最后无法使【gap 1】比如gap 6的时候那此时的话就需要在最后加上一个1使得最后一次缩小gap增量的时候可以使其到达1gap 1就是因为设 gap 10, 最后会除到1此时1/3 1会永远等于1所以gap 1.i n - gap ,也是为了防止数组越界因为我们是分组进行排序每次都是与end gap 下班班元素进行比较
整体代码演示:
/*希尔排序*/
void ShellSort(int* a, int n)
{int gap n;while (gap 1) {/** gap 1 —— 预排序* gap 1 —— 直接插入排序*///gap / 2;gap gap / 3 1; //保证最后的gap值为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;}}
}
复杂度分析
【时间复杂度】O(NlogN) 【空间复杂度】O(1)
但这也仅仅似乎根据我们写的代码来看实际上希尔排序的时间复杂度不是O(NlogN)而是O(N1.3)大家只能要能够计算出O(NlogN)就行了如果有读者数学很好的当然也是可以做到然后对于希尔排序时间复杂度最坏是O(N2)这一点上面也已经写出了最坏情况就是等差数列的时候例如5个数要挪动4下3个数要挪动2下。。。N个数要挪动N - 1下希尔排序比直接插入排序快的原因就是因为分组预排序让数组接近有序并且比较的数据变少然后最后一次排序的时候由于数组已经接近有序那么比较的次数就变少了。 然后是有关希尔排序的空间复杂度这一块还是和插入排序一样只是在内部定义了一些变量并没有去申请一些额外的空间因此空间复杂度为O(1)
堆排序【太有石粒啦】
动图演示 堆的概念与结构 如果有一个关键码的集合K { k0 k1 k2…kn-1 }把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中。并满足Ki K2i1 且 Ki K2i2 ( Ki K2i1 且 Ki K2i2 ) i 012…则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆 【堆的性质】 堆中的左右孩子节点总是大于(小根堆)根节点或者小于(大根堆)根节点堆总是一颗完全二叉树
基本了解堆的概念后我们来看看琢磨一下什么是大根堆和小根堆
从上图可以看出对于【堆】而言其实就是一种完全二叉树但是呢它又在完全二叉树的基础上再进一步形成一个区分也就是分为【大根堆】和【小根堆】但是这只是我们自己想象出来的逻辑结构但是在内存中的物理结构实际上就是数组存储的既然是数组我们就一定可以通过下标来访问其中的各个元素。这其实也得出了一个结论在逻辑结构中我们可以看出其实每个根节点都要左右孩子节点那么在物理结构中我们想要访问这些节点也可以吗在二叉树和堆中已经讲过。
【lchild parent * 2 1】 左孩子 【rchild parent * 2 2】 右孩子 【parent (child - 1) / 2】
向下调整算法【核心所在】
算法图解(这里假设我们建的大堆)
对于向下调整算法必须满足的前提就是需要调整的根节点的左右子树是大根堆这样保证调整后整棵树也是一个大根堆。对于上面的原理就是如果我们需要保证调整完后整颗二叉树是一个大堆根节点18需要找他的左右孩子节点谁更大与其交换保证交换后对于18,49,34这颗二叉树是一个大根堆然后从把交换的孩子节点作为新的子树根节点依次循环以上步骤。直到这个【18】的孩子结点到达【n - 1】就不作交换了因为【n - 1】就相当于是位于数组下标的最后一个值
代码考究精析
首先对于向下调整算法我们需要调整堆那么前面堆的结构说了其实物理结构是一个数组(也就是顺序二叉树)那么我们第一个参数就传数组名然后我们要调整他的根节点根节点与左右孩子节点比较交换所以我们把父节点传过去通过【lchild parent * 2 1】 左孩子 【rchild parent * 2 2】 右孩子求其左右孩子节点。还有就是传数组的长度这在循环的结束条件要用到。
void Adjust_Down(int* a, int n, int parent)
你可以通过每次计算 左右孩子节点来比较谁大。但是有点冗余我们这里假设左孩子为最大节点如果他比右孩子节点小那么左孩子节点下标1因为数组数连续存储的1就是右孩子节点。if判断里还加了一个【child 1 n】这个的话其实就是进行一个右孩子的越界访问判断因为我们是在进行一个不断向下调整的过程因此肯定会到达倒数第二层此时它的左孩子可能是存在的但若是它的右孩子不存在了那么在后面去访问这个【child 1】就会变成越界访问⚠是一个非法操作 //判断是否存在右孩子防止越界访问
if (child 1 n a[child 1] a[child])
{child; //若右孩子来的大则转化为右孩子
}
然后是循环内部的逻辑和【向上调整算法】一样就是一个比较和迭代更新的过程
if (a[child] a[parent])
{swap(a[child], a[parent]);parent child; //更新父亲child parent * 2 1; //更新孩子
}
else {break;
}
整体代码演示
/*向下调整算法*/
void Adjust_Down(int* a, int n, int parent)
{int child parent * 2 1; //默认左孩子来得大while (child n){ //判断是否存在右孩子防止越界访问if (child 1 n a[child 1] a[child]){child; //若右孩子来的大则转化为右孩子}if (a[child] a[parent]){swap(a[child], a[parent]);parent child;child parent * 2 1;}else {break;}}
}
升序建大堆 or 小堆?
给个答案就是升序我们应该建大堆降序我们应该建小堆。为什么升序建大堆 我们建堆就是为了排序数组既然是升序就是小的在前面大的在后面。我们建大堆可以保证堆顶一是最大的这时候我们只需要把堆顶与数组最后一个元素交换就可以保证数组最后一个元素是最大的。 有人说了那我用建小堆也能保证数组第一个元素是最小的。 看图 那有n个数排序我们就要建n个堆建堆一次时间复杂度为o(n),建n个堆就是o(n^2)而建大堆我们只需要把堆顶和数组最后一个元素进行交换然后对堆进行向下调整即可可能有人疑问那建小堆的时候为什么不直接向下调整我前面说过向下调整前提是需要保证其左右子树是小堆的但是上图父亲孩子节点打乱后就不是小堆了。
//建立大根堆倒数第一个非叶子结点
for (int i ((n - 1) - 1) / 2 ; i 0; --i)
{Adjust_Down(a, n, i);
}
如何进一步实现排序
其实在前面讲向下调整算法的过程中已经透露出排序的过程了
就是建大堆后把堆顶元素和数组最后一个元素进行交换达到数组最后一个元素是最大的目的。然后进行向下调整恢复大堆的性质(堆顶为最大元素)再进行交换知道交换到堆顶结束。注意每次交换后被交换到后面的数据不参与下次堆的向下调整。 代码如下:
/*堆排序*/
void HeapSort(int* a, int n)
{//建立大根堆倒数第一个非叶子结点for (int i ((n - 1) - 1) / 2 ; i 0; --i){Adjust_Down(a, n, i);}int end n - 1;while (end 0){swap(a[0], a[end]); //首先交换堆顶结点和堆底末梢结点Adjust_Down(a, end, 0); //一一向前调整end--;}
}
整体代码
/*交换*/
void swap(int* x, int* y)
{int t *x;*x *y;*y t;
}
/*向下调整算法*/
void Adjust_Down(int* a, int n, int parent)
{int child parent * 2 1; //默认左孩子来得大while (child n){ //判断是否存在右孩子防止越界访问if (child 1 n a[child 1] a[child]){child; //若右孩子来的大则转化为右孩子}if (a[child] a[parent]){swap(a[child], a[parent]);parent child;child parent * 2 1;}else {break;}}
}
/*堆排序*/
void HeapSort(int* a, int n)
{//建立大根堆倒数第一个非叶子结点for (int i ((n - 1) - 1) / 2; i 0; --i){Adjust_Down(a, n, i);}int end n - 1;while (end 0){swap(a[0], a[end]); //首先交换堆顶结点和堆底末梢结点Adjust_Down(a, end, 0); //一一向前调整end--;}
}
复杂度分析
【时间复杂度】O(NlogN) 【空间复杂度】O(1) 在建堆这块的时间复杂度是o(N),在排序一个数据的时候是lognn个数据就是nlongn ,nnlogn为nlogn空间复杂度就是o(1),并没有在堆排序里面重新申请空间。
