常见的排序算法（1）

✨前言✨

 博客主页：to Keep博客主页
欢迎关注，点赞，留言评论
⏳首发时间：2022年2月27日
 博主码云地址：博主码云地址
参考书籍：java核心技术 卷1
编程练习：牛客网+力扣网
由于博主目前也是处于一个学习的状态，如有讲的不对的地方，请一定联系我予以改正！！！

排序的相关概念：插入排序 希尔排序 选择排序 堆排序 冒泡排序源码地址

1 排序：
就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
2 稳定性：
两个相等的数据，如果经过排序后，排序算法能保证其相对位置不发生变化，则我们称该算法是具备稳定性的排序算法。
例如：

插入排序的核心思想就是把数组中的第一个数据是作为有序的，从第二个数据开始，就要与前面的数据进行比较，在合适的位置进行插入；
代码如下：

public class TestSort {
    public static void main(String[] args) {
        int[] array = {12,23,43,52,24,64,78,0,1,4};
        InsertSort(array);
        System.out.println(Arrays.toString(array));
    }

    
    public static void InsertSort(int[] array){
        for (int i = 1; i =0;j--){
                //如果j位置上数据大于tmp，那么就需要将j+1上的数据覆盖成j位置上的数据
                if(array[j]>tmp){
                    array[j+1]=array[j];
                }else{
                    //说明此时数据是有序的，直接退出循环
                    break;
                }
            }
            //将tmp放在j+1位置上
            array[j+1]=tmp;
        }
    }
}

**特点:**时间复杂度为O(N)是在数据有序的情况下，所以对于插入排序而言，数据越有序就越快！

希尔排序其实就是在插入排序的基础上，进行了优化，它所利用的也是直接插入排序，但是它采用了数据分组的思想，接下来就简单的来了解一下什么是希尔排序！
代码如下：

public class TestSort {
    public static void main(String[] args) {
        int[] array = {12,23,43,52,24,64,78,0,1,4};
        ShellSort(array);
        System.out.println(Arrays.toString(array));
    }

    //交换元素位置
    public static void Swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i]=array[j];
        array[j]=tmp;
    }

    

    public static void ShellSort(int[] array){
        int gap = array.length;
        while(gap!=1){
            Shell(array,gap);
            gap=gap/2;
        }
        Shell(array,1);
    }
    //插入排序
    public static void Shell(int[] array,int gap){
        for(int i=gap;i=0;j-=gap){
                if(array[j]>tmp){
                    array[j+gap]=array[j];
                }else{
                    break;
                }
            }
            array[j+gap]=tmp;
        }
    }
}

选择排序其实就是，每一次都要将数组中，最小的元素放置到第一位
代码如下：

public class TestSort {
    public static void main(String[] args) {
        int[] array = {12,23,43,52,24,64,78,0,1,4};
        selection(array);
        System.out.println(Arrays.toString(array));
    }
    
    //交换元素位置
    public static void Swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i]=array[j];
        array[j]=tmp;
    }

    

    public static void selection(int[] array){
        for(int i = 0;iarray[j]){
                    minIndex=j;//找到最小值小标
                }
            }
            //如果不是i所在位置元素是最小，那么就要交换元素
            if(minIndex!=i){
                Swap(array,i,minIndex);
            }
        }
    }
}

对于选择排序而言，无论数组是否有序，时间复杂度都为O（N^2）!

堆排序就是就是我们之前讲过堆的调整。
代码如下：

public class TestSort {
    public static void main(String[] args) {
        int[] array = {12,23,43,52,24,64,78,0,1,4};
        HeapSort(array);
        System.out.println(Arrays.toString(array));
    }

    //交换元素位置
    public static void Swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i]=array[j];
        array[j]=tmp;
    }

    

    public static void HeapSort(int[] array){
        //调整建大堆
        for(int parent = (array.length-1-1)/2;parent>=0;parent--){
            shiftDown(array,parent,array.length);
        }
        //开始排序
        int end = array.length-1;
        while (end>0){
            //将最大的放到最后
            Swap(array,0,end);
            end--;
            //除去最大的之后，堆重新调整,对0位置调整
            shiftDown(array,0,end);
        }

    }

    public static void shiftDown(int[] array,int parent,int len){
        int child = 2*parent+1;
        while (childarray[parent]){
                Swap(array,parent,child);
                parent=child;
                child=2*parent+1;
            }else{
                break;
            }
        }
    }
}

堆的详解

冒泡排序的时间复杂度：O(N^2)
空间复杂度：O（1）
稳定性：稳定
图解冒泡排序