分类: Java 算法 排序

标签: bucketsort radixsort 基数排序 桶排序

基数排序：对于十进制数字来说，将要排序的数字对齐排成一列，我们可以从低位起，假设目标数组元素不超过3位，第一次我们把这列数字按个位数排序，在这基础上第二次我们把这些数字再按十位数排序，第三次按百位数排序，三趟下来得到的数组就是已排序的数组。在对个位数排序时，我们可以采用下面的方法，用10个标志为0..9的桶，桶0放入所有个位数为0的数，桶1放入所有个位数为1的数，最后将所有桶的数从桶0开始输出，这样得到的数组就是按个位数排序的数组。然后，其余高位数类似处理。

桶排序：其实基数排序已经用到了桶排序的思想。桶排序假设输入数组符合均匀发布，假设n个元素都是均匀而独立的分布在区间[0,1)上， 然后将区间[0,1)划分为n个相同大小的子区间，这些子区间就是桶，然后对桶中的元素进行排序（一般使用插入排序），最后输出桶中的元素，得到排序数组。桶排序假设输入均匀分布，所以一般每个桶中的元素不会很多，因而运行得很快。

基数排序跟桶排序的时间复杂度都是O(n)。

分类: Java 算法 排序

标签: countingsort 计数排序

计数排序假设n个输入元素中的每一个都是介于0到k之间的整数，此处k为某个整数。

计数排序算法的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。例如，如果输入序列中只有17个元素的值小于x的值，则x可以直接存放在输出序列的第18个位置上。当然，如果有多个元素具有相同的值时，我们不能将这些元素放在输出序列的同一个位置上，因此，上述方案还要作适当的修改。

计数排序的时间复杂度为O(n)，当然是有条件的。计数排序不是原地排序。

分类: Java 算法 排序

标签: quicksort 分区 快速排序

快速排序（QuickSort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列—–摘自百度百科。

快速排序的核心算法是分区，如何将一个数组分成两个子数组，前面的数组所有元素都小于等于后面数组的所有元素，关键字夹在两个数组中间。实现见partition方法，这里关键字取的是数组最后一个元素，实际上取任何元素都行。

快速排序的时间复杂度为O(nlogn)，是原地排序。

分类: Java 算法 排序

标签: buildmaxheap heapsort maxheapify 堆排序 最大堆

堆积排序(Heapsort)是指利用堆积树（堆）这种资料结构所设计的一种排序算法，可以利用数组的特点快速定位指定索引的元素。

堆排序原理有点点复杂，文字我描述不清楚，画图是最有助于理解了的，想深入研究的朋友建议参考算法导论中有关堆排序的描述。

堆排序中有几个重要的过程：Max-Heapify，是用来保持最大堆性质；Build-Max-Heap是用来把一个无序数组建立成最大堆；Heap-Sort则是把一个数组利用最大堆性质进行原地排序。

堆排序的时间复杂度为O(nlog n) ，同合并排序，但相比合并排序他的优点是可以在原数组上实现排序。

分类: Java 算法 排序

标签: sort 排序 bubblesort 冒泡排序

冒泡排序也是常用的排序方法之一，他的优点在于可读性好，容易编程实现。他的原理是，对于长度为n的数组，做n-1趟比较，每一趟比较，依次比较前后两数，小的数往前放，大的数往后放，相当于气泡往上升，所以叫冒泡排序。每一趟依次找出数组中最大的数，因此，每趟可以依次少比较一个数，只需比较到n-i+1个数即可。

冒泡排序的时间复杂度为O(n²)。

分类: Java 算法 排序

标签: sort 排序 mergesort 合并排序 递归

合并排序是分治法的典型应用，就是我们常说的递归。合并排序是将两个已经排好序的数组合并成一个有序数组的过程，所以只需保证子数组有序，那么合并出来的数组也是有序的，那剩下的问题就是如何递归地对子数组进行排序。

合并排序是不能在原数组上实现的，他的时间复杂度为O(nlog n)。在上面的代码中，核心算法是merge合并算法。在该算法的实现中，对要合并的目标数组进行了拷贝，然后替换源数组的值，这样的话可读性较好，但实际上也是一件影响效率的工作。参考网上其它的算法，一般是返回一个新的排序数组，各中优略请读者自己把握。

分类: Java 算法 排序

标签: insertionsort sort 排序 插入排序

插入排序是排序算法中很简单的一种排序，适用于少量元素排序。对他的描述，《算法导论》一书中的例子我觉得很形象。插入排序的算法原理类似于打牌中的摸牌：没摸牌时，我们手中是空的，接着，一次摸一张牌，每次摸起时，我们按照大小把它排列，无论什么时候，我们手中的牌都是已排好序的。

在实现时，我们使用两个数组，数组A用来模拟待摸的牌，数组B用来模拟我们自己手上抓的牌，每次我们从A中取一张牌插到B中，不管什么时候，B中的牌都是排好序的。

插入排序是可以在原数组上实现的，时间复杂度为O(n²)。