细说八大java 排序算法

算法（Algorithm）是指解决问题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。排序算法，就是如何使得记录按照要求排列的方法。Java排序算法在很多领域中发挥着举足轻重的作用，在大量数据的处理方面尤为出色。四两拨千斤的道理大家都懂得，一个优秀的算法不仅可以节省大量的资源，同时也可以加快目标项目的进度，提高其运行的速度。对于排序，我们首先要求其具有一定的稳定性，即当两个相同的元素同时出现于某个序列之中，则经过一定的排序算法之后，两者在排序前后的相对位置不发生变化。

然而在各个领域中结合实际情况，考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，需要进行大量的推理和分析，同时大量的数据处理和演算也是必不可少的步骤。我们之所以能够了解大量的高质量的排序算法是因为我们站在了巨人们的肩膀上，才能预见这么多优秀的算法从而完成许多难以完成的大型程序和项目。接下来，我们来了解一下java中的八大排序算法。

一、直接插入

- 1.基本思路

在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

- 2.代码实现

1）遍历数组，每次循环从第二个数字往前插入

2）设定插入数和得到已经排好序列的最后一个数的位数。temp和j=i-1。

3）从最后一个数开始向前循环，如果插入数小于当前数，就将当前数向后移动一位。

public static void insertSort(int[] data) {

    int temp;

    for(int i = 1;i < data.length; i++){// 取第i个数,插入前边的有序的序列

        temp = data[i];

        int j;

        for(j = i - 1; j>=0; j--) {// 从第i-1的位置上开始比较

            if(data[j] > temp) {// 若前面的数大，则往后挪一位

                data[j+1] = data[j];

            } else {

                break;// 否则，说明要插入的数比较大

            }

        }

        data[j+1] = temp;// 找到这个位置，插入数据

    }

}

- 3.时间复杂度和空间复杂度

直接插入排序的平均复杂度为O(n²)，最坏时间复杂度：O(n²)，空间复杂度：O(1)，没有分配内存。

二、希尔排序

针对直接插入排序下的效率问题，有人对此进行了改进与升级，这就是现在的希尔排序。希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

1.基本思路

1）数的个数为length，i=length/2，将下标差值为i的数分为一组，构成有序序列。

2）再取i=i/2 ，将下标差值为i的数分为一组，构成有序序列。

3）重复第二步，直到k=1执行简单插入排序。

2.代码实现

1）遍历数组，每次循环从第二个数字往前插入

2）设定插入数和得到已经排好序列的最后一个数的位数。temp和j=i-1。

3）从最后一个数开始向前循环，如果插入数小于当前数，就将当前数向后移动一位。

（1）首先确定每一组序列的下标的间隔，循环每次需要的间隔：int i = length/2; i >0 ; i /= 2

