常见的排序算法（1）

✨前言✨

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

文章目录

🌍排序的相关概念：

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

🌎插入排序

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

publicclassTestSort{publicstaticvoidmain(String[] args){int[] array ={12,23,43,52,24,64,78,0,1,4};InsertSort(array);System.out.println(Arrays.toString(array));}/**
     *时间复杂度：O(N^2) 最好情况下O(N)
     * 空间复杂度：O(1)
     * 稳定性：稳定
     * @param array 待排序数组
     */publicstaticvoidInsertSort(int[] array){for(int i =1; i <array.length ; i++){//取出当前要进行比较的数据int tmp = array[i];//需要从i与前面的数据比较，就从最近的i-1开始int j = i-1;//j要大于等于零for(;j>=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)是在数据有序的情况下，所以对于插入排序而言，数据越有序就越快！

🌏 希尔排序

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

publicclassTestSort{publicstaticvoidmain(String[] args){int[] array ={12,23,43,52,24,64,78,0,1,4};ShellSort(array);System.out.println(Arrays.toString(array));}//交换元素位置publicstaticvoidSwap(int[] array,int i,int j){int tmp = array[i];
        array[i]=array[j];
        array[j]=tmp;}/**
     * 时间复杂度：0(N^1.3)~O(N^1.5)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array 待排序序列
     */publicstaticvoidShellSort(int[] array){int gap = array.length;while(gap!=1){Shell(array,gap);
            gap=gap/2;}Shell(array,1);}//插入排序publicstaticvoidShell(int[] array,int gap){for(int i=gap;i<array.length;i++){int tmp = array[i];int j = i-gap;for(;j>=0;j-=gap){if(array[j]>tmp){
                    array[j+gap]=array[j];}else{break;}}
            array[j+gap]=tmp;}}}

🌳 选择排序

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

publicclassTestSort{publicstaticvoidmain(String[] args){int[] array ={12,23,43,52,24,64,78,0,1,4};selection(array);System.out.println(Arrays.toString(array));}//交换元素位置publicstaticvoidSwap(int[] array,int i,int j){int tmp = array[i];
        array[i]=array[j];
        array[j]=tmp;}/**
     * 时间复杂度：O(N^2)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array 待排序数组
     */publicstaticvoidselection(int[] array){for(int i =0;i<array.length;i++){int minIndex = i;//假设最小值下标一开始是ifor(int j = i+1;j<array.length;j++){if(array[minIndex]>array[j]){
                    minIndex=j;//找到最小值小标}}//如果不是i所在位置元素是最小，那么就要交换元素if(minIndex!=i){Swap(array,i,minIndex);}}}}

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

🍀 堆排序

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

publicclassTestSort{publicstaticvoidmain(String[] args){int[] array ={12,23,43,52,24,64,78,0,1,4};HeapSort(array);System.out.println(Arrays.toString(array));}//交换元素位置publicstaticvoidSwap(int[] array,int i,int j){int tmp = array[i];
        array[i]=array[j];
        array[j]=tmp;}/**
     * 时间复杂度：O(N*logN)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array 待排序数组
     */publicstaticvoidHeapSort(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);}}publicstaticvoidshiftDown(int[] array,int parent,int len){int child =2*parent+1;while(child<len){//找到左右节点的最大值if(child+1<len&&array[child]<array[child+1]){
                child++;}if(array[child]>array[parent]){Swap(array,parent,child);
                parent=child;
                child=2*parent+1;}else{break;}}}}

堆的详解

🌱 冒泡排序

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

源码地址