目录 冒泡排序的过程就如同它的名字一样，每次冒泡的过程会将元素中最大/小的一个数冒出来，?这样最后的一个元素就会是最大/小的元素，下一次冒泡过程就可以对前n-1个再进行排序，n趟过程下来整个序列就变成有序的了。 ?以上图为例，它的过程如下： 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对，最后的元素将会是最大的数。? 之后针对所有的元素重复以上的步骤，除了最后一个。 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较，排序就完成了。 第一趟：5和8比，5小不用动；8和6比，6小，进行交换；8和1比，1小进行交换；8和9比，8小不用动，第一趟排序结束。 第二趟：9已经是选出的最大元素，对剩下的元素进行冒泡，5和6比不用动；6和1比交换，6和8比不用动。 以此类推，最后排序结束。 动图示例： 外层循环控制趟数，内层循环用来进行两两元素的交换。 测试： 打印结果： 普通的冒泡排序存在着一个问题，数据的顺序排好之后，冒泡算法仍然会继续进行下一轮的比较，直到arr.length-1次，后面的比较没有意义的，因此可以通过优化减少它的比较次数。 改进方法：设置标志位flag，如果发生了交换flag设置为true；如果没有交换就设置为false。 这样当一轮比较结束后如果flag仍为false，即：这一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去。 时间复杂度： 若元素序列的初始状态已经是正序的，一趟扫描即可完成排序。所需的关键字比较次数C?和记录移动次数M?均达到最小值：Cmin=n-1，Mmin=0。 因此冒泡排序最好情况下的时间复杂度为O(n)。 若初始元素序列是逆序的，需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值。 因此冒泡排序最好情况下的时间复杂度为O(n^2）。 综上，冒泡排序的平均时间复杂度为：O(n^2）。 空间复杂度： 冒泡排序的空间复杂度为常数阶O(1)。 算法稳定性： 首先算法稳定性的定义：我的理解是在整个排序过程中，如果任意两个相等的元素在排序之前和排序之后的相对位置顺序没有发生改变，那么该算法就是稳定的，反之就是不稳定的。 比如arr[i]=arr[j]，i<j,整个过程中arr[i]都在arr[j]的前面没有发生改变，那么就是稳定的排序算法。 冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定的排序算法。 ?第一次从待排序的元素中选出最小（大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。 以上图为例： 第一趟：选出最小的元素1，与第一位元素5进行交换。 第二趟：选出最小的元素5，和第二位的元素8进行交换。 第三趟：最小的元素就在第三位，第四趟，第五趟都是，排序结束。 动图示例： 外层循环控制趟数，内层循环用来寻找每一趟中最小元素的下标，内层循环结束进行最小元素与趟数对应位置的交换。 ?测试： 打印输出：? 普通的选择排序算法在每一次交换中仅仅是选择出了最小的一个元素放在了第i个坐标，优化后可以加一个将最大元素放在最大下标的操作，这样可以减少整个排序的趟数，只需进行n/2趟即可。 用minIndex和maxIndex分别记录每一趟最小和最大元素的下标，找到之后与对应的i，j位置进行交换。 完整代码： 对于其中的一段代码： ?为什么要加个这个呢，因为优化后的算法存在一种情况，当maxIndex的下标恰好为i的时候，在上一步minIndex和i交换的过程中把arr[minIndex]和arr[i]的值给互换了，所以要将maxIndex改为minIndex。 时间复杂度： 选择排序的交换操作介于 0 和 (n - 1)次之间。选择排序的比较操作为 n (n - 1） / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1） 次之间。 比较次数O(n^2），比较次数与关键字的初始状态无关，总的比较次数N=(n-1）+(n-2）+...+1=n*(n-1）/2。 交换次数O(n），最好情况是，已经有序，交换0次；最坏情况交换n-1次，逆序交换n/2次。 交换次数比冒泡排序少，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。 综上所述，选择排序的平均时间复杂度为：O(n^2）。 空间复杂度： 选择排序的空间复杂度为常数阶O(1)。 算法稳定性： 选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。举个例子，序列5 8 5 2 9，如果选择第二个5和第一个5交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。 插入排序思想是将数组R划分成两个子区间R[1．．i-1]（已排好序的有序区）和R[i．．n]（当前未排序的部分，可称无序区）。插入排序的基本操作是将当前无序区的第1个记录R[i]插人到有序区R[1．．i-1]中适当的位置上，使R[1．．i]变为新的有序区。 如上图，第一趟-1小于3，将-1放在3的位置，3后移；第二趟2小于3但大于-1，将2插入3前面，3后移；第三趟8大于3不用动；第四趟5小于8但大于3，将5插入到8前面，8后移。 动图示例： ?外层循环控制趟数，内层循环寻找到要插入到有序序列的无序序列下标，然后将有序序列后移，将temp放到找到的位置下标。 测试： 打印输出： 普通插入是先找到位置然后移动，优化后可以将两个操作放在一个循环中，减少一个for循环的使用，从而减少了比较次数。 时间复杂度：? 在插入排序中，当待排序数组是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较N- 1次，时间复杂度为O(n)。 最坏的情况是待排序数组是逆序的，此时需要比较次数最多，总次数记为：1+2+3+…+N-1，所以，插入排序最坏情况下的时间复杂度为(On^2)。 平均来说，A[1..j-1]中的一半元素小于A[j]，一半元素大于A[j]。插入排序在平均情况运行时间与最坏情况运行时间一样，是输入规模的二次函数?。 综上所述，插入排序的平均时间复杂度为：O(n^2）。 空间复杂度： 插入排序的空间复杂度为常数阶O(1)。 算法稳定性： 排序前后相等元素的相对位置没有发生改变，所以该算法是稳定的。 希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（，是直接插入排序算法的更高效的改进版本。 希尔排序是基于插入排序的以下两点性质而提出改进方法的： 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。 先取一个小于n的整数d1作为第一个增量，把所有元素按增量进行分组，所有距离为d1的倍数的元素放在同一个组中，然后各组内进行直接插入排序；接下来取第二个增量d2 ，重复上述操作，直至增量为1时，最后进行一次排序即可。 如上图，开始增量为length/2=5时，有[8,0],[5,3],[11,9],[3,13],[-1,4]五组，对五组进行以此排序，以此类推，再减少增量为3然后排序，最后减少增量为1进行排序。 有两种方式，一种是直接定义gap每次就除以2，也可以自定义增量数组，循环调用shellSort函数进行排序。 完整代码（自定义增量）： 或者（自除2）：? 测试： 打印输出： 时间复杂度： 希尔排序的时间复杂度与增量的选取有关： 如希尔自己提出的每次将增量除以2向下取整的选择方法，时间复杂度为O(n^2)。 增量的选取有两个要点： 空间复杂度： 希尔排序的空间复杂度为常数阶O(1)。 算法稳定性： 一次插入排序是稳定的，不会改变相同元素的相对顺序，但在多次插入排序时，在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。 每一趟的排序过程中，先选定序列中的一个元素作为中心枢纽，选取是随意的，因此一般选择第一个元素，将子序列中比枢纽元素小的移动到它的前面，比它大的移动到它的后面，根据需求将相等的元素划分到前面一部分还是后面的部分。当这一趟结束后，该序列以枢纽为中心被划分为两部分，一部分元素都比它小，一部分元素都比它大，然后分别对这两部分重复上述操作，不断的递归，当序列长度还剩一个元素时排序就完成了。 动图示例： 实现过程：定义两个引用start和end，分别指向待排序列的第一个元素和最后一个元素，定义一个基准，一般来说取待排序列的第一个元素，从后往前比较end与基准的大小，如果end小于基准，则end往前走，从前往后比较start和基准的大小，如果start大于基准，则start往后走，start和end相对位置发生改变，此时结束，start=end=基准，此时会发现，基准的左边都是比基准小的数据，基准的右边都是比基准大的数据，接下来针对左右两边的序列继续进行以上过程，最终可以得到一个完全有序的序列。 测试： ?打印输出： 时间复杂度： 快速排序最好情况下的时间复杂度为O(nlogn)，即待排序序列越接近无序，该算法效率越高。 最坏情况下时间复杂度为O(n^2)，待排序序列越接近有序，该算法效率越低。 空间复杂度： 从空间性能上看，尽管快速排序只需要一个元素的辅助空间，但快速排序需要一个栈空间来实现递归。最好的情况下，即快速排序的每一趟排序都将元素序列均匀地分割成长度相近的两个子表，所需栈的最大深度为log2(n+1)；但最坏的情况下，栈的最大深度为n。这样，快速排序的空间复杂度为O(log2n)。 算法稳定性： 举个例子，3,2,2,5,4，如果选择arr[1]作为枢纽，取小于等于它的移动到前面，该算法就是不稳定的；或者取arr[2]为枢纽，大于等于它的移动到后面，这样来看也是稳定的。 综上所述，快速排序是一种不稳定的排序算法。 归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 简单来说，就是讲初始序列进行重复的对半分组，知道每组只剩一个元素或者两个元素时进行排序，按照指定的顺序排好序后，再合并两个小组进行排序，以此类推，直至最后将整个序列排序完毕后就完成了。 例如： 设有数列{6，202，100，301，38，8，1} 初始状态：6,202,100,301,38,8,1 第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3； 第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4； 第三次归并后：{1,6,8,38,100,202,301},比较次数：4； 总的比较次数为：3+4+4=11； 动图示例： 整体思想是二分法将序列分成两部分，用四个下标记录两部分的起始与终止位置，循环比较两部分中，将较小的加入到temp数组中，一次比较完成后，至少有一部分已经归并完成，对可能存在的另一部分没有归并完的情况继续进行归并，然后进行位置的更新，当划分只有一部分的时候退出循环。退出时将临时数组拷贝至原数组即可。 ?测试： 归并排序最好，最坏，平均时间复杂度都为O(nlogn)，空间复杂度为O(n)，是一种稳定算法。? 堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。 ? ?在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作： 最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点 创建最大堆（Build Max Heap）：将堆中的所有数据重新排序 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算 堆排序的树结构： 动图示例： 首先根据序列建堆，也就是一个二叉树，从上到下，从左到右依次填充。adjust函数用于调整，步长为2n+1，当结点下标超过end时终止循环，在循环中，判断如果i结点的右边结点存在并且arr[i]小于arr[i+1]的话，将i++，让i指向左右孩子结点中较大的右孩子结点，再与开始tmp存储的arr[start]值进行比较，如果比tmp要大，就用该值对arr[start]进行覆盖，然后start指向i，也就是当前最大孩子的下标。循环结束后，再将tmp赋值给arr[start]。 headSort中通过多次调用调整函数，进行大根堆的建造。 测试： 堆排序的最好，最坏和平均时间复杂度都为O(nlogn)，空间复杂度为O(1)，因为发生了元素位置顺序的交换，所以是一种不稳定的排序算法。? 基数排序又称为，属于“分配式排序”，它通过元素的各个位的值，将元素放置对应的“桶”中。首先把元素统一为同样长度的数组长度元素较短的数前面补0，比如（1 15 336 ? 看成? 001 015 336），然后从最低位开始，以此进行排序。 动图示例： ?测试： 基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。? 平均情况下，快速排序、希尔排序、归并排序和堆排序的时间复杂度均为O(nlog2n)，其他都是O(n^2)，比较特殊的是基数排序，它的时间复杂度为O(d(r+rd))。 最坏情况下，快速排序的时间复杂度为O(n^2)，其他都和平均情况相同，具体参照下表。
?
创客课程开发的每个主题课程需要基于现实情景，设置学习探究任务，通过问题研究、任务...
创客空间建设 能够给人们分享各种乐趣，通过电脑，技术，科学，艺术结合，设计创造一...
在了解创客教育之前，我们首先了解下何为创客。创客是一群喜欢或享受创新的人。创客跨...
STEAM教育是对传统教育的提升，它是基于自然学校方式的功能性框架，可以适合各类...
