JAVA 九种排序算法详解（上）

一、排序：

引入: 排序算法就是指通过特定的算法因式将一组或多组数据按照既定模式进行重新排序，这种新序列遵循着一定的规则，体现出一定的规律，因此，经处理后的数据便于筛选和计算，大大提高了计算效率。

1.排序的定义：

所谓排序算法，即通过特定的算法因式将一组或多组数据按照既定模式进行重新排序。这种新序列遵循着一定的规则，体现出一定的规律，因此，经处理后的数据便于筛选和计算，大大提高了计算效率。

对于排序，我们首先要求其具有一定的稳定性，即当两个相同的元素同时出现于某个序列之中，则经过一定的排序算法之后，两者在排序前后的相对位置不发生变化。换言之，即便是两个完全相同的元素，它们在排序过程中也是各有区别的，不允许混淆不清。

排序(Sorting) 是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列。

2.排序的方式：

排序就是把集合中的元素按照一定的次序排序在一起，排序大的分类可以分为两种：内排序和外排序。在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使用外存，则称为外排序。下面讲的排序都是属于内排序。

内排序有可以分为以下几类：

• 插入排序： 直接插入排序、二分法插入排序、希尔排序

• 选择排序： 简单选择排序、堆排序

• 交换排序： 冒泡排序、快速排序

• 归并排序

• 基数排序

接下来我们就这以上几种排序进行详细讲解

二、直接插入排序

1.基本思想：

每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置（从后向前找到合适位置后），直到全部插入排序完为止

2.实现过程：

• 原数组值为：

• 32 , 43, 23, 13, 5

• 第一轮比较：将第一个数和第二个数排序，然后构成一个有序序列，得到结果：

• 32 , 43, 23, 13, 5

• 第二轮比较：将第三个数插入，构成新的有序序列，得到结果：

• 23 , 32, 43, 13, 5

• 第三轮比较：将第四个数插入，构成新的有序序列，得到结果为：

• 13 , 23, 32, 43, 5

• 第四轮比较：将第五个数插入，构成新的有序序列，得到结果为：

• 5 , 13, 23, 32, 43

实现过程如图所示：

3.实现代码:

package cn.hz;
/** * @author hz * @version 1.0 * 直接插入排序 * 需求分析: * 首先设定插入次数，即循环次数，for(int i=1;i<length;i++)，1个数的那次不用插入。 * 设定插入数和得到已经排好序列的最后一个数的位数。insertNum和j=i-1。 * 从最后一个数开始向前循环，如果插入数小于当前数，就将当前数向后移动一位。 * 将当前数放置到空着的位置，即j+1。 */public class Demo1 {    public static void main(String[] args) {        int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1};  //定义需要排序数组        System.out.println("直接插入排序前");        for (int i:a){            System.out.print(i+"\t");        }        int length=a.length;//数组长度，将这个提取出来是为了提高速度。        int insertNum;//要插入的数        for(int i=1;i<length;i++){//插入的次数            insertNum=a[i];//要插入的数            int j=i-1;//已经排序好的序列元素个数            while(j>=0&&a[j]>insertNum){//序列从后到前循环，将大于insertNum的数向后移动一格                a[j+1]=a[j];//元素移动一格                j--;            }            a[j+1]=insertNum;//将需要插入的数放在要插入的位置。        }        System.out.println("\n直接插入排序后");        for (int i:a){            System.out.print(i+"\t");        }
    }}

实现效果：

4.分析：

文件初态不同时，直接插入排序所耗费的时间有很大差异。若文件初态为正序，则每个待插入的记录只需要比较一次就能够找到合适的位置插入，故算法的时间复杂度为 O(n)，这时最好的情况。若初态为反序，则第 i 个待插入记录需要比较 i+1 次才能找到合适位置插入，故时间复杂度为 O(n2)，这时最坏的情况。

直接插入排序的平均时间复杂度为 O(n2)。

5.稳定性总结：

插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有 1 个元素，也就是第一个元素（默认它有序）。

比较是从有序序列的末尾开始，也就是把待插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面。

否则一直往前找直到找到它该插入的位置。如果遇见一个与插入元素相等的，那么把待插入的元素放在相等元素的后面。

所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序仍是排好序后的顺序，所以插入排序是稳定的。

三、二分法插入排序

1.基本思想:

基本思想：二分法插入排序的思想和直接插入一样，只是找合适的插入位置的方式不同，这里是按二分法找到合适的位置，可以减少比较的次数。

2.实现过程：

二分法排序其实是一种改进的插入排序，也是通过查找待插入位置来实现排序，这和插入排序是类似的。

