一、插入排序

1.原理

 将整个区间分为两个区间:1.有序区间  2.无序区间,每次将无序区间的第一个元素,在有序区间的合适位置插入.

2.代码实现

   public static void insertSort(int[] array)
       //有序区间[0,i)
       //无序区间[i,array.length)
       for(int i = 1; i < array.length;i++)
           int v = array[i];//无序区间第一个数
           int j = i-1;//有序区间最后一个下标
           for(; j >= 0 && array[j] > v;j--)
               array[j+1] = array[j];
           
           //如果不交换此时下标在i-1
           array[j+1] = v;
       
   

时间复杂度为O(N^2) ;空间复杂度为O(1)
稳定性 : 稳定排序;  如果array[j] > v换成array[j] >=  v就变成不稳地的了.
特点: 1.数组越短,速度越快
      2.数组越接近有序,速度越快

二、希尔排序

1.原理

进阶版本的插入排序,先分组,再针对每个组进行排序,逐渐缩小组的个数,最终整个数组就有序了.

2.代码实现

    public static void shellSort(int[] arr)
        int gap = arr.length / 2;//将数组分为gap组
        while (gap > 1 )
        //传入组数和数组,带组数的插入排序
            insertSortGap(arr,gap);
            gap = gap / 2;
        
        insertSortGap(arr,1);
    

    private static void insertSortGap(int[] arr, int gap) 
    //[0,i)为已排序区间;[i,arr.length)为未排序区间
        for(int i = gap ;i < arr.length;i++)
            int v = arr[i];
            int cur = i - gap;
            for( ; cur >= 0&& arr[cur]> v ;cur -= gap)
                arr[cur+gap] = arr[cur];
            
            arr[cur + gap] = v;
        
    

时间复杂度为O(N^1.3);空间复杂度为O(1)
时间复杂度最好为O(N),最坏为O(N^2);
特点:插入排序的优化版
稳定性 : 不稳定排序

三、选择排序

1.原理

基于打擂台的方式:选数组首元素为擂主,循环遍历数组剩余元素,如果发现比擂主小的元素,就交换两个数.
遍历完成后让擂主加一,重复前面的动作.

2.代码实现

    public static void selectSort(int[] arr)
        for(int bound  = 0; bound < arr.length; bound++) 
            //bound 位置元素作为擂主,循环进行比较
            //如果打擂成功就和擂主交换
            for(int cur = bound + 1 ; cur < arr.length; cur++) 
                if(arr[bound] > arr[cur])
                    int tmp = arr[bound];
                    arr[bound] = arr[cur];
                    arr[cur] = tmp ;
                
            
        
    

时间复杂度:O(N^2) ;空间复杂度:O(1);
稳定性 : 不稳定排序

四、堆排序

1.原理

 升序排列:将数组建一个大堆,然后将堆顶元素和堆底元素交换,重新生成一个大堆,并且将堆的大小减一,每一次循环
 都会让数组的最后一个元素是较大者,重复这个过程就实现了堆排序.  数组就是升序.

2.代码实现

    public static void heapSort(int[] arr)
        //第一步先将传入的数组创建成一个大堆
        createHeap(arr);
        //循环将堆顶元素与堆底元素交换,并且调整堆
        //当堆中是剩一个元素的时候也就不用循环了,所以少循环一次 -1
        for(int i = 0 ;i < arr.length -1 ;i ++)
                //交换堆顶和堆底元素
            //堆顶下标为0 ;堆底下标为arr.length - i -1
            swap(arr , 0 ,arr.length - i -1 );
            //交换完成再进行向下调整堆; 让堆的大小每次小 1
            shiftDown(arr , arr.length - i -1 , 0 );
        
    

    private static void shiftDown(int[] arr, int heapLength, int index) 
        int parent = index;
        int child = 2 * parent + 1;
        while( child < heapLength)
            //判断parent左右子树较大者
            if( child + 1 < heapLength && arr[child + 1] > arr[child])
                child = child + 1;
            
            //判断孩子是否大于,如果大于交换,否则满足大堆直接break
            if( arr[child] > arr[parent])
                swap(arr, child ,parent);
            else
                break;
            
            parent = child;
            child = 2 * parent + 1;
        
    

    private static void createHeap(int[] arr) 
        int cur  = (arr.length - 1 - 1) / 2 ;
        for( int i = cur ; i >= 0 ;i--)
            shiftDown(arr, arr.length, i);
        
    

    private static void swap(int[] arr, int i, int j) 
        int tmp =  arr[i];
        arr[i] = arr[j];
        arr[j] = tmp ;
    

时间复杂度:O(N*log(N)) ;空间复杂度:O(1);
稳定性 : 不稳定排序

五、冒泡排序

