数据结构与算法Java版——九大基本排序算法（2）

墨蓝 2022-06-12 00:20 128阅读 0赞

> 　　这次分享的主题是排序算法，排序是数据处理中经常用到的一种操作，主要目的就是为了查找，在数据大量时，不同的算法有不同的效果。
> 
> 　　排序板块是目前我的写的数据结构与算法Java版的最后一块内容，所以日后会开始学习其他的内容，有兴趣的伙伴可以继续关注我,[我的博客][Link 1]  
>

由于csdn上排版有点丑，建议到我个人博客上查看  
　　今天继续上次的内容，接下来分享到了选择排序其他一些常规排序。

## 选择排序 ##

选择排序就是借助选择进行的排序，主要思想:每趟排序在当前待排序序列中选出关键码最小的记录，添加到有序序列中。选择排序的特点是记录移动的次数较少。

直接选择排序

直接选择排序的实现思想很简单：**在无序区选择最小的放在有序区中，这里实现方法是每一趟定位在无序区第一个数据，将后面数据与其比较，如果后面数据小则交换两个的位置，直到全部比较完。（第一趟5和4交换，之后4再与1交换……）**

代码如下：

public void selectSort(int[] a){
            //执行n-1躺即可，最后一个数自动排好
            for(int i=0;i<a.length-1;i++)
            {
                //j一定要等于i+1，才能确保每趟第i个数和从i+1开始的无序区中选中的最小数比较
                for(int j=i+1;j<a.length;j++)
                {
                    //如果第i个数比第j个数大则交换
                    if(a[i]>a[j]){
                        int cos=a[i];
                        a[i]=a[j];
                        a[j]=cos;
                    }
                }
            }
        }

容易看出，直接选择排序移动次数少，其算法时间复杂度为O(n^2)。直接选择排序用了一个辅助空间，其作用是保存数据并交换。

直接选择排序是一种不稳定算法。

堆排序

堆排序是直接选择排序的一种改进，而实现堆排序最重要的是如何调整堆（堆是具有下列性质的完全二叉树，每个节点的值都小于或等于其左右孩子节点的值（小根堆），或每个节点的值都大于或等于其左右孩子节点的值（大根堆）），以下以大根堆为例进行讲解：

由于堆是完全二叉树，所以用数组进行存储，如下图所示（一个大根堆结构的例子）：

![这里写图片描述][80855870.jpg]

（1）调整堆：如下图所示，将根节点与左右孩子比较，如果左右孩子中较大者大于根节点，则交换两者位置（28与35交换），经过了调整，会破坏左子树的堆结构，于是对左子树继续进行调整，重复上述操作将28与32调换。直到不需要再调整，即整个树处于堆结构。同理，右子树不为堆结构时也是如此调整。

![这里写图片描述][86566456.jpg]

调整堆的代码如下：

/**
         * @param a 待需排序的数组
         * @param k 当前筛选的节点
         * @param m 堆中最后一个节点下标
         */
        public void modifyHeap(int[] a,int k,int m){
            // i为筛选节点，j为i的左孩子
            int i = k, j = 2 * i + 1;
            // 筛选的不是叶子结点便循环下去
            while (j <= m) {
                // 如果筛选节点的左孩子小于右孩子，则j指向右孩子下标;
                if (j < m && a[j] < a[j + 1]) {
                    j++;
                }
                // 筛选节点大于其左右孩子则结束
                if (a[i] > a[j]) {
                    break;
                } else {
                    // 交换筛选节点与叶子节点位置
                    int cos = a[i];
                    a[i] = a[j];
                    a[j] = cos;
                    //继续循环调整直到i为叶子节点
                    i = j;
                    j = 2 * i + 1;
                }
            }
        }

（2）堆排序的实现：

1、先将已知的数组进行堆调整。（此处从(n-1)/2开始，因为(n-1)/2是从下往上的第一个非叶子节点,如下图数值为25的节点）

2、将数组第一位与最后一位交换位置，再重新调整堆。

3、不断重复第二步直到排序完成。（如下图所示）

![这里写图片描述][78047401.jpg]

交换第一个和最后一个节点，再在树中除去了最大元素47，便变成下图所示：

![这里写图片描述][31588065.jpg]

交换元素后破坏了堆结构，因此开始重新建堆。建好后如下图：

![这里写图片描述][27154599.jpg]

堆建好后再次交换最后一位与第一位位置，再在树中除去了此时最大元素35，便变成下图：

![这里写图片描述][1142977.jpg]

不断重复上面的图的操作，直到堆排序完成。实现上述操作代码如下：

// 堆排序
        public void heapSort(int[] a ) {
            int n=a.length; //a的数组长度
            //建立大根堆，从i=(n-1)/2的位置开始处理
            for(int i=(n-1)/2;i>=0;i--){
                modifyHeap(a, i, n-1);
            }
            //运行了n-1趟
            for(int i=1;i<n;i++){
                //交换最后一个数与第一个数的位置
                int cos=a[0];
                a[0]=a[n-i];
                a[n-i]=cos;
                //再次调整堆
                modifyHeap(a, 0, n-i-1);
            }
        }

