、再十位、个位(这一步可以反着来：个位、十位、百位对比排序快速排序，如同用天平找出球堆中最重或最轻的球，数组分成3部分。...归并排序，对半分数组，排序，将已有序的子序列合并。即：对n个元素进行排序。分解为先对n/2，在对n/2个元素排序，最后合并的问题。利用的是分治思想，还有递归的思想 。采用先分后合并的思想。...假设需要排序的数位数d，因此如果对每一位都使用计数排序的话，总的时间复杂度为o(dn)时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法...0-9通过得到待排序数字的个十百等位的数字，把这个数字对应的item放到对应的桶中基数排序动画gif动画演示基数排序有两种排序方式：LSD和MSD，最小位优先(从右边开始)和最大位优先(从左边开始)最高有效位...|基数|桶|堆|希尔|快速|归并》,请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/SortingAlgorithms/8279.html
时间复杂度为 O(nlogn),好于冒泡,简单选择,直接插入的O(n^2) 七、快速排序 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序...时间复杂度为O(nlogn) 下文没有给出快速排序的实现，参考以前的文章。 ?...八：计数排序 计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。...然后根据数组C来将A中的元素排到正确的位置。...算法的步骤如下： 找出待排序的数组中最大和最小的元素 统计数组中每个值为i的元素出现的次数，存入数组C的第i项 对所有的计数累加（从C中的位置为1的元素开始，每一项和前一项相加） 反向填充目标数组：将每个元素
堆排序 ⚪步骤 堆排序： 堆排序（Heap Sort）是一种基于二叉堆数据结构的排序算法，它利用堆的性质进行排序。堆是一个完全二叉树，可以分为最大堆和最小堆两种类型。...排序： 交换堆顶元素（最大或最小元素）和堆的最后一个元素，然后将堆的大小减 1。 再次调整堆，使其满足堆的性质。 重复上述步骤，直到堆的大小为 1，排序完成。...数组的相对排序（计数排序） ⚪点击跳转：1122. 数组的相对排序 给你两个数组，arr1 和 arr2，arr2 中的元素各不相同，arr2 中的每个元素都出现在 arr1 中。...该算法的基本思想是统计每个元素的出现次数，然后根据这些统计信息将元素放回正确的位置。...丢失的数字（计数排序） ⚪点击跳转：268. 丢失的数字 给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
快速排序 快速排序，和二分查找的思想很像，都是先将数据一份为二然后再逐个处理。快速排序也是最常见的排序算法的一种，面试被问到的概率还是比较大的。...而根据排序的方向又分为大顶堆和小顶堆： 大顶堆：每个节点值都大于或等于子节点的值，在堆排序中用做升序排序。 小顶堆：每个节点值都小于或等于子节点的值，在堆排序中用做降序排序。...主要步骤： 创建一个二叉堆，参数就是无序序列[0~n]； 把堆顶元素和堆尾元素互换； 调整后的堆顶元素，可能不是最大或最小的值，所以还需要调整此时堆顶元素的到正确的位置，这个调整位置的过程，主要是和二叉树的子元素的值对比后找到正确的位置...重复步骤2、步骤3，直至整个序列的元素都在二叉堆的正确位置上了。 动图演示 ?...主要步骤： 找出待排序的数组中最大和最小的元素； 统计数组中每个值为i的元素出现的次数，存入数组C的第i项； 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）； 反向填充目标数组：将每个元素
计数排序（Counting Sort）：统计待排序序列中每个元素的出现次数，然后根据元素的值从小到大依次输出。时间复杂度为O(n+k)，其中k表示序列中元素的范围。...堆排序的具体步骤如下：将待排序序列构建成一个大顶堆（或小顶堆），从最后一个非叶子节点开始，自下而上地进行堆调整。交换堆顶元素（最大值或最小值）和堆中最后一个元素。...从根节点开始，自上而下地进行堆调整，保持堆的性质。重复步骤2和步骤3，直到堆中只剩下一个元素。堆排序适用于在多个元素中找出前几名的方案设计，因为堆排序是选择排序，而且选择出前几名的效率很高。...重复步骤1和步骤2，直到没有需要交换的元素，即列表已经有序。冒泡排序的时间复杂度为O(n^2)，其中n是列表的长度。由于每次遍历都会将当前未排序部分的最大元素“冒泡”到末尾，因此需要遍历n次。...、基准元素和右子数组合并起来。
只要变量j比0大（因为数组的第一个索引是0——没有负值的索引）并且数组中前面的值比待比较的值大（行{5}），我们就把这个值移到当前位置上（行{6}）并减小j。最终，该项目能插入到正确的位置上。 4....然后将左右子序列合并，首先每次合并成两个元素的子序列，然后合并成四个元素的子序列，3 和 5 除外，它们会一直保留到最后一次迭代，那时会把它们合并成右子序列，然后再与最后的左子序列合并成最终的有序数组。...和简单地比较相邻元素相比，使用这种方案可以使离正确位置很远的元素更快地回到合适的位置。...由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。...算法的步骤如下： 找出待排序的数组中最大和最小的元素 统计数组中每个值为i的元素出现的次数，存入数组C的第i项 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加） 反向填充目标数组：将每个元素
，再次按原方法对比右移，到前一次右移到末尾的前一位结束 快速排序 选择最左边的数作为基点A，位置标记为i，最右边标记为j，然后i右移，遇到比A大的停下，j向左移动，遇到比A小的停下，然后i和j对应的数交换...当i和j相遇后，i,j对应的数要和A对比，比A大，继续走，当i或j有个数比A小时，该数与A交换；然后分成两份，交换数的左边和右边各自执行同样的算法 合并排序 合并排序简而言之就是分而治之的思想 把所有数据一步步拆分...可能会进行n次的比较和交换才能将该数据移至正确位置。而希尔排序会用较大的步长移动数据，所以小数据只需进行少数比较和交换即可到正确位置 桶排序 工作的原理是将数组分到有限数量的桶里。...计数排序使用一个额外的数组 {\displaystyle C} C ，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。...算法的步骤如下： 找出待排序的数组中最大和最小的元素 统计数组中每个值为i的元素出现的次数，存入数组 C 的第i项 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加） 反向填充目标数组：将每个元素
*logN)O(n∗logN) 非稳定排序 快速排序 O(n∗logN)O(n*logN)O(n∗logN) 非稳定排序 计数排序 O(n+k)O(n+k)O(n+k) 稳定排序 基数排序 O(n+k)...归并排序的分治思想 分解：分解待排序的n个元素的序列成各具 n/2 个元素的子序列 解决：使用归并排序递归地排序子序列 合并：合并两个已经排序的子序列以产生已排序的答案。...4、原地排序 ☘️快速排序 同样是分治思想。...4、原地排序 O(n+k)O(n+k)O(n+k)的排序算法、非比较排序 ☘️计数排序 把数组元素作为数组的下标，然后用一个临时数组统计该元素出现的次数，例如 temp[i] = n, 表示元素 i...计数排序比较适用于待排序数组中最大值和最小值相差不大的排序。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。...算法思想： 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区； 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn...对这两个子序列分别采用归并排序；3. 将两个排序好的子序列合并成一个最终的排序序列。...计数排序基于一个假设，待排序数列的所有数均为整数，且出现在（0，k）的区间之内。...算法思想： 找出待排序的数组中最大和最小的元素； 统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项； 对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）； 向填充目标数组
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 ?...算法思想： 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区； 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn...对这两个子序列分别采用归并排序；3. 将两个排序好的子序列合并成一个最终的排序序列。 ?...计数排序基于一个假设，待排序数列的所有数均为整数，且出现在（0，k）的区间之内。...算法思想： 找出待排序的数组中最大和最小的元素； 统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项； 对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）； 向填充目标数组
十大排序讲解顺序 为了方便大家查找，我这里弄一个伪目录，没有跳转功能。...4、原地排序 8、计数排序 计数排序是一种适合于最大值和最小值的差值不是不是很大的排序。...桶排序就是把最大值和最小值之间的数进行瓜分，例如分成 10 个区间，10个区间对应10个桶，我们把各元素放到对应区间的桶中去，再对每个桶中的数进行排序，可以采用归并排序，也可以采用快速排序之类的。...min = arr[i]; 12 if(max < arr[i]) 13 max = arr[i]; 14 } 15 //和优化版本的计数排序一样...如果还是不懂的话我还给你准备了优质的文章讲解：为什么说O(n)复杂度的基数排序没有快速排序快？
计数排序算法思想 使用一个额外的数组counts，其中第i个元素counts[i]是待排序数组arr中值等于i的元素个数。 然后根据数组counts来将arr中的元素排到正确的位置....统计数组中每个值为i的元素出现的次数，存入数组的第i项 对所有的计数累加（从counts中的第一行素开始，每一项和前一项累加） 反向填充目标数组：将每个元素i放在新数组的第counts[i]项，每放一个元素就要将...所以计数排序对于数据范围很大的数组，需要大量的时间和内存。...如果全为负数，则求平凡之后按照从大到小进行排序的；如果是既有负数，也有正数，可以找到中间分界点，递归的进行求平方，然后合并两个有序数组； 双指针，从开头和结尾开始遍历，因为平方的曲线是一个u型，最大值一般出现在两头处...当遍历结束后，所有在arr2中出现过的元素就已经有序了。 此时还剩下没有在arr2中出现过的元素，因此我们还需要对整个数组frequency 进行一次遍历。
算法分类 冒泡排序(重点) 选择排序 插入排序 归并排序（重点） 快速排序（重点） 堆排序（重点） 计数排序 基数排序 本文的重点排序方法在：冒泡排序，归并排序，快速排序，桶排序。...之前一直以为快排和二分法有关，但是其实是分治法的应用。 【算法描述】 快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。...【分步详解】 堆（二叉堆）可以视为一棵完全的二叉树。完全二叉树的一个优秀的性质就是，除了最底层之外，每一层都是满的 二叉堆一般分为两种：最大堆和最小堆。...最大堆 ：最大堆中的最大元素在根结点（堆顶）；堆中每个父节点的元素值都大于等于其子结点（如果子节点存在） 最小堆：最小堆中的最小元素出现在根结点（堆顶）；堆中每个父节点的元素值都小于等于其子结点（如果子节点存在...i的元素出现的次数，存入数组C的第i项； 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）； 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 1.1 算法描述 比较相邻的元素。...般情况下.标准元素值的分布是随机的,这样的二支树的深度接近于log2n,所以快速排序算法的平均(或称期望)时间复杂度为O(nlog2n) 7、堆排序（Heap Sort） 堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法...7.1 算法描述 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区； 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区...8.1 算法描述 找出待排序的数组中最大和最小的元素； 统计数组中每个值为i的元素出现的次数，存入数组C的第i项； 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）； 反向填充目标数组：将每个元素...(0<count[i]--)a[k++]=i;//到正确的位置 } } 8.4 算法分析 计数排序是一个稳定的排序算法。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
