排序

一、梳排序简介 梳排序是冒泡排序的一种优化方案，主要是为了解决冒泡排序中的尾部小数值问题。它主要的思想是通过比较元素和固定步长位置上的数据，先进行部分优化，然后逐步减少步长，以此来对数据进行预处理。 以数组 [3,1 5, 2, 4] 为例，假设步长是 2，那么就分别处理 [3, 5, 4] 和 [1, 2]， ... 阅读更多

一、堆排序原理 通过最大堆的性质可以知道：一个堆中最大的元素总是在堆顶的，即数组下标 0 的位置。基于这一点，我们可以每次都把堆中的最大值提取出来，放到当前数组的后面。然后重新构建最大堆，重复这个过程，以此来完成一个数组的排序。 例如，一个已知的最大堆为： 把最大的元素 16 提取出来，放到最后。然后重新建 ... 阅读更多

一、计数排序 其基本思想为：假设 n 个输入的元素中的每一个都是在 0 到 k 之间的一个整数，对于每一个输入元素 x，确定小于 x 的元素个数，直接把 x 放在它输出的数组中的位置上。例如有 17 个元素小于 x，则 x 就应该在数组的第 18 个位置上。当有几个元素相同时，这一方案就要略作修改，不能都放在同一个位置上。 计数排序需 ... 阅读更多

一、原理 冒泡排序的原理很简单， 它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序 （如从大到小、首字母从从 Z 到 A） 错误就把他们交换过来。 冒泡排序是一种稳定的排序算法。 冒泡排序不管在什么情况下，时间复杂度都是 O() 。 对比插入排序来说，在平均的情况下，插入排序性能是冒泡排序的两倍。 ... 阅读更多

一、原理 选择排序 （Selection sort） 是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小 （或最大） 的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小 （大） 元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序 ... 阅读更多

一、原理 选择排序的原理是分治，把排序序列切分成若干个小组后分别排序。每次排序都以随机的一个元素作为哨兵 （一般都以排序区间的中间元素或者首元素作为哨兵），比他大的元素都放到右边，比它小的都放到左边。然后分别对该元素左边和右边的元素再法排序，直到所有的元素都是有序状态。 具体的排序过程描述为： 选取一 ... 阅读更多