1.原理

 升序排列:将一个无序的区间相邻进行比较,较大的放在后面,循环比较,一次循环可以把最大的放在数组最后,下一次
 循环可以将较大者放到次后位置,循环N次就得到了一个升序数组.

2.代码实现

    public static  void bubbleSort(int[] arr) 
        //循环 i 次
        for(int i = 0 ; i < arr.length ;i++) 
            //每循环一次会确定一个较大值
            //注意数组下标越界bound + 1 < arr.length - i
            for(int bound = 0 ;bound + 1 < arr.length - i ;bound++)
                if(arr[bound + 1] < arr[bound])
                    int tmp = arr[bound];
                    arr[bound] = arr[bound + 1];
                    arr[bound + 1 ] = tmp;
                
            
        
    

时间复杂度:O(N^2) ;空间复杂度:O(1);
稳定性 : 稳定排序

六、快速排序

1.原理

 升序排列:1.在待排数组中选取一个数作为基准值(一般选最左侧或最右侧作为基准值;
         2.比基准值大的放在基准值的右边,比基准值小的放在基准值的左边
         3.在递归排序基准值的左边,递归基准值的右边

2.代码实现

递归版本

    public static void quickSort(int[] arr) 
        //借助helper方法进行递归
        //为了代码简单设置成前闭后闭区间[left,right]
        quickSortHelper(arr ,0 ,arr.length - 1);

    

    private static void quickSortHelper(int[] arr, int left, int right) 
        //判断数组元素有几个,如果有0个或者1个就无需排序,直接return;
        if(left >= right)
            return ;
        
        //通过partition对数组进行分区左侧为小于基准值,右侧为大于基准值
        //index 为整理后left和right重合的位置
        int index = partition(arr ,left ,right);
        quickSortHelper(arr ,left , index - 1);
        quickSortHelper(arr , index + 1,right);
    

    private static int partition(int[] arr, int left, int right) 
        int i = left ;
        int j = right ;
        int base = arr[right];  //将数组最后一个元素设为基准值
        //left < right 说明数组还没判断完
        while( i < j)
            while ( i < j && arr[i] <= base)
                i++ ;
                //循环结束后,要么i和j重回,要么i下标是一个比base值大的数
            
            while ( i < j && arr[j] >= base)
                j-- ;
                //循环结束要么j和i重合,要么j下标是一个比base小的数
            
            //交换i和j下标的元素
            swap(arr,i ,j);
        
        //循环结束要将i或j(i和j此时在同一位置)位置的元素和right(基准值)元素进行交换
        swap(arr, i , right);
        //返回基准值位置
        return  i;
    
    
    private static void swap(int[] arr, int i, int j) 
        int tmp =  arr[i];
        arr[i] = arr[j];
        arr[j] = tmp ;
    

时间复杂度:O(N*log(N)) ;空间复杂度:O(log(N))主要是因为递归;
稳定性 : 不稳定排序

非递归版本

    public static void quickSortByLoop(int[] arr) 
        //通过栈来模拟实现递归
        Stack<Integer> stack = new Stack<>();
        //将数组左右位置下标入栈
        stack.push(arr.length - 1);
        stack.push(0);
        while (!stack.empty())
            //出栈顺序和入栈顺序相反
            int left = stack.pop();
            int right = stack.pop();
            //如果左右区间之间只有一个数证明已经有序 直接进行下一次循环
            if( left >= right)
                continue ;
            
            int index = partition(arr , left ,right);
            //排序后的右区间[ index + 1 ,right]
            stack.push(right);
            stack.push(index + 1);
            //排序后的左区间[left ,index - 1]
            stack.push(index - 1);
            stack.push(left);
        
    
    
    private static int partition(int[] arr, int left, int right) 
        int i = left ;
        int j = right ;
        int base = arr[right];  //将数组最后一个元素设为基准值
        //left < right 说明数组还没判断完
        while( i < j)
            while ( i < j && arr[i] <= base)
                i++ ;
                //循环结束后,要么i和j重回,要么i下标是一个比base值大的数
            
            while ( i < j && arr[j] >= base)
                j-- ;
                //循环结束要么j和i重合,要么j下标是一个比base小的数
            
            //交换i和j下标的元素
            swap(arr,i ,j);
        
        //循环结束要将i或j(i和j此时在同一位置)位置的元素和right(基准值)元素进行交换
        swap(arr, i , right);
        //返回基准值位置
        return  i;
    

    private static void swap(int[] arr, int i, int j) 
        int tmp =  arr[i];
        arr[i] = arr[j];
        arr[j] = tmp ;
    

时间复杂度:O(N*log(N)) ;空间复杂度:O(log(N))
稳定性 : 不稳定排序

七、归并排序

1.原理

 升序排列:将数组分成若干个子数组,若子数组仅剩一个元素那么他就是有序的,然后将这些已有的子序列合并,得到
 一个有序的数列.而将两个有序表合成一个有序表就是"二路归并".

2.代码实现

递归实现

      public static void mergeSort(int[] arr)
        //创建一个helper方法帮助完成递归
        mergeSortHelper(arr ,0 ,arr.length);
    

    private static void mergeSortHelper(int[] arr, int low, int high) 
        if( high - low <= 1)
            return;
        
        //求出中间值
        int  mid = (low + high) / 2;
        //这个递归执行完 [low,mid)就已经排序好了
        mergeSortHelper(arr,low ,mid);
        //这个递归执行完[mid,high)就已经排序好了
        mergeSortHelper(arr,mid , high);
        //对[low, high)进行排序
        merge(arr ,low ,mid ,high);
    

    private static void merge(int[] arr, int low, int mid, int high) 
        int[] output = new int[high - low];
        int cur1 = low;
        int cur2 = mid;
        //记录output数组存放了多少元素
        int outputIndex = 0 ;
        while (cur1 < mid && cur2 < high)
            //这里写成 > 才能保证稳定性
            if(arr[cur1] > arr[cur2])
                output[outputIndex] = arr[cur2];
                outputIndex++;
                cur2 ++;
            else 
                output[outputIndex] = arr[cur1];
                outputIndex ++;
                cur1 ++;
            
        
        //上面循环结束不是cur1到mid就是cur2到high
        //再写两个循环将剩余的元素写入output数组中
        while (cur1 < mid)
            output[outputIndex] = arr[cur1];
            outputIndex ++;
            cur1 ++;
        
        while (cur2 < high)
            output[outputIndex] = arr[cur2];
            outputIndex ++;
            cur2 ++;
        
        //将output数组中的元素放回arr数组
        for(int i = 0 ;i < high - low ;i ++)
            arr[low + i ] = output[ i];
        
    

非递归实现

    public static void mergeSortByLoop(int[] arr) 
       //定义一个gap变量进行分组
        for (int gap = 1 ; gap < arr.length;gap *= 2)
            for(int i = 0 ;i < arr.length ;i = i + 2 * gap)
                int low = i ;
                int mid = i + gap;
                int high = i  + 2* gap;
                if(mid > arr.length)
                    mid  = arr.length;
                
                if(high > arr.length)
                    high = arr.length;
                
                merge(arr , low , mid ,high);
            
        
    

    private static void merge(int[] arr, int low, int mid, int high) 
        int[] output = new int[high - low];
        int cur1 = low;
        int cur2 = mid;
        //记录output数组存放了多少元素
        int outputIndex = 0 ;
        while (cur1 < mid && cur2 < high)
            //这里写成 > 才能保证稳定性
            if(arr[cur1] > arr[cur2])
                output[outputIndex] = arr[cur2];
                outputIndex++;
                cur2 ++;
            else 
                output[outputIndex] = arr[cur1];
                outputIndex ++;
                cur1 ++;
            
        
        //上面循环结束不是cur1到mid就是cur2到high
        //再写两个循环将剩余的元素写入output数组中
        while (cur1 < mid)
            output[outputIndex] = arr[cur1];
            outputIndex ++;
            cur1 ++;
        
        while (cur2 < high)
            output[outputIndex] = arr[cur2];
            outputIndex ++;
            cur2 ++;
        
        //将output数组中的元素放回arr数组
        for(int i = 0 ;i < high - low 六千字快速复习七种常用排序(代码片段)
文章目录一、插入排序1.原理2.代码实现二、希尔排序1.原理2.代码实现三、选择排序1.原理2.代码实现四、堆排序1.原理2.代码实现五、冒泡排序1.原理2.代码实现六、快速排序1.原理2.代码实现递归版本非递归版本七、归并排序1.原...  查看详情  
                
分支结构，你会了吗？（五千字超详细教程，带你快速复习）(代码片段)
本章目录每篇前言1.导语2.目标3.知识点1，运算符or表达式   1.1，关系运算符和关系表达式     1.1.1，关系运算符     1.1.2，关系表达式     1.1.3，关系运算实例   1.2，逻辑运算符...  查看详情  
                
拷贝构造，赋值运算符重载（六千字长文详解！）(代码片段)
c++之类和对象详解拷贝构造，赋值运算符重载拷贝构造拷贝构造特征那能不呢使用指针呢？答案是可以的！==因为指针的类型是date产生的临时变量不会引发拷贝构造，但是这时候叫做构造函数，不是拷贝构造函数！==，==因为拷...  查看详情  
                
java容器（listsetmap）知识点快速复习手册（下）
前言本文快速回顾了Java中容器的知识点，用作面试复习，事半功倍。上篇：容器概览，容器中用到的设计模式，List源码中篇：Map源码下篇：Set源码，容器总结其它知识点复习手册Java基础知识点面试手册（上）Java基础知识点面...  查看详情  
                
java容器（listsetmap）知识点快速复习手册（上）
前言本文快速回顾了Java中容器的知识点，用作面试复习，事半功倍。上篇：主要为容器概览，容器中用到的设计模式，List源码中篇：Map源码下篇：Set源码，容器总结其它知识点复习手册Java基础知识点面试手册（上）Java基础知...  查看详情  
                
python从入门到精通五万六千字对python基础知识做一个了结吧！（二十八）值得收藏(代码片段)
为什么写这篇文章我从2021年6月13号写下第一篇Python的系列专栏算起，陆续更新了二十七篇Python系列文章。在此感谢读者朋友们的支持和阅读，特别感谢一键三连的小伙伴。本专栏起名【Python从入门到精通】，主要分...  查看详情  
                
python从入门到精通五万六千字对python基础知识做一个了结吧！（二十八）值得收藏(代码片段)
为什么写这篇文章我从2021年6月13号写下第一篇Python的系列专栏算起，陆续更新了二十七篇Python系列文章。在此感谢读者朋友们的支持和阅读，特别感谢一键三连的小伙伴。本专栏起名【Python从入门到精通】，主要分...  查看详情  
                
猿创征文｜基于反事实的因果推理causalinferencebasedoncounterfactuals--一万六千字文献详细解读（因果关系的推理应用）全文总结
前言：        在研0的这个暑假当中，这篇文章也是对自己近两个月以来的部分学习做了一个ending!!在这段生活当中，经历了难受，经历了迷茫找不到一个属于自己的学习方法。写下这篇文章解读也对自己近段...  查看详情  
                
六消息队列复习
1为什么使用消息队列？　　六个字：解耦、异步、消峰。2使用消息队列有什么缺点？　　消息队列挂了，系统就不能用了，系统可用性降低。3消息队列的高可用？　　kafka使用zookeeper，master/slave,保证高可用；　　Kafka通过Zookeep...  查看详情  
                
html快速复习
1,强调em用斜体strong用粗体2，<q>引用文本</q>blockquote标签长文本引用块级引用3,address为网页加入联系地址信息4,<code>一行代码</code><pre>多行代码</pre>5，无序列表ul>li有序列表ol>li6,div是独立的版块7，...  查看详情  
                
六千字让你明白什么是数字孪生？
文章目录1.背景2.数字孪生基础2.1概念2.2价值3.技术生态3.1技术体系3.2核心技术3.2.1多领域、多尺度融合建模3.2.2数据驱动与物理模型融合的状态评估3.2.3数据采集和传输3.2.4全生命周期数据管理3.2.5虚拟现实呈现3.2.6高性能计算3.3建...  查看详情  
                
常见的七种排序算法（java实现）
...法[Java代码]1.冒泡排序2.选择排序3.插入排序4.希尔排序5.快速排序6.归并排序7.基数排序一、算法的一些概念1.排序算法分类排序也称排序算法  查看详情  
                
《麦肯锡方法》读完后的千字感悟
《麦肯锡方法》读完后的千字感悟文章目录问题拆解团队的重要性汇报沟通会议公司和家最后肯锡方法》看完了。在不重新复习前面知识的情况下，讲讲几点我感触最深和印象最深的。问题拆解MECE原则的核心：相互独立...  查看详情  
                
复习之七种寻址
段寄存器：CS、DS、ES、SS1.指令指令由操作数码和操作数两部分构成操作码：说明计算机要执行的操作，如传送、运算、移位、跳转等操作，它是指令中不可缺少的组成部分。    操作数：是指令执行的参与者，即...  查看详情  
                
spring框架爆gan两万六千字，助你通关ioc和di(代码片段)
✅作者简介：热爱Java后端开发的一名学习者，大家可以跟我一起讨论各种问题喔。🍎个人主页：Hhzzy99🍊个人信条：坚持就是胜利！💞当前专栏：【Spring】🥭本文内容：Spring框架IoC和DI...  查看详情  
                
常见的七种排序算法（java实现）(代码片段)
...法[Java代码]1.冒泡排序2.选择排序3.插入排序4.希尔排序5.快速排序6.归并排序7.基数排序一、算法的一些概念1.排序算法分类排序也称排序算法  查看详情  
                
常见的七种排序算法（java实现）(代码片段)
...法[Java代码]1.冒泡排序2.选择排序3.插入排序4.希尔排序5.快速排序6.归并排序7.基数排序一、算法的一些概念1.排序算法分类排序也称排序算法  查看详情  
                
计算机网络之物理层3千字考前知识点复习专用
物理层2.1物理层的基本概念2.2数据通信的基础知识传输方式常用术语编码与调制基本编码基本调制2.3物理层下面的传输媒体2.4信道复用技术信道分类信道复用1.频分复用2.时分复用3.统计时分复用4.波分复用5.码分复用2.5&2.6就考...  查看详情