对于堆排序而言，如果有n个数据就需要进行n-1次建堆，堆排序时间效率为O（nlog2 n），堆排序只需要一个记录的辅助空间，并且堆排序是不稳定的。

归并排序

**归并基本思想是将两个（或以上）有序的序列合并成一个新的有序序列。**

![这里写图片描述][40617204.jpg]

如：设有数列\{6，202，100，301，38，8，1\}

*  初始状态：6,202,100,301,38,8，1
 *  第一次归并后：\{6,202\},\{100,301\},\{8,38\},\{1\}；
 *  第二次归并后：\{6,100,202,301\}，\{1,8,38\}；
 *  第三次归并后：\{1,6,8,38,100,202,301\}。
    
    　　此处最重要的是如何合并，合并算法如下：

**1. 定义两个变量i,i从0开始，依次等于A序列中每个元素索引。**  
**2. 定义两个变量j,j从0开始，依次等于B序列中每个元素索引。**  
**3. 将A序列中i处元素与B序列j处元素进行比较，将较小的元素复制到一个临时数组中。**  
**4. 如果i索引处的元素小，i++;如果j索引处的元素小，j++;**  
**5. 重复上述1、2、3、4，直到A或B中所有数据复制到临时数组中，再将另一个数组中多的元素全部复制到临时数组，最后再将临时数组中所有数据复制回原来的数组。**

合并代码如下：

/**
             * @param a 待排序数组
             * @param left 左数组的第一个数下标
             * @param center 左数组的最后一个数下标
             * @param right 右数组的最后一个数下标
             */
            private void merge(int [] a,int left,int center,int right){
                int[] temp=new int[a.length];   //临时数组
                int mid= center+1;
                //中间数组的索引
                int i=left; 
                int j=left; 
                //一直进行到其中一方所有数据全部复制到临时数组
                while(left<=center&&mid<=right){
                    //比较两组数据，根据大小确定将谁复制
                    if(a[left]<=a[mid]){
                        temp[i]=a[left];
                        i++;
                        left++;
                    }
                    else{
                        temp[i]=a[mid];
                        i++;
                        mid++;
                    }
                }
                //将剩余部分加入到数组中
                while(left<=center){
                    temp[i]=a[left];
                    i++;
                    left++;
                }
                while(mid<=right){
                    temp[i]=a[mid];
                    i++;
                    mid++;
                }
                //将临时数组中数据复制回原来的数组
                while(j<=right){
                    a[j]=temp[j];
                    j++;
                }
            }

上述合并算法完成后，接下来只需将待排序数组分两半进行递归合并，代码如下：

public void mergeSort(int [] a){
            sort(a, 0, a.length-1);
        }
    
        /**
         * @param a 待排序数组
         * @param first 数组第一个数下标
         * @param end 数组最后一个数下标
         */
        private void sort(int [] a,int first,int end){
            if(first<end){
                //找出中间索引
                int middle=(first+end)/2;
                //对左边数组进行递归
                sort(a, first, middle);
                //对右边数组进行递归
                sort(a, middle+1, end);
                //合并
                merge(a, first, middle, end);
            }
        }

从上面代码可以看出，归并排序需要先分解，再合并。 归并排序算法复杂度为O(nlog2 n)。归并排序算法空间效率较差，因为它需要一个与原数组相同大小的数组，但归并排序是稳定的。

桶式排序

桶式排序是一种很神奇排序方式，下面以\{3，6，1，5，7，6\}为例进行分析（看完你就知道神奇在哪了）

这个数组处于1~7这个范围内，范围很小，用桶式排序正好，具体步骤如下：

1、对于这个范围构建一个buckets数组，用于记录落入每个桶中的元素的个数，如下所示：

数组范围     1       2       3       4       5       6       7 
    buckets数组  1       0       1       0       1       2       1  
    数组下标     0       1       2       3       4       5       6

2、对于上图的buckets数组中的元素按公式buckets\[i\]=buckets\[i\]+buckets\[i-1\]重新计算。得到如下所示数组（由下表可知，排序6时，在下表中找到数组范围一行找到6的位置，其新buckets中对应5，即应该排第五位，同理：7对应的新6buckets中的6，所以7应该在第6位……） 。

数组范围        1       2       3       4       5       6       7  
     新buckets数组   1       1       2       2       3       5       6  
     数组下标        0       1       2       3       4       5       6

3、最后根据得到的新的buckets数组的信息将原数组排序好。

