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排序是不稳定的排序算法。

五、简单选择排序：

1.基本思想：

在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止

2.实现过程：

原数组值：

32 , 43, 23, 13, 5
第一轮比较：遍历整个序列，将最小的数放在最前面，得到结果：

5 , 32, 43, 23, 13
第二轮比较：遍历剩下的序列，将最小的数放在最前面，得到结果：

5 , 13， 32, 43, 23
第三轮比较：遍历剩下的序列，将最小的数放在最前面，得到结果：

5 , 13， 23， 32， 43
第四轮比较：遍历剩下的序列，将最小的数放在最前面，得到结果

5 , 13， 23， 32， 43
第五轮比较：遍历剩下的序列，将最小的数放在最前面，得到结果

5 , 13， 23， 32， 43

实现过程如图所示：

在这里插入图片描述

3.实现代码：

package cn.hz.demo2;

/**
 * @author hz
 * @version 1.0
 *
 * 简单选择排序
 * 需求分析：
 * 遍历整个序列，将最小的数放在最前面。
 * 遍历剩下的序列，将最小的数放在最前面。
 * 重复第二步，直到只剩下一个数。
 */
public class Demo4 {
    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;
        for (int i = 0; i < length; i++) {//循环次数
            int key = a[i];
            int position=i;
            for (int j = i + 1; j < length; j++) {//选出最小的值和位置
                if (a[j] < key) {
                    key = a[j];
                    position = j;
                }
            }
            a[position]=a[i];//交换位置
            a[i]=key;
        }
        System.out.println("\n简单选择排序后");
        for (int i:a){
            System.out.print(i+"\t");
        }

    }
}

复制代码

实现效果：

在这里插入图片描述

4.分析：

简单选择排序是不稳定的排序。

时间复杂度：T(n)=O(n2)。

5.稳定性总结：

选择排序即是给每个位置选择待排序元素中当前最小的元素。比如给第一个位置选择最小的，在剩余元素里面给第二个位置选择次小的，

依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。

那么，在一趟选择时，如果当前锁定元素比后面一个元素大，而后面较小的那个元素又出现在一个与当前锁定元素相等的元素后面，那么交换后位置顺序显然改变了。

呵呵！比较拗口，举个例子：序列5 8 5 2 9，我们知道第一趟选择第1个元素5会与2进行交换，那么原序列中两个5的相对先后顺序也就被破坏了。

所以选择排序不是一个稳定的排序算法。

六、堆排序：

1.基本思想：

堆排序是一种树形选择排序，是对直接选择排序的有效改进。

堆的定义：具有n个元素的序列（h1,h2,…,hn),当且仅当满足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1） (i=1,2,…,n/2)时称之为堆。在这里只讨论满足前者条件的堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项（大顶堆）。完全二叉树可以很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。

思想: 初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储序，使之成为一个堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。

2.实现过程：

原数组值：

32 , 43, 23, 13, 5
将数组值构建大顶堆（堆顶元素（即第一个元素）必为最大项），得到结果如下：

在这里插入图片描述

将根节点与最后一个节点交换，然后断开最后一个节点。
重复第一、二步，直到所有节点断开。

重新建大顶堆：

根节点与最后节点交换，然后断开最后节点
重复第一、二步，直到所有节点断开。

得到结果5, 13, 23, 32, 43

3.实现代码：

package cn.hz.demo2;

/**
 * @author hz
 * @version 1.0
 *
 * 堆排序
 * 需求分析：
 * 将序列构建成大顶堆。
 * 将根节点与最后一个节点交换，然后断开最后一个节点。
 * 重复第一、二步，直到所有节点断开。
 *
 */
public class Demo6 {
    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 arrayLength=a.length;
        //循环建堆
        for(int i=0;i<arrayLength-1;i++){
            //建堆
            buildMaxHeap(a,arrayLength-1-i);
            //交换堆顶和最后一个元素
            swap(a,0,arrayLength-1-i);
        }

