选择排序+冒泡排序+直接插入排序

朱雀 2021-01-24 18:20 841阅读 0赞

马上要秋招了，赶紧复习一下算法，这三种排序属于很基础的，记得大一刚学c语言的时候，经常接触的
先上代码

package com.example.eurekaribbonclient.test;
    
    import java.util.Arrays;
    
    /**
     * @ClassName test_4
     * @Description TODO
     * @Author Mr.G
     * @Date 2018/9/20 13:43
     * @Version 1.0
     */
    public class test_4 {
        public static void main(String[] args){
    
            int[] arry_1={3,4,2,1};
            int[] arry_2={3,4,2,1};
            int[] arry_3={3,4,2,1};
            selctorSort(arry_1);
            bubbleSort(arry_2);
            insertSort(arry_3);
            System.out.println(Arrays.toString(arry_1));
            System.out.println(Arrays.toString(arry_2));
            System.out.println(Arrays.toString(arry_3));
        }
        public static void swap(int[] arry,int a,int b){//交换数组的两个元素
            arry[a]=arry[a]+arry[b];
            arry[b]=arry[a]-arry[b];
            arry[a]=arry[a]-arry[b];
        }
        public static void selctorSort(int[] arry){//选择排序
            for(int i=0;i<arry.length-1;i++){//长度之所以是数组长度减1，是因为最后剩下的那个元素不用比较
                int min=i;
                for(int j=i+1;j<arry.length;j++){
                    if(arry[min]>arry[j]){
                        min=j;
                    }
                }
                if(min!=i) {
                    swap(arry, i, min);
                }
            }
        }
        public static void bubbleSort(int[] arry){//冒泡排序
            for(int i=0;i<arry.length-1;i++){//同样的道理，剩下两个元素的时候，只需要比较一次就可以得到结果
                for(int j=0;j<arry.length-1-i;j++){//后面的i个元素是已经排好顺序的
                    if(arry[j]>arry[j+1]){
                        swap(arry,j,j+1);
                    }
                }
            }
        }
        public static void insertSort(int[] arry){//插入排序
            for(int i=1;i<arry.length;i++){//因为就算剩下了一个元素，还要和前面的比，所以这个没有-1
                for(int j=i;j>0&&arry[j]<arry[j-1];j--){//比较完第一次后，向前冒泡，通过冒泡实现插入
                    swap(arry,j,j-1);
                }
            }
    
        }
    }

结果

![70][]

然后是分析

**选择排序**

从数组的的第一个元素，分别与剩余元素比较，每次比较后保存最小元素的下标，然后与第一个元素交换，接着是第二个元素，比较结果和第二个元素交换。直到倒数第二个元素，因为最后一个元素不用比了，一定是最大的，最好情况，是有序数列，不需要换，当是倒序数列时，交换次数是n-1但是比较次数时n+(n-1)+(n-2)+...1结果时（n\*(n+1)）/2，所以时间复杂度时o(n^2)，是一种不稳定排序

**冒泡排序**

总共n-1轮，每次从第一个开始，相邻的比较，较大的向后沉，但是每一轮都比上一轮少比较一次，因为最后的部分已经确定，是前面i轮的结果，最好的情况，不需要交换，最差的情况，交换次数时n+(n-1)+(n-2)+...1结果时（n\*(n+1)）/2，所以时间复杂度时o(n^2)，是一种不稳定排序

**直接插入排序**

数组第一个元素作为，待插入的有序数列，从第二个元素开始，向有序数列中比较插入，而插入的功能有冒泡代替，时间复杂度和上面一样都是o(n^2)，但是是综合了上面两种的方法的特点（个人看法）

[70]: /images/1611512417507.png