Java常见排序算法

       希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

基本思想

子主题

代码实现

希尔排序

       用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它左边，所有比它大的数都放到它右边，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。

排序原理

快速排序

实现思路

插入排序

       从头至尾扫描序列，找出最小的一个元素，和第一个元素交换，接着从剩下的元素中继续这种选择和交换方式，最终得到一个有序序列。

算法思想

选择排序

        归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案\"修补\"在一起，即分而治之)。

归并排序

       堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。堆  堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

堆排序基本思想及步骤

堆排序

       基数排序不需要进行元素的比较与交换。如果你有一些算法的功底，或者丰富的项目经验，我想你可能已经想到了这可能类似于一些“打表”或是哈希的做法。而计数排序则是打表或是哈希思想最简单的实现。

       在算法的原理中，我们是以一张二维数组的表来存储这些无序的元素。使用二维数组有一个很明显的不足就是二维数组太过稀疏。数组的利用率为 10%。       在寻求优化的路上，我们想到一种可以压缩空间的方法，且时间复杂度并没有偏离得太厉害。那就是设计了两个辅助数组，一个是 count[]，一个是 bucket[]。count 用于记录在某个桶中的最后一个元素的下标，然后再把原数组中的元素计算一下它应该属于哪个“桶”，并修改相应位置的 count 值。直到最大数的最高位也被添加到桶中，或者说，当所有的元素都被被在第 0 个桶中，基数排序就结束了。

算法优化

基数排序

      大家一定都喝过汽水吧，汽水中常常有许多小小的气泡，往上飘，这是因为组成小气泡的二氧化碳比水要轻，所以小气泡才会一点一点的向上浮。而冒泡排序之所以叫冒泡排序，正是因为这种排序算法的每一个元素都可以向小气泡一样，根据自身大小，一点一点向着数组的一侧移动。

专业术语

冒泡排序

Java常见排序算法