        System.out.println("\n堆排序后：");
        for (int i : a) {
            System.out.print(i + "\t");
        }
    }

    /**
     * 交换
     */
    private static void swap(int[] data, int i, int j) {
        int tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }

    /**
     * 对data数组从0到lastIndex建大顶堆
     */
    private static void buildMaxHeap(int[] data, int lastIndex) {
        //从lastIndex处节点（最后一个节点）的父节点开始
        for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
            //k保存正在判断的节点
            int k = i;
            //如果当前k节点的子节点存在
            while (k * 2 + 1 <= lastIndex) {
                //k节点的左子节点的索引
                int biggerIndex = 2 * k + 1;
                //如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在
                if (biggerIndex < lastIndex) {
                    //若果右子节点的值较大
                    if (data[biggerIndex] < data[biggerIndex + 1]) {
                        //biggerIndex总是记录较大子节点的索引
                        biggerIndex++;
                    }
                }
                //如果k节点的值小于其较大的子节点的值
                if (data[k] < data[biggerIndex]) {
                 //交换他们
                    swap(data, k, biggerIndex);
                //将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值
                    k = biggerIndex;
                } else {
                    break;
                }
            }
        }
    }
}
复制代码

实现效果:

在这里插入图片描述

4.分析：

堆排序也是一种不稳定的排序算法。

堆排序优于简单选择排序的原因：

直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。

堆排序可通过树形结构保存部分比较结果，可减少比较次数。

堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。

5.稳定性总结：

我们知道堆的结构是节点i的孩子为2i和2i+1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。

在一个长为n的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大（大顶堆）或者最小（小顶堆），这3个元素之间的选择当然不会破坏稳定性。

但当为n/2-1, n/2-2, …1这些个父节点选择元素时，就会破坏稳定性。

有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。

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

七、冒泡排序：

1.基本思想：

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换

2.实现过程：

原数组值：

32 , 43, 23, 13, 5
第一轮比较：将序列中所有元素两两比较，将最大的放在最后面，得到结果：

32 , 23, 13, 5, 43

如图所示：
第二轮比较：将剩余序列中所有元素两两比较，将最大的放在最后面,得到结果：

23 , 13, 5, 32, 43

如图所示：
第三轮比较：将剩余序列中所有元素两两比较，将最大的放在最后面,得到结果：

13 , 5, 23, 32, 43

如图所示：

在这里插入图片描述

第三轮比较：将剩余序列中所有元素两两比较，将最大的放在最后面,得到结果：

5 , 13, 23, 32, 43

如图所示：

3.实现代码：

package cn.hz.demo2;

/**
 * @author hz
 * @version 1.0
 *
 * 冒泡排序
 * 需求分析：
 * 设置循环次数。
 * 设置开始比较的位数，和结束的位数。
 * 两两比较，将最小的放到前面去。
 * 重复2、3步，直到循环次数完毕。
 *
 */
public class Demo7 {
    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 temp;
        for(int i=0;i<a.length;i++){
            for(int j=0;j<a.length-i-1;j++){
                if(a[j]>a[j+1]){
                    temp=a[j];
                    a[j]=a[j+1];
                    a[j+1]=temp;
                }
            }
        }
        System.out.println("\n冒泡排序后");
        for (int i:a){
            System.out.print(i+"\t");
        }

    }
}

复制代码

实现效果：

在这里插入图片描述

4.分析：

冒泡排序是一种稳定的排序方法。

若文件初状为正序，则一趟起泡就可完成排序，排序码的比较次数为n-1，且没有记录移动，时间复杂度是O(n)
若文件初态为逆序，则需要n-1趟起泡，每趟进行n-i次排序码的比较，且每次比较都移动三次，比较和移动次数均达到最大值∶O(n2)
起泡排序平均时间复杂度为O(n2)

5.稳定性总结：