算法思想，在插入第 i 个元素时，对前面的 0～i-1 元素进行折半，先跟他们中间的那个元素比，如果小，则对前半部分再进行折半，否则对后半进行折半，

直到 left<right，然后再把第 i 个元素前 1 位与目标位置之间的所有元素后移，再把第 i 个元素放在目标位置上。

二分法实际上没有进行排序，只进行了有查找。所以当找到要插入的位置时，必须从移动最后一个记录开始，向后移动一位，再移动倒数第 2 位，直到要插入的位置的记录移后一位。如图所示：

3.实现代码：

package cn.hz.demo2;
/** * @author hz * @version 1.0 * 二分法插入排序 * 需求分析： * 插入方式同直接插入相似，只是插入的位置的方式不同 */public class Demo2 {    public static void main(String[] args) {        int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1};  //定义需要排序数组        System.out.println("二分法插入排序前");        for (int i:a){            System.out.print(i+"\t");        }        for (int i = 0; i < a.length; i++) {             int temp = a[i];             int left = 0;             int right = i-1;             int mid = 0;             while(left<=right){                mid = (left+right)/2;                if(temp<a[mid]){                    right = mid-1;                }else{                    left = mid+1;                }             }            for (int j = i-1; j >= left; j--) {                a[j+1] = a[j];             }            if(left != i){                 a[left] = temp;             }        }        System.out.println("\n二分法插入排序后");        for (int i:a){            System.out.print(i+"\t");        }
    }}

实现效果：

4.分析：

当然，二分法插入排序也是稳定的。

二分插入排序的比较次数与待排序记录的初始状态无关，仅依赖于记录的个数。当 n 较大时，比直接插入排序的最大比较次数少得多。但大于直接插入排序的最小比较次数。算法的移动次数与直接插入排序算法的相同，最坏的情况为 n2/2，最好的情况为 n，平均移动次数为 O(n2)。

5.稳定性总结：

同直接插入排序一致。

四、希尔排序

1.基本思想：

先取一个小于 n 的整数 d1 作为第一个增量，把文件的全部记录分成 d1 个组。所有距离为 d1 的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量 d2<d1 重复上述的分组和排序，直至所取的增量 dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。

2.实现过程：

希尔排序主要解决直接排序数据量大时问题。

• 原数组值：

• 32 , 43, 23, 13, 5

• 首先将数的个数设为 n，取奇数 k=n/2 (n 为奇数时+1)，将下标差值为 k 的书分为一组，构成有序序列。

• 如上共 5 个数，k=n/2=3(n 为奇数+1 得 6)，所以 32-13 为一组，43-5 为一组，23 单独一组，将各自组数字进行相应排序，得到结果如下：

• 13 , 5, 23, 32, 43

• 再取 k=k/2 ，将下标差值为 k 的书分为一组，构成有序序列。

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

• 由于 k 已经等于 1，所以后续进行简单插入排序，详解参考简单插入排序...

• 实现过程如图所示：

3.实现代码：

package cn.hz.demo2;
/** * @author hz * @version 1.0 * * 希尔排序 * 需求分析： * 首先确定分的组数。 * 然后对组中元素进行插入排序。 * 然后将length/2，重复1,2步，直到length=0为止。 */public class Demo3 {    public static void main(String[] args) {        int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1};  //定义需要排序数组        System.out.println("希尔排序前");        for (int i:a){            System.out.print(i+"\t");        }        int d  = a.length;        while (d!=0) {            d=d/2;            for (int x = 0; x < d; x++) {//分的组数                for (int i = x + d; i < a.length; i += d) {//组中的元素，从第二个数开始                    int j = i - d;//j为有序序列最后一位的位数                    int temp = a[i];//要插入的元素                    for (; j >= 0 && temp < a[j]; j -= d) {//从后往前遍历。                        a[j + d] = a[j];//向后移动d位                    }                    a[j + d] = temp;                }            }        }        System.out.println("\n希尔排序后");        for (int i:a){            System.out.print(i+"\t");        }    }}

实现效果：

4.分析

我们知道一次插入排序是稳定的，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。

希尔排序的时间性能优于直接插入排序，原因如下：

• 当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。

• 当 n 值较小时，n 和 n2 的差别也较小，即直接插入排序的最好时间复杂度 O(n)和最坏时间复杂度 0(n2)差别不大。

• 在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量 di 逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按 di-1 作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快

因此，希尔排序在效率上较直接插人排序有较大的改进。

希尔排序的平均时间复杂度为 O(nlogn)。

5.稳定性总结：

希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；

当元素基本有序时，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比 O(N^2)好一些。

由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，

但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱。

所以 shell 排序是不稳定的排序算法。