（2）然后将每一组序列中元素进行插入排序，第二组第一个插入的数字是第一组第一个插入数字之后的那个数组，从i之后每个数字都要进行插入排序，就是插入的序列是各自不同的序列，不是一个一个子序列循环，而是在一个循环中for (int j=i;j

（3）直到i=0为止。

public static void shellSort(int[] array) {

    int length = array.length;

    for (int i = length / 2; i > 0; i /= 2) {//序列的间隔，一直到间隔为一，这时候就只有一个子序列

        for (int j = i; j < length; j++) {//从i之后每个数字都要进行插入排序，就是插入的序列是各自不同的序列

            int temp = array[j];//里面就是直接插入算法

            int k;

            for (k = j - i; k >= 0; k -= i) {//实现各个数字插入排序到不同的序列中，直到间隔为1的时候，只有一个序列，就是完全的一个直接插入排序

                if (temp < array[k]) {

                    array[k + i] = array[k];

                } else {

                    break;

                }

            }

            array[k + i] = temp;//把数字插入到位置上

        }

    }

    System.out.println(Arrays.toString(array));

}

3.时间复杂度和空间复杂度

希尔排序的平均时间复杂度为O(n²)，空间复杂度O(1) 。

三、简单选择

1.基本思路

基本原理如下：对于给定的一组记录，经过第一轮比较后得到最小的记录，然后将该记录的位置与第一个记录的位置交换；接着对不包括第一个记录以外的其他记录进行第二次比较，得到最小记录并与第二个位置记录交换；重复该过程，直到进行比较的记录只剩下一个为止。

2.代码实现

1）确定要插入最小值的位置，从0开始到最后int i = 0; i

2）将每次开始位置上的数字暂定为最小值min,从开始数字之后一个个和min比较，再把最小值存放到min

3）将最小值所在位置上的数字和开始位置上的数字交换

public static void selectSort(int[] array) {

    int len = array.length;

    for (int i = 0; i < len; i++) {//确定每次开始的位置

        int min = array[i];//设定开始数字为最小的值最小值

        int flag = i;

        for (int j = i + 1; j < len; j++) {//把最小值存放到min,从开始数字向后一个个和min比较，再把最小值存放到min

            if (min > array[j]) {

                min = array[j];

                flag = j;

            }

        }

        if (flag != i) {

            array[flag] = array[i];

            array[i] = min;

        }

    }

    System.out.println(Arrays.toString(array));

}

3.时间复杂度和空间复杂度

简单选择排序的时间复杂度为O(n²)

四、堆排序

1.基本思路

1）若array[0，…，n-1]表示一颗完全二叉树的顺序存储模式，则双亲节点指针和孩子结点指针之间的内在关系如下：

任意一节点指针 i：

父节点：i==0 ? null : (i-1)/2

左孩子：2*i + 1

右孩子：2*i + 2

2）堆得定义

n个关键字序列array[0，...，n-1]，当且仅当满足下列要求：(0 <= i <= (n-1)/2)

① array[i] <= array[2*i + 1] 且 array[i] <= array[2*i + 2]； 称为小根堆；

② array[i] >= array[2*i + 1] 且 array[i] >= array[2*i + 2]； 称为大根堆；

3）建立大顶堆

n个节点的完全二叉树array[0，…，n-1]，最后一个节点n-1是第(n-1-1)/2个节点的孩子。对第(n-1-1)/2个节点为根的子树调整，使该子树称为堆。

对于大根堆，调整方法为：若【根节点的关键字】小于【左右子女中关键字较大者】，则交换。

之后向前依次对各节点（(n-2)/2 - 1）~ 0为根的子树进行调整，看该节点值是否大于其左右子节点的值，若不是，将左右子节点中较大值与之交换，交换后可能会破坏下一级堆，于是继续采用上述方法构建下一级的堆，直到以该节点为根的子树构成堆为止。

反复利用上述调整堆的方法建堆，直到根节点。

4）堆排序（大顶堆）

①将存放在array[0，...，n-1]中的n个元素建成初始堆；

②将堆顶元素与堆底元素进行交换，则序列的最大值即已放到正确的位置；

③将数组中array[0，...，n-1]前n-1个元素再次形成大根堆，再重复第②③步，直到堆中仅剩下一个元素为止。

3.时间复杂度和空间复杂度

时间复杂度:建堆：o(n)，每次调整o(log n)，故最好、最坏、平均情况下：o(n*logn);

五、冒泡排序

打个小guang告，搜索拼duoduo店铺： Boush杂货铺

物美价廉，你值得拥有

1.基本思路

一次冒泡将序列中从头到尾所有元素两两比较，将最大的放在最后面。

将剩余序列中所有元素再次两两比较，将最大的放在最后面。

重复第二步，直到只剩下一个数。

2.代码实现

/**

 * @author fupeng

 * 冒泡排序优化第二版

 * 第一版优化增加flag标记，没有数字交换直接return，最优时间复杂度O(n)

 * 第二版优化，增加tempPostion记录内循环最后一次交换的位置，来缩减内循环的次数

3.时间复杂度和空间复杂度

冒泡排序的最好时间复杂度为O(n),最坏时间复杂度为O(n²),平均时间复杂度为O(n²),空间复杂度为O(1),它是一种稳定的排序算法。

六、快速排序

1.基本思路

快速排序使用分治策略来把一个序列（list）分为两个子序列（sub-lists）。步骤为：

1）从数列中挑出一个元素，称为"基准"（pivot）。

2）重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

3）递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

2.代码实现

public static void quickSort(int[] array) {

    sort(array, 0, array.length - 1);

    System.out.println(Arrays.toString(array));

}

private static void sort(int[] a, int low, int high) {

    int i = low;

    int j = high;

    if (a.length <= 1) {

        return;

    }

  if (i = j) {

        return;

    }

    int index = a[i];

    while (i < j) {

        while (i < j && a[j] >= index)

            j--;

        if (a[j] < index)

            a[i++] = a[j];

        while (i < j && a[i] <= index)

            i++;

        if (a[i] > index)

            a[j--] = a[i];

    }

    a[i] = index;

    sort(a, low, i - 1);

    sort(a, i + 1, high);

}

3.时间复杂度和空间复杂度

虽然 快排的时间复杂度达到了 O(n²)，但是在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好。

七、归并排序

1.基本思路

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

1）分而治之

可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。

2）合并相邻有序子序列

再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。

2.代码实现

归并排序排序的代码实现由于比较复杂可以参考网上的一些例子。

3.时间复杂度和空间复杂度

归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。

八、基数排序

1.基本思路

1.基数排序的思想就是先排好各位，然后排好各位的基础上排十位，以此类推，直到遍历最高位 次，排序结束（仔细理解最后一句话）

2.基数排序不是比较排序，而是通过分配和收集的过程来实现排序

3.初始化10个桶(固定的)，桶下标为0-9

4.通过得到待排序数字的个十百等位的数字，把这个数字对应的item放到对应的桶中

5.基数排序有两种排序方式：LSD和MSD，最小位优先(从右边开始)和最大位优先(从左边开始)

2.代码实现

基数排序的代码实现由于比较复杂可以参考网上的一些例子。

3.时间复杂度和空间复杂度

归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。

在学习了上述的八种java排序算法后，大家已经快速掌握了相关的专业知识。尽管java排序算法的种类有点繁杂，但这也是排序算法的经过许多的算法大师经过无数实践和推导的结果，希望大家能珍惜这份宝贵的果实，这也是我们在今后的编程中解决大量算法问题的利刃。