冒泡排序就是把小的元素往前调（或者把大的元素往后调）。注意是相邻的两个元素进行比较，而且是否需要交换也发生在这两个元素之间。

所以，如果两个元素相等，我想你是不会再无聊地把它们俩再交换一下。

如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个元素相邻起来，最终也不会交换它俩的位置，所以相同元素经过排序后顺序并没有改变。

所以冒泡排序是一种稳定排序算法。

八、快速排序：

1.基本思想：

选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。

2.实现过程：

原数组值：

32 , 43, 23, 13, 5
第一轮比较：选择第一个数为p，小于p的数放在左边，大于p的数放在右边，结果如下：

32 , 13, 5, 32, 43

如图所示：

在这里插入图片描述

第二轮比较：递归的将p左边和右边的数都按照第一步进行，直到不能递归，结果如下：

13 , 5, 23, 32, 43

如图所示：
第三轮比较：递归的将p左边和右边的数都按照第一步进行，直到不能递归，结果如下：

5 , 13, 23, 32, 43

如图所示：

3.实现代码：

package cn.hz.demo2;

/**
 * @author hz
 * @version 1.0
 *
 * 快速排序
 * 需求分析：
 * 选择第一个数为p，小于p的数放在左边，大于p的数放在右边。
 * 递归的将p左边和右边的数都按照第一步进行，直到不能递归。
 *
 */
public class Demo8 {
    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 ia:a){
            System.out.print(ia+"\t");
        }
        //快速排序
        quickSort(a,0,a.length-1);
        System.out.println("\n快速排序后");
        for (int ia:a){
            System.out.print(ia+"\t");
        }

    }
    public static void quickSort(int[] numbers, int start, int end) {
        if (start < end) {
            int base = numbers[start]; // 选定的基准值（第一个数值作为基准值）
            int temp; // 记录临时中间值
            int i = start, j = end;
            do {
                while ((numbers[i] < base) && (i < end))
                    i++;
                while ((numbers[j] > base) && (j > start))
                    j--;
                if (i <= j) {
                    temp = numbers[i];
                    numbers[i] = numbers[j];
                    numbers[j] = temp;
                    i++;
                    j--;
                }
            } while (i <= j);
            if (start < j)
                quickSort(numbers, start, j);
            if (end > i)
                quickSort(numbers, i, end);
        }
    }
}

复制代码

实现效果：

在这里插入图片描述

4.分析：

快速排序是不稳定的排序。

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

当n较大时使用快排比较好，当序列基本有序时用快排反而不好。

5.稳定性总结：

快速排序有两个方向，左边的i下标一直往右走（当条件a[i] <= a[center_index]时），其中center_index是中枢元素的数组下标，一般取为数组第0个元素。

而右边的j下标一直往左走（当a[j] > a[center_index]时）。

如果i和j都走不动了，i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j。交换a[j]和a[center_index]，完成一趟快速排序。

在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为 5 3 3 4 3 8 9 10 11

现在中枢元素5和3(第5个元素，下标从1开始计)交换就会把元素3的稳定性打乱。

所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j]交换的时刻。

九、归并排序：

1.基本思想：

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

2.实现过程：

原数组值：

32 , 43, 23, 13, 5
第一轮比较：选择相邻两个数组成一个有序序列，结果如下：

32 , 43, 13, 23, 5

如图所示：
第二轮比较：选择相邻的两个有序序列组成一个有序序列，结果如下：

13, 23, 32, 43, 5

如图所示：
第三轮比较：选择相邻的两个有序序列组成一个有序序列，结果如下：

5， 13, 23, 32, 43,

如图所示：

3.实现代码：

package cn.hz.demo2;

/**
 * @author hz
 * @version 1.0
 *
 * 归并排序
 * 需求分析:
 * 选择相邻两个数组成一个有序序列。
 * 选择相邻的两个有序序列组成一个有序序列。
 * 重复第二步，直到全部组成一个有序序列。
 */
