5种常用的Java排序算法

Java 本身就是一门灵活的语言，支持多种排序算法的操作。这些算法中的大多数本身都非常灵活，可以使用递归和迭代方法来实现。以下是动力节点为大家介绍java中最流行的5种排序算法：

合并排序

堆排序

插入排序

选择排序

冒泡排序

让我们详细了解这些 java 排序算法。

1.合并排序

合并排序是人类已知的 java 中最灵活的排序算法之一(是的，不是开玩笑)。它使用分而治之的策略对数组中的元素进行排序。它也是一种稳定的排序，这意味着它不会改变数组中彼此相关的原始元素的顺序。底层策略将数组分解为多个较小的段，直到获得只有两个元素(或一个元素)的段。现在，对这些段中的元素进行排序，并合并这些段以形成更大的段。这个过程一直持续到整个数组被排序。

该算法有两个主要部分：

mergeSort() -此函数计算子数组的中间索引，然后将子数组分成两半。前半部分从索引左到中，后半部分从索引中间+1 到右。分区完成后，该函数会自动调用 merge() 函数对由 mergeSort() 调用处理的子数组进行排序。

merge() -此函数为排序过程执行实际繁重的工作。它需要输入四个参数——数组、起始索引(左)、中间索引(中间)和结束索引(右)。收到后，merge() 会将子数组拆分为两个子数组——一个左子数组和一个右子数组。左子数组从索引左到中运行，而右子数组从索引middle+1 运行到右。该函数然后合并两个子数组以获得排序的子数组。

合并排序 Java 代码：

类 排序 
{
    无效 合并( int arr [],  int left ,  int middle ,  int right ) 
    { 
        int low = middle - left +  1 ;                     //左子数组的大小
        int high = right - middle ;                       //右子数组的大小 
        诠释L []  = 新 诠释[低];                              //创建左右子数组
        int R []  =  new  int [ high ];
        整数i =  0 , j =  0 ; 
        for  ( i =  0 ; i < low ; i ++)                                //复制元素到左子数组
        { 
            L [ i ]  = arr [ left + i ]; 
        } 
        for  ( j =  0 ; j < high ; j ++)                               //复制元素到右子数组
        { 
            R [ j ]  = arr [ middle +  1  +Ĵ ]; 
        }         
        诠释k =左;                                            //获取排序的起始索引
        i =  0 ;                                              //在执行合并之前重置循环变量
        j =  0 ;
        while  ( i < low && j < high )                      //合并左右子数组
        { 
            if  ( L [ i ]  <= R [ j ])  
            { 
                arr [ k ]  = L [ i ]; 
                我++; 
            }
            其他 
            { 
                arr [ k ]  = R [ j ]; 
                Ĵ ++; 
            }
            ķ ++; 
        } 
        while  ( i < low )                              //合并左子数组的剩余元素
        { 
            arr [ k ]  = L [ i ]; 
            我++; 
            ķ ++; 
        } 
        while  ( j < high )                            //合并右子数组的剩余元素
        { 
            arr [ k ]  = R [ j ]; 
            Ĵ ++; 
            ķ ++; 
        } 
    }
    void  mergeSort ( int arr [],  int left ,  int right )        //为排序创建子案例的辅助函数
    { 
        int middle ; 
        if  ( left < right )  {                              // 仅当左侧索引小于右侧索引时才排序（表示已排序） 
            middle =  ( left + right )  /  2 ; 
            合并排序（ arr ，左，中）；                    //左子
            数组 mergeSort ( arr , middle +  1 , right );                //右子数组 
            合并（ arr ，左，中，右）；                //合并两个子数组
        } 
    } 
    void  display ( int arr [])                  //显示数组
    {   
        for  ( int i = 0 ; i < arr .length ; ++ i ) { 
            System . 出来。打印( arr [ i ]+ " " ); } }      
    public  static  void  main ( String args []) 
    { 
        int arr []  =  {  9 ,  3 ,  1 ,  5 ,  13 ,  12  }; 
        排序 ob =  new Sort (); 
        ob _ 合并排序( arr ,  0 , arr .length - 1 ) ; 
        ob _ 显示（ arr ）；} }     

解释它是如何工作的

2.堆排序

堆排序是java中最重要的排序方法之一，需要学习才能进入排序。它结合了树和排序的概念，适当地加强了两者概念的使用。堆是一个完整的二叉搜索树，其中项目根据要求以特殊顺序存储。最小堆包含根处的最小元素，并且根的每个孩子都必须大于根本身。之后级别的孩子必须大于这些孩子，依此类推。类似地，最大堆包含根处的最大元素。对于排序过程，堆存储为一个数组，其中对于索引 i 处的每个父节点，左子节点位于索引 2 * i + 1 处，右子节点位于索引 2 * i + 2 处。

