[排序算法] 常见的排序算法

雨点打透心脏的1/2处 2023-09-29 14:29 272阅读 0赞

####  ####

*  前言
 *  1.冒泡排序
 *  2.选择排序
 *  3.插入排序
 *  4希尔排序
 *  5.归并排序
 *  6.快速排序

## 前言 ##

在实际需求中，我们可能要对商品的物价等按照价格高低来进行排序，这个时候，我们就得需要学会几种常见的排序算法，来满足我们的开发需求  
推荐一个网站，可以对数据结构等进行动画演示 [https://visualgo.net/zh][https_visualgo.net_zh]  
![在这里插入图片描述][d1f083dd7aa441a0ba8ca991c965c0b0.png]

## 1.冒泡排序 ##

>  排序原理:  
> ①比较相邻的元素，如果前一个元素比后一个元素大，就交换这个两个元素的位置  
> ②对每一对相邻的元素做同样的操作，从开始的第一对元素到结尾的最后一对元素 ③每一次排序过后，都会把当前排序元素的最大值找出来 
> 
> 以3，6，4，2，11，10，5排序为例![在这里插入图片描述][c7b35576d3ec43b2b752709450870af5.png]  
> 代码示例  
> 因为涉及到元素的交换，所以我们可以先一个方法swap专门用来交换数组中的元素,在后面的排序中都会用到，后面 的排序就不把这个方法展示出来了  
> ![在这里插入图片描述][f447f10bc21d49358764c78fa5ca76a7.png]  
> ![在这里插入图片描述][7753c63ec0bb41ac8ba1bb61c7b88c38.png]  
> ![在这里插入图片描述][1082974ec2c14cdeb4bd7139f294e84a.png]  
> 接下来进行测试  
> ![在这里插入图片描述][4f74cc908ca845a38275fbc9a820e1f7.png]

## 2.选择排序 ##

>  排序原理:  
> ①.每一次遍历的过程中，都假定第一个索引处的元素是最小值，和其他索引处的值依次进行比较，如果当前索引处的值大于其他某个索引处的值，则假定其他某个索引出的值为最小值，最后可以找到最小值所在的索引  
> ②.交换第一个索引处和最小值所在的索引处的值 
> 
> ![在这里插入图片描述][c991b747347f4f388135ae4c0dfb1e3e.png]  
> ![在这里插入图片描述][ed7bef3a197b47e58c03379db9d0c4ad.png]  
> 测试  
> ![在这里插入图片描述][ecff5b23fa224e1dbea8a4c034842192.png]

## 3.插入排序 ##

> 排序原理:  
> 1.把所有的元素分为两组，已经排序的和未排序的；  
>   
> 2.找到未排序的组中的第一个元素，向已经排序的组中进行插入；  
>   
> 3.倒叙遍历已经排序的元素，依次和待插入的元素进行比较，直到找到一个元素小于等于待插入元素，那么就把待 插入元素放到这个位置，其他的元素向后移动一位；  
> ![在这里插入图片描述][5b28d3955ea74051afedebdff76bd3a8.png]  
> ![在这里插入图片描述][1ef21791065448fd8c24ca5bd62aef50.png]  
> 测试  
> ![在这里插入图片描述][597976e509f34a869f4c09bd5309db32.png]

## 4希尔排序 ##

希尔排序是插入排序的一种，又称“缩小增量排序”，是插入排序算法的一种更高效的改进版本。

> 排序原理  
> ①.选定一个增长量d，按照增长量d作为数据分组的依据，对数据进行分组；  
> ②.对分好组的每一组数据完成插入排序；  
> ③.减小增长量，最小减为1，重复第二步操作。  
> ![这里是引用][4d84972750f749eb840de9af9576710a.png]  
> 那么刚开始d的取值要怎么取呢  
> ![在这里插入图片描述][cc339900675f4727a6a41282a05d089a.png]

public static void sort(int[] arr) {
        
            //根据数组的长度来确定增长量的初始值
            int d = 1;
            while (d < arr.length/2) {
        
                d = d * 2 + 1;
            }
            while (d >= 1) {
        
                //排序
                /**
                 * 找到待插入的元素
                 * 我们可以发现，第一个待插入的元素的索引是h的值
                 * 然后把待插入元素插入到有序数组中
                 */
                for (int i = d; i < arr.length; i++) {
        
                    //待插入元素的初始索引为h
                    for (int j = i; j >= d; j -= d) {
        
                        if (arr[j-d]>arr[j]) {
        
                            swap(arr, j - d, j);
                        } else {
        
                            //待插入元素已经找到合适的位置了
                            break;
                        }
                    }
    
                }
                int i = 1;
                System.out.println("第" + (i++) + "轮排序结果:" + Arrays.toString(arr));
                //更改h的值
                d = d >> 1;
    
            }
    
        }

测试  
![在这里插入图片描述][b26ec85126554976b4d9c630290dfb38.png]

## 5.归并排序 ##

> 归并排序是分治法的典型英语，把有序的子序列合并，得到完全有序的序列，就是说先让每一个子序列有序，再让子序列段间有序  
>   
> 排序原理：  
> ①尽可能的一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数是  
> 1为止。  
> ②将相邻的两个子组进行合并成一个有序的大组；  
> ③不断的重复步骤2，直到最终只有一个组为止  
> ![在这里插入图片描述][63567da16430435d84f5f7e933b69e28.png]  
> 归并原理  
> ![在这里插入图片描述][d50099b47ccd4055b2270afc27fd45f1.png]  
> ![在这里插入图片描述][deb09b3d574845369b94ea12723d4ae4.png]  
> ![在这里插入图片描述][5a1e46bd86cf4ce8991b544e6e147dbb.png]  
> ![在这里插入图片描述][454aad05b3114e2dbd38cc0b609ba74a.png]  
> ![在这里插入图片描述][da49aaced3244fa88b5b39b5f44ccb2b.png]  
> 注:Comparable接口是为了通用性，这个是Java语法，大家把这个改成对应的数据类型也可以

/**
     * @author zengyihong
     * @create 2022--05--10 8:25
     */
    public class Merge {
        
        //归并所需要的辅助数组
        private static Comparable[] assist;
    
        /*
           比较v元素是否小于w元素
        */
        private static boolean less(Comparable v, Comparable w) {
        
            return v.compareTo(w)<0;
        }
    
        /*
        数组元素i和j交换位置
         */
        private static void exch(Comparable[] a, int i, int j) {
        
            Comparable t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    
    
        /*
               对数组a中的元素进行排序
            */
        public static void sort(Comparable[] a) {
        
            //1.初始化辅助数组assist；
            assist = new Comparable[a.length];
            //2.定义一个lo变量，和hi变量，分别记录数组中最小的索引和最大的索引；
            int lo=0;
            int hi=a.length-1;
            //3.调用sort重载方法完成数组a中，从索引lo到索引hi的元素的排序
            sort(a,lo,hi);
        }
    
        /*
        对数组a中从lo到hi的元素进行排序
         */
        private static void sort(Comparable[] a, int lo, int hi) {
        
            //做安全性校验；
            if (hi<=lo){
        
                return;
            }
    
            //对lo到hi之间的数据进行分为两个组
            int mid = lo+(hi-lo)/2;//   5,9  mid=7
    
            //分别对每一组数据进行排序
            sort(a,lo,mid);
            sort(a,mid+1,hi);
    
            //再把两个组中的数据进行归并
            merge(a,lo,mid,hi);
        }
    
        /*
        对数组中，从lo到mid为一组，从mid+1到hi为一组，对这两组数据进行归并
         */
        private static void merge(Comparable[] a, int lo, int mid, int hi) {
        
            //定义三个指针
            int i=lo;
            int p1=lo;
            int p2=mid+1;
    
            //遍历，移动p1指针和p2指针，比较对应索引处的值，找出小的那个，放到辅助数组的对应索引处
            while(p1<=mid && p2<=hi){
        
                //比较对应索引处的值
                if (less(a[p1],a[p2])){
        
                    assist[i++] = a[p1++];
                }else{
        
                    assist[i++]=a[p2++];
                }
            }
    
            //遍历，如果p1的指针没有走完，那么顺序移动p1指针，把对应的元素放到辅助数组的对应索引处
            while(p1<=mid){
        
                assist[i++]=a[p1++];
            }
            //遍历，如果p2的指针没有走完，那么顺序移动p2指针，把对应的元素放到辅助数组的对应索引处
            while(p2<=hi){
        
                assist[i++]=a[p2++];
            }
            //把辅助数组中的元素拷贝到原数组中
            for(int index=lo;index<=hi;index++){
        
                a[index]=assist[index];
            }
    
        }
    
    
    
    }

## 6.快速排序 ##

> 快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一  
> 部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序  
> 过程可以递归进行，以此达到整个数据变成有序序列  
>   
> 排序原理:  
> 1.首先设定一个分界值，通过该分界值将数组分成左右两部分；  
> 2.将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于  
> 或等于分界值，而右边部分中各元素都大于或等于分界值；  
> 3.然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两  
> 部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。  
> 4.重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当  
> 左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了。  
> ![在这里插入图片描述][e4dd4b54c2254edaa7639816a633e702.png]  
> 切分原理：  
> 把一个数组切分成两个子数组的基本思想：  
> 1.找一个基准值，用两个指针分别指向数组的头部和尾部；  
> 2.先从尾部向头部开始搜索一个比基准值小的元素，搜索到即停止，并记录指针的位置；  
> 3.再从头部向尾部开始搜索一个比基准值大的元素，搜索到即停止，并记录指针的位置；  
> 4.交换当前左边指针位置和右边指针位置的元素；  
> 5.重复2,3,4步骤，直到左边指针的值大于右边指针的值停止。  
> ![在这里插入图片描述][7e41cb6d11494acda0fafd96dce4d11f.png]  
> ![在这里插入图片描述][0f128e0f764740c0ab7781275b50c14e.png]  
> ![在这里插入图片描述][916b3980057b46c59942a022572404cf.png]  
> ![在这里插入图片描述][26f4e466b59640ac99645057f00008dd.png]

public static void sort(int[] arr, int left, int right) {
        
    
            //如果左边的索引比右边的索引大，则不合法
            if (left > right) {
        
                return;
            }
            //定义变量保存基准数
            int base = arr[left];
            //定义变量i,指向最左边
            int i = left;
            //定义变量j，指向最右边
            int j = right;
            //当i和j不相遇的时候，在循环中进行检索
            while (i != j) {
        
                //先由j从右边往左检索，如果检索到比基准数小的就停下
                //如果检索到比基准数大或相等就继续检索
                while (arr[j] >= base && j>i) {
        
                    j--;
                }
                //i从左边往右边检索
                while (arr[i] <= base && j>i) {
        
                    i++;
                }
                //代码走到这里，说明i和j都停下了，则交换i和j位置的元素
    
                    swap(arr,i,j);
    
    
            }
            //如果条件不成立，就会跳出循环，说明i和j相遇了
            //i和j一旦相遇，就停止检索，把基准数和相遇位置的元素交换
              arr[left]=arr[i];
             arr[i]=base;
            //此时，基准数的左边都比它小，右边都比它大
            //接下来继续相同的操作，可以使用递归
            //排基准数的左边
            sort(arr,left,i-1);
            //排基准数的右边
            sort(arr,i+1,right);
    
    
    
        }

代码测试  
![在这里插入图片描述][ce003e6216a146ff80b640061282c68f.png]

[https_visualgo.net_zh]: https://visualgo.net/zh
[d1f083dd7aa441a0ba8ca991c965c0b0.png]: https://img-blog.csdnimg.cn/d1f083dd7aa441a0ba8ca991c965c0b0.png
[c7b35576d3ec43b2b752709450870af5.png]: https://img-blog.csdnimg.cn/c7b35576d3ec43b2b752709450870af5.png
[f447f10bc21d49358764c78fa5ca76a7.png]: https://img-blog.csdnimg.cn/f447f10bc21d49358764c78fa5ca76a7.png
[7753c63ec0bb41ac8ba1bb61c7b88c38.png]: https://img-blog.csdnimg.cn/7753c63ec0bb41ac8ba1bb61c7b88c38.png
[1082974ec2c14cdeb4bd7139f294e84a.png]: https://img-blog.csdnimg.cn/1082974ec2c14cdeb4bd7139f294e84a.png
[4f74cc908ca845a38275fbc9a820e1f7.png]: https://img-blog.csdnimg.cn/4f74cc908ca845a38275fbc9a820e1f7.png
[c991b747347f4f388135ae4c0dfb1e3e.png]: https://img-blog.csdnimg.cn/c991b747347f4f388135ae4c0dfb1e3e.png
[ed7bef3a197b47e58c03379db9d0c4ad.png]: https://img-blog.csdnimg.cn/ed7bef3a197b47e58c03379db9d0c4ad.png
[ecff5b23fa224e1dbea8a4c034842192.png]: https://img-blog.csdnimg.cn/ecff5b23fa224e1dbea8a4c034842192.png
[5b28d3955ea74051afedebdff76bd3a8.png]: https://img-blog.csdnimg.cn/5b28d3955ea74051afedebdff76bd3a8.png
[1ef21791065448fd8c24ca5bd62aef50.png]: https://img-blog.csdnimg.cn/1ef21791065448fd8c24ca5bd62aef50.png
[597976e509f34a869f4c09bd5309db32.png]: https://img-blog.csdnimg.cn/597976e509f34a869f4c09bd5309db32.png
[4d84972750f749eb840de9af9576710a.png]: https://img-blog.csdnimg.cn/4d84972750f749eb840de9af9576710a.png
[cc339900675f4727a6a41282a05d089a.png]: https://img-blog.csdnimg.cn/cc339900675f4727a6a41282a05d089a.png
[b26ec85126554976b4d9c630290dfb38.png]: https://img-blog.csdnimg.cn/b26ec85126554976b4d9c630290dfb38.png
[63567da16430435d84f5f7e933b69e28.png]: https://img-blog.csdnimg.cn/63567da16430435d84f5f7e933b69e28.png
[d50099b47ccd4055b2270afc27fd45f1.png]: https://img-blog.csdnimg.cn/d50099b47ccd4055b2270afc27fd45f1.png
[deb09b3d574845369b94ea12723d4ae4.png]: https://img-blog.csdnimg.cn/deb09b3d574845369b94ea12723d4ae4.png
[5a1e46bd86cf4ce8991b544e6e147dbb.png]: https://img-blog.csdnimg.cn/5a1e46bd86cf4ce8991b544e6e147dbb.png
[454aad05b3114e2dbd38cc0b609ba74a.png]: https://img-blog.csdnimg.cn/454aad05b3114e2dbd38cc0b609ba74a.png
[da49aaced3244fa88b5b39b5f44ccb2b.png]: https://img-blog.csdnimg.cn/da49aaced3244fa88b5b39b5f44ccb2b.png
[e4dd4b54c2254edaa7639816a633e702.png]: https://img-blog.csdnimg.cn/e4dd4b54c2254edaa7639816a633e702.png
[7e41cb6d11494acda0fafd96dce4d11f.png]: https://img-blog.csdnimg.cn/7e41cb6d11494acda0fafd96dce4d11f.png
[0f128e0f764740c0ab7781275b50c14e.png]: https://img-blog.csdnimg.cn/0f128e0f764740c0ab7781275b50c14e.png
[916b3980057b46c59942a022572404cf.png]: https://img-blog.csdnimg.cn/916b3980057b46c59942a022572404cf.png
[26f4e466b59640ac99645057f00008dd.png]: https://img-blog.csdnimg.cn/26f4e466b59640ac99645057f00008dd.png
[ce003e6216a146ff80b640061282c68f.png]: https://img-blog.csdnimg.cn/ce003e6216a146ff80b640061282c68f.png