public class Demo9 {
    public static void main(String[] args) {
        int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8};
        System.out.println("归并排序之前：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
        //归并排序
        mergeSort(a,0,a.length-1);
        System.out.println();
        System.out.println("排序之后：");
        for (int i = 0; i < a.length; i++) {
           System.out.print(a[i]+" ");
        }
    }
    private static void mergeSort(int[] a, int left, int right) {
        if(left<right){
           int middle = (left+right)/2;
            //对左边进行递归
            mergeSort(a, left, middle);
            //对右边进行递归
            mergeSort(a, middle+1, right);
           //合并
           merge(a,left,middle,right);
        }
    }

    private static void merge(int[] a, int left, int middle, int right) {
       int[] tmpArr = new int[a.length];
       int mid = middle+1; //右边的起始位置
       int tmp = left;
       int third = left;
       while(left<=middle && mid<=right){
           //从两个数组中选取较小的数放入中间数组
            if(a[left]<=a[mid]){
                tmpArr[third++] = a[left++];
            }else{
                tmpArr[third++] = a[mid++];
            }
       }
         //将剩余的部分放入中间数组
        while(left<=middle){
           tmpArr[third++] = a[left++];
        }
        while(mid<=right){
            tmpArr[third++] = a[mid++];
        }
       //将中间数组复制回原数组
        while(tmp<=right){
          a[tmp] = tmpArr[tmp++];
        }
    }
}

复制代码

实现效果：

在这里插入图片描述

4.分析：

归并排序是稳定的排序方法。

归并排序的时间复杂度为O(nlogn)。

速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列

5.稳定性总结：

归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换)，

然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。

可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。

那么，在短的有序序列合并的过程中，稳定是是否受到破坏？

没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。

所以，归并排序也是稳定的排序算法。

十、基数排序：

1.基本思想：

将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

2.实现过程：

该排序方式比较麻烦，换一个值较多的数组进行讲解：

原数组值：

135， 242, 192， 93， 345， 11， 24， 19
第一轮比较：将所有的数的个位数取出，按照个位数进行排序，构成一个序列，结果如下：

11， 242， 192， 93， 24， 135， 345, 19

如图所示：
第二轮比较：将新构成的所有的数的十位数取出，按照十位数进行排序，构成一个序列，结果如下：

11, 19， 24， 135, 242，345， 192， 93

如图所示：
第三轮比较：将新构成的所有的数的百位数取出，按照百位数进行排序，构成一个序列，结果如下：

11， 19， 24， 93， 135， 192， 242， 345

如图所示：

3.实现代码：

package cn.hz.demo2;

import java.util.ArrayList;
import java.util.List;

/**
 * @author hz
 * @version 1.0
 *
 * 基数排序
 * 需求分析：
 * 将所有的数的个位数取出，按照个位数进行排序，构成一个序列。
 * 将新构成的所有的数的十位数取出，按照十位数进行排序，构成一个序列。
 */
public class Demo10 {
    public static void main(String[] args) {
        int[] array={49,38,65,97,76,13,27,49,78,34,12,64,1,8};
        System.out.println("基数排序之前：");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+" ");
        }
        //基数排序
        //首先确定排序的趟数;
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }
        int time = 0;
        //判断位数;
        while (max > 0) {
            max /= 10;
            time++;
        }
        //建立10个队列;
        List<ArrayList> queue = new ArrayList<ArrayList>();
        for (int i = 0; i < 10; i++) {
            ArrayList<Integer> queue1 = new ArrayList<Integer>();
            queue.add(queue1);
        }
        //进行time次分配和收集;
        for (int i = 0; i < time; i++) {
            //分配数组元素;
            for (int j = 0; j < array.length; j++) {
                //得到数字的第time+1位数;
                int x = array[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
                ArrayList<Integer> queue2 = queue.get(x);
                queue2.add(array[j]);
                queue.set(x, queue2);
            }
            int count = 0;//元素计数器;
            //收集队列元素;
            for (int k = 0; k < 10; k++) {
                while (queue.get(k).size() > 0) {
                    ArrayList<Integer> queue3 = queue.get(k);
                    array[count] = queue3.get(0);
                    queue3.remove(0);
                    count++;
                }
            }
        }

        System.out.println("\n基数排序之后：");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+" ");
        }


    }
}