/**
             * 桶式排序
             * @param a待排序数组
             * @param min数组中最小的数
             * @param max数组中最大的数
             */
            public void bucketSort(int [] a,int min,int max){
                //buckets数组相当于定义了max-min+1个桶，即数组的容量就是桶几个
                int [] buckets=new int[max-min+1];
                //记录每个数出现的次数
                for(int i=0;i<a.length;i++){
                    //在指定的位置记录元素出现的个数
                    buckets[a[i]-min]++;
                }
                //将buckets换成新的buckets
                for(int i=1;i<max-min+1;i++){
                    buckets[i]=buckets[i]+buckets[i-1];
                }
                //定义一个临时数组将a数组缓存下来
                int[] tmp=new int[a.length];
                System.arraycopy(a, 0, tmp, 0, a.length);
                //根据新的buckets的信息将数据按放回相应位置，即排序 
                for(int k=a.length-1;k>=0;k--){
                    /* 
                    tmp[k]-min得到的是tmp[k]在buckets数组中的下标
                    --buckets[tmp[k]-min]中的--是因为要将得到的
                    buckets[tmp[k]-min]，即某数排在第几位转化为数组下标
                    所以减一即可。
                    */
                    a[--buckets[tmp[k]-min]]=tmp[k];
                }
            }

桶式排序是一种非常优秀的算法，时间效率高。但是其空间开销大，它需要buckets数组记录落入各桶中元素的个数，第二个临时数组缓存待排序数据。

基数排序

基数排序需要依赖其他排序实现，所以并不是一种常规的排序方法。其基本思想：将待排序数据拆分成多个关键字进行排序，也就是说，基数排序的实质是多关键字排序。

接下来以\{230，129，45，12\}进行分析：

如果以我们人的习惯思维一定是先比较百位，如果百位相同再比较十位，如果十位相同则比较个位，这是最高位优先方式（MSD）。但是如果将这种方式应用到电脑会有许多不便，电脑的处理方式通常是最低位优先方式（LSD）。

第一轮以个位为关键字进行排序：\{230，12，45，129\}

第二轮以十位为关键字进行排序：\{12，129，230，45\}

第三轮以百位为关键字进行排序：\{12，45，129，230\}

基数排序利用的其他排序技术必须是稳定，如果用到的排序技术不稳定可能会出现数据乱位。 那么用哪一个排序技术比较好？这里用的是桶式排序，因为每个关键码都在0~9之间，范围不大，很适合桶式排序。

代码实现如下：

/**
         * @param a待排序数组
         * @param radix 指定关键字拆分进制
         * @param d 子关键字数目
         */
        public void radixSort(int [] a ,int radix,int d){
            System.out.println("开始排序:");
            int length=a.length;
            //创建临时数组
            int[] tmp=new int[length];
            //创建buckets数组即创建了其长度数量的桶
            int[] buckets=new int[radix];
            //rate为保存当前计算的位，1为个位，10为十位......
            for(int i=0,rate=1;i<d;i++){
                //重置buckets数组
                Arrays.fill(buckets, 0);
                //将data数组的元素复制到临时数组中
                System.arraycopy(a, 0, tmp, 0, length);
                for(int j=0;j<length;j++){
                    //计算数据指定位上的子关键字，比如第一轮129的subKey为9
                    int subKey=(tmp[j]/rate)%radix;
                    //记录subKey出现的次数
                    buckets[subKey]++;
                }
                //按桶式公式将buckets换成新的buckets
                for(int j=1;j<radix;j++){
                    buckets[j]=buckets[j]+buckets[j-1];
                }
                //按子关键字对指定数据进行排序
                for(int m=length-1;m>=0;m--){
                    int subKey=(tmp[m]/rate)%radix;
                    a[--buckets[subKey]]=tmp[m];
                }
                System.out.println("按"+rate+"位上子关键字进行排序："+Arrays.toString(a) );
                rate *=radix;
            }
        }

其实仔细阅读以上代码，会发现就是几轮桶式排序罢了，有几个子关键字就进行了几轮桶式排序，当然基数排序也可以用其他稳定的排序算法实现，这里就不介绍了。

以上就介绍完了九大基本排序，有些地方可能个人解释的不大仔细，小伙伴也可以查查其他资料，相信一定可以搞定这九大排序。如果有任何错误的地方，欢迎指出。今天分享就到这里了，下次见。

[Link 1]: http://xichangblog.com
[80855870.jpg]: http://or0um8wrx.bkt.clouddn.com/17-7-7/80855870.jpg
[86566456.jpg]: http://or0um8wrx.bkt.clouddn.com/17-7-7/86566456.jpg
[78047401.jpg]: http://or0um8wrx.bkt.clouddn.com/17-7-7/78047401.jpg
[31588065.jpg]: http://or0um8wrx.bkt.clouddn.com/17-7-7/31588065.jpg
[27154599.jpg]: http://or0um8wrx.bkt.clouddn.com/17-7-7/27154599.jpg
[1142977.jpg]: http://or0um8wrx.bkt.clouddn.com/17-7-7/1142977.jpg
[40617204.jpg]: http://or0um8wrx.bkt.clouddn.com/17-7-10/40617204.jpg