本博主要介绍Java中几种常见的排序算法；

/*
排序方法的演示
1）插入排序（直接插入排序、希尔排序）
2）交换排序（冒泡排序、快速排序）
3）选择排序（直接选择排序、堆排序）
4）归并排序
5）分配排序（基数排序）
所需辅助空间最多：归并排序
所需辅助空间最少：堆排序
平均速度最快：快速排序
不稳定：快速排序，希尔排序，堆排序。
*/

其中，文字部分来自于网上整理，代码部分属于自己实现的（堆排序，归并排序，基数排序代码来自网上），主要用于自己学习，有空的时候翻翻老笔记看看

　　直接插入排序的基本操作是将一个记录插入到已经排好的有序表中，从而得到一个新的、记录数增1的有序表。对于给定的一组记录，初始时假定第一个记录自成一个有序序列，其余记录为无序序列。接着从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中，直到最后一个记录插到有序序列中为止。

　　当最好的情况，也就是要排序的表本身就是有序的，此时只有数据比较，没有数据移动，时间复杂度为O(n)。 
当最坏的情况，即待排序的表是逆序的情况，此时需要比较次数为：2+3+…+n=(n+2)(n-1)/2 次,而记录移动的最大值也达到了 (n+4)(n-1)/2 次. 
如果排序记录是随机的，那么根据概率相同的原则，平均比较和移动次数约为次n²/4，因此，得出直接插入排序发的时间复杂度为。从这里可以看出，同样的是时间复杂度，直接插入排序法比冒泡和简单选择排序的性能要好一些。

package MySort;

import java.util.Arrays;

public class MySortTest2 {

    public static void main(String[] args) {
        // 原始数据
        int[] data1 = { 1, 3, 6, 2, 4, 8, 9, 5, 12 };
        // 1.插入排序:直接插入排序
        System.out.println("插入排序：\t" + Arrays.toString(insertSort(data1)));
    }

    // 1.插入排序:直接插入排序
    private static int[] insertSort(int[] data) {
        for (int i = 1; i < data.length; i++) {
            int insertData = data[i]; // 要插入到数组中的数据
            int j = i - 1; // 临时脚标
            while (j >= 0 && insertData < data[j]) {
                data[j + 1] = data[j];// 将原始数据后移
                j--;
            }
            data[j + 1] = insertData; // 将如要插入的数据插入到此处
        }
        return data;
    }

}

　　希尔排序也成为“缩小增量排序”，其基本原理是，现将待排序的数组元素分成多个子序列，使得每个子序列的元素个数相对较少，然后对各个子序列分别进行直接插入排序，待整个待排序列“基本有序”后，最后在对所有元素进行一次直接插入排序。因此，我们要采用跳跃分割的策略：将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。希尔排序是对直接插入排序算法的优化和升级。 
　　所谓的基本有序，就是小的关键字基本在前面，大的基本在后面，不大不小的基本在中间，例如｛2,1,3,6,4,7,5,8,9,｝就可以称为基本有序了。但像｛1,5,9,3,7,8,2,4,6｝这样，9在第三位，2在倒数第三位就谈不上基本有序。

　　希尔排序的关键并不是随便分组后各自排序，而是将相隔某个“增量”的记录组成一个子序列，实现跳跃式移动，使得排序的效率提高。需要注意的是，增量序列的最后一个增量值必须等于1才行。另外，由于记录是跳跃式的移动，希尔排序并不是一种稳定的排序算法。 
希尔排序最好时间复杂度和平均时间复杂度都是，最坏时间复杂度为。

package MySort;

import java.util.Arrays;

public class MySortTest3 {

    public static void main(String[] args) {
        // 原始数据
        int[] data = { 1, 3, 6, 2, 4, 8, 9, 5, 12 };
        // 1.插入排序:希尔排序
        System.out.println("希尔排序：\t" + Arrays.toString(shellSort(data)));

    }