复制代码

实现效果：

在这里插入图片描述

4.分析：

基数排序是稳定的排序算法。

基数排序的时间复杂度为O(d(n+r)),d为位数，r为基数。

5.稳定性总结：

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。

有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序结果就是高优先级高的在前，高优先级相同的情况下低优先级高的在前。

基数排序基于分别排序，分别收集，所以其是稳定的排序算法。

总结:

1.稳定性：

稳定：冒泡排序、插入排序、归并排序和基数排序
不稳定：选择排序、快速排序、希尔排序、堆排序

2.平均时间复杂度：

O(n^2):直接插入排序，简单选择排序，冒泡排序。

在数据规模较小时（9W内），直接插入排序，简单选择排序差不多。当数据较大时，冒泡排序算法的时间代价最高。性能为O(n^2)的算法基本上是相邻元素进行比较，基本上都是稳定的。

O(nlogn):快速排序，归并排序，希尔排序，堆排序。

其中，快排是最好的，其次是归并和希尔，堆排序在数据量很大时效果明显。

3.排序算法的选择：

规模较小：

待排序列基本序的情况下，可以选择直接插入排序；
对稳定性不作要求宜用简单选择排序，对稳定性有要求宜用插入或冒泡

数据规模不是很大：

完全可以用内存空间，序列杂乱无序，对稳定性没有要求，快速排序，此时要付出log（N）的额外空间。
序列本身可能有序，对稳定性有要求，空间允许下，宜用归并排序

数据规模很大：

对稳定性有求，则可考虑归并排序。
对稳定性没要求，宜用堆排序

序列初始基本有序（正序），宜用直接插入，冒泡。

文章版权归作者所有，未经允许请勿转载。

THE END

后端

如何一台机器同时使用多个git秘钥

那些年，我们一起做过的 Java 课后练习题（56 – 60）

DSM Light Explorer.EXE目录遍历漏洞

new Integer和Integer.valueOf的区别 – 从源码解析

W Website Baker CMS 用户显示名称 跨站脚本攻击(XSS)漏洞

Hitachi JP1/Cm2/Network Node Manager多个未明拒绝服务漏洞

JAVA九种排序算法详解

JAVA九种排序算法详解

一、排序：

1.排序的定义：

2.排序的方式：

二、直接插入排序

1.基本思想：

2.实现过程：

3.实现代码:

4.分析：

5.稳定性总结：

三、二分法插入排序

1.基本思想:

2.实现过程：

3.实现代码：

4.分析：

5.稳定性总结：

四、希尔排序

1.基本思想：

2.实现过程：

3.实现代码：

4.分析

5.稳定性总结：

五、简单选择排序：

1.基本思想：

2.实现过程：

3.实现代码：

4.分析：

5.稳定性总结：

六、堆排序：

1.基本思想：

2.实现过程：

3.实现代码：

4.分析：

5.稳定性总结：

七、冒泡排序：

1.基本思想：

2.实现过程：

3.实现代码：

4.分析：

5.稳定性总结：

八、快速排序：

1.基本思想：

2.实现过程：

3.实现代码：

4.分析：

5.稳定性总结：

九、归并排序：

1.基本思想：

2.实现过程：

3.实现代码：

4.分析：

5.稳定性总结：

十、基数排序：

1.基本思想：

2.实现过程：

3.实现代码：

4.分析：

5.稳定性总结：

总结:

1.稳定性：

2.平均时间复杂度：

3.排序算法的选择：

W Website Baker CMS 用户显示名称跨站脚本攻击(XSS)漏洞