用未排序数组的元素构建一个最大堆 ，然后从数组的根中提取最大元素，然后与数组的最后一个元素进行交换。完成后，将重建最大堆以获取下一个最大元素。这个过程一直持续到堆中只有一个节点。

该算法有两个主要部分：

heapSort() -此函数有助于构建最初使用的最大堆。完成后，将提取每个根元素并将其发送到数组的末尾。完成后，将从根中重建最大堆。再次提取根并将其发送到数组的末尾，因此该过程继续进行。

heapify() -此函数是堆排序算法的构建块。此函数确定正在检查的元素作为根及其两个子元素的最大值。如果最大值在根的孩子之间，则交换根和它的孩子。然后对新根重复此过程。当找到数组中的最大元素(使其子元素小于它)时，函数停止。对于索引 i 处的节点，左孩子在索引 2 * i + 1 处，右孩子在索引 2 * i + 1 处。(数组中的索引从 0 开始，因此根在 0)。

堆排序 Java 代码：

类 排序 { 
    public  void  heapSort ( int arr []) 
    { 
        int temp ; 
        for  ( int i = arr .length / 2 - 1 ; i >= 0 ; i --) //建立堆{ 
            heapify ( arr , arr .length , i ) ; }                      
        for  ( int i = arr .length - 1 ; i > 0 ; i -- ) //从堆中提取元素{ 
            temp = arr [ 0 ]; //将当前根移动到末尾（因为它是最大的） 
            arr [ 0 ] = arr [ i ]; 
            arr [我] =温度; 
            heapify ( arr ,我,                                                                                            0 );                                              //recall heapify 为剩余的元素重建堆
        } 
    } 
    void  heapify ( int arr [],  int n ,  int i ) 
    { 
        int MAX = i ;  // 将最大初始化为根
        int left =  2  * i +  1 ;  //第i个节点的左孩子的索引 = 2*i + 1 
        int right =  2  * i +  2 ;  //第i个节点的右孩子的索引= 2 * i + 2 
        int temp ;
        if  ( left < n && arr [ left ]  > arr [ MAX ])             //检查根的左孩子是否大于根
        { 
            MAX = left ; 
        } 
        if  ( right < n && arr [ right ]  > arr [ MAX ])             //检查根的右孩子是否大于根
        { 
            MAX = right ; 
        } 
        if  ( MAX != i )  
        {                                                //重复寻找堆中最大元素的过程
            temp = arr [ i ]; 
            arr [ i ]  = arr [最大值]；
            arr [最大值]  =温度；
            堆化（ arr ， n ， MAX ）；
        } 
    }
    void  display ( int arr [])                  //显示数组
    {   
        for  ( int i = 0 ; i < arr .length ; ++ i ) { 
            System . 出来。打印( arr [ i ]+ " " ); } }   
    public  static  void  main ( String args []) 
    { 
        int arr []  =  {  1 ,  12 ,  9  ,  3 ,  10 ,  15  }; 
        排序 ob =  new Sort (); 
        ob _ 堆排序（ arr ）；
        ob _ 显示（ arr ）；
    } 
}

解释它是如何工作的：

3.插入排序

如果您已经完成了更复杂的排序算法并希望继续使用更简单的方法：插入排序是您的最佳选择。虽然它不是对数组排序的优化算法，但它是更容易理解的算法之一。实施也很容易。在插入排序中，人们选择一个元素并将其视为关键。如果密钥小于其前任，则将其移动到数组中的正确位置。

算法：

开始

重复步骤 2 到 4，直到到达数组末端。

将当前索引 i 处的元素与其前身进行比较。如果较小，请重复步骤 3。

继续从数组的“排序”部分移动元素，直到找到键的正确位置。

递增循环变量。

结尾

插入排序 Java 代码：

class  Sort   
{  
    static  void  insertSort ( int arr [],  int n )  
    {  
        if  ( n <=  1 )                              //passes are done 
        { 
            return ;  
        }
        插入排序( arr , n - 1  );         //一个元素排序，剩下的数组排序       
        int last = arr [ n - 1 ];                         //数组的最后一个元素
        int j = n - 2 ;                                 //正确的数组最后一个元素的索引       
        while  ( j >=  0  && arr [ j ]  > last )                  //找到最后一个元素的正确索引
        {  
            arr [ j + 1 ]  = arr [ j ];                           //如果没有找到正确的索引，则将已排序元素的部分向上移动一个元素
            j --;  
        }  
        arr [ j + 1 ]  =最后;                             //将最后一个元素设置在正确的索引处
    } 
    void  display ( int arr [])                  //显示数组
    {   
        for  ( int i = 0 ; i < arr .length ; ++ i ) { 
            System . 出来。打印( arr [ i ]+ " " ); } }                
    公共 静态 无效 主要（字符串[] args ） 
    {  
        int arr []  =  { 22 ,  21 ,  11 ,  15 ,  16 };        
        插入排序（ arr ， arr.length ）； 
        排序 ob = new Sort (); 
        ob _ 显示（ arr ）；} }  

解释它是如何工作的：

4.选择排序

二次排序算法是一些比较流行的排序算法，易于理解和实现。这些并没有为数组排序提供独特或优化的方法——相反，它们应该为刚接触它的人提供排序概念的构建块。在选择排序中，使用了两个循环。内部循环从数组中挑选最小元素并将其移动到外部循环指示的正确索引处。在外循环的每次运行中，一个元素都会移动到数组中的正确位置。它也是python中非常流行的排序算法。

算法：

开始

运行两个循环：一个内循环和一个外循环。

重复步骤直到找到最小元素。

将外部循环变量标记的元素标记为最小值。

如果内部循环中的当前元素小于标记的最小元素，则将最小元素的值更改为当前元素。

将最小元素的值与外部循环变量标记的元素交换。

结尾

选择排序 Java 代码：

类 排序 
{  
    void  selectionSort ( int arr [])  
    {  
        int pos ; 
        国际温度; 
        for  ( int i =  0 ; i < arr .length ; i ++ ) {  
            pos = i ; for ( int j = i + 1 ; j < arr .length ; j ++ ) {           
                if  ( arr [ j ]  < arr [ pos ])                   //找到最小元素的索引
                { 
                    pos = j ; 
                } 
            }
            温度= arr [位置];             //用最小元素交换当前元素
            arr [ pos ]  = arr [ i ];  
            arr [我]  =温度;  
        }  
    }   
    void  display ( int arr [])                      //显示数组
    {  
        for  ( int i = 0 ; i < arr .length ; i ++ ) { 
            System . 出来。打印( arr [ i ]+ " " ); } } 
    public  static  void  main ( String args [])  
    {  
        Sort ob =  new Sort ();  
        int arr []  =  { 64 , 25 , 12 , 22 , 11 };  
        ob _ 选择排序( arr );  
        ob _ 显示（ arr ）； 
    }  
} 

解释它是如何工作的：

5.冒泡排序

大多数初学者开始其排序生涯的两种算法是冒泡排序和选择排序。这些排序算法效率不高，但它们提供了对什么是排序以及排序算法如何在幕后工作的关键见解。冒泡排序依赖于多次交换而不是单一的选择排序。该算法继续重复数组遍历，交换不在正确位置的元素。

算法：

开始

运行两个循环——一个内循环和一个外循环。

重复步骤，直到外循环用尽。

如果内部循环中的当前元素小于其下一个元素，则交换两个元素的值。

结尾

冒泡排序Java代码：

class  Sort  
{ 
    static  void  bubbleSort ( int arr [],  int n ) 
    {                                        
        if  ( n ==  1 )                      //passes are done 
        { 
            return ; 
        }
        for  ( int i = 0 ; i < n - 1 ; i ++)        //遍历未排序的元素
        { 
            if  ( arr [ i ]  > arr [ i + 1 ])       //检查元素是否有序
            {                            //如果没有，交换它们
                int temp = arr [ i ]; 
                arr [ i ]  = arr [ i + 1 ];
                arr [ i + 1 ]  =温度；
            } 
        }            
        冒泡排序( arr , n - 1 );            //一次完成，继续下一个
    }
    void  display ( int arr [])                  //显示数组
    {   
        for  ( int i = 0 ; i < arr .length ; ++ i ) { 
            System . 出来。打印( arr [ i ]+ " " ); } }     
    public  static  void  main ( String [] args ) 
    { 
        Sort ob =  new Sort (); 
        int arr []  =  { 6 ,  4 ,  5 ,  12 ,  2 ,  11 ,  9 };     
        冒泡排序（ arr ， arr .length ）；
        ob _ 显示（ arr ）；} }

解释它是如何工作的：