Java实现几种常见排序方法

悠悠 2022-07-14 10:51 212阅读 0赞

日常操作中常见的排序方法有：冒泡排序、快速排序、选择排序、插入排序、希尔排序，甚至还有基数排序、鸡尾酒排序、桶排序、鸽巢排序、归并排序等。

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

![复制代码][copycode.gif]

![ExpandedBlockStart.gif][] 代码

/\*\*     
 \* 冒泡法排序<br/>    
  
 \* <li>比较相邻的元素。如果第一个比第二个大，就交换他们两个。</li>    
 \* <li>对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。</li>    
 \* <li>针对所有的元素重复以上的步骤，除了最后一个。</li>    
 \* <li>持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。</li>    
  
 \*     
 \*  @param  numbers    
 \*            需要排序的整型数组    
  \*/     
 public   static   void  bubbleSort( int \[\] numbers) \{     
     int  temp;  //  记录临时中间值      
      int  size  =  numbers.length;  //  数组大小      
      for  ( int  i  =   0 ; i  <  size  \-   1 ; i \++ ) \{     
         for  ( int  j  =  i  \+   1 ; j  <  size; j \++ ) \{     
             if  (numbers\[i\]  <  numbers\[j\]) \{  //  交换两数的位置      
                 temp  =  numbers\[i\];     
                numbers\[i\]  =  numbers\[j\];     
                numbers\[j\]  =  temp;     
            \}     
        \}     
    \}     
\}

![复制代码][copycode.gif]

快速排序使用分治法策略来把一个序列分为两个子序列。

![复制代码][copycode.gif]

![ExpandedBlockStart.gif][] 代码

/\*\*     
 \* 快速排序<br/>    
 \* <ul>    
 \* <li>从数列中挑出一个元素，称为“基准”</li>    
 \* <li>重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割之后，    
 \* 该基准是它的最后位置。这个称为分割（partition）操作。</li>    
 \* <li>递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。</li>    
 \* </ul>    
 \*     
 \*  @param  numbers    
 \*  @param  start    
 \*  @param  end    
  \*/     
 public   static   void  quickSort( int \[\] numbers,  int  start,  int  end) \{     
     if  (start  <  end) \{     
         int  base  =  numbers\[start\];  //  选定的基准值（第一个数值作为基准值）      
          int  temp;  //  记录临时中间值      
          int  i  =  start, j  =  end;     
         do  \{     
             while  ((numbers\[i\]  <  base)  &&  (i  <  end))     
                i \++ ;     
             while  ((numbers\[j\]  >  base)  &&  (j  >  start))     
                j \-- ;     
             if  (i  <=  j) \{     
                temp  =  numbers\[i\];     
                numbers\[i\]  =  numbers\[j\];     
                numbers\[j\]  =  temp;     
                i \++ ;     
                j \-- ;     
            \}     
        \}  while  (i  <=  j);     
         if  (start  <  j)     
            quickSort(numbers, start, j);     
         if  (end  >  i)     
            quickSort(numbers, i, end);     
    \}     
\}

![复制代码][copycode.gif]

选择排序是一种简单直观的排序方法，每次寻找序列中的最小值，然后放在最末尾的位置。

![复制代码][copycode.gif]

![ExpandedBlockStart.gif][] 代码

/\*\*     
 \* 选择排序<br/>    
 \* <li>在未排序序列中找到最小元素，存放到排序序列的起始位置</li>    
 \* <li>再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。</li>    
 \* <li>以此类推，直到所有元素均排序完毕。</li>    
  
 \*     
 \*  @param  numbers    
  \*/     
 public   static   void  selectSort( int \[\] numbers) \{     
     int  size  =  numbers.length, temp;     
     for  ( int  i  =   0 ; i  <  size; i \++ ) \{     
         int  k  =  i;     
         for  ( int  j  =  size  \-   1 ; j  > i; j \-- )  \{     
             if  (numbers\[j\]  <  numbers\[k\])  k  =  j;     
        \}     
        temp  =  numbers\[i\];     
        numbers\[i\]  =  numbers\[k\];     
        numbers\[k\]  =  temp;     
    \}     
\}

![复制代码][copycode.gif]

插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。其具体步骤参见代码及注释。

![复制代码][copycode.gif]

![ExpandedBlockStart.gif][] 代码

/\*\*     
 \* 插入排序<br/>    
 \* <ul>    
 \* <li>从第一个元素开始，该元素可以认为已经被排序</li>    
 \* <li>取出下一个元素，在已经排序的元素序列中从后向前扫描</li>    
 \* <li>如果该元素（已排序）大于新元素，将该元素移到下一位置</li>    
 \* <li>重复步骤3，直到找到已排序的元素小于或者等于新元素的位置</li>    
 \* <li>将新元素插入到该位置中</li>    
 \* <li>重复步骤2</li>    
 \* </ul>    
 \*     
 \*  @param  numbers    
  \*/     
 public   static   void  insertSort( int \[\] numbers) \{     
     int  size  =  numbers.length, temp, j;     
     for ( int  i = 1 ; i < size; i \++ ) \{     
        temp  =  numbers\[i\];     
         for (j  =  i; j  >   0   &&  temp  <  numbers\[j \- 1 \]; j \-- )     
            numbers\[j\]  =  numbers\[j \- 1 \];     
        numbers\[j\]  =  temp;     
    \}     
\}

![复制代码][copycode.gif]

归并排序是建立在归并操作上的一种有效的排序算法，归并是指将两个已经排序的序列合并成一个序列的操作。参考代码如下：

![复制代码][copycode.gif]

![ExpandedBlockStart.gif][] 代码

/\*\*     
 \* 归并排序<br/>    
 \* <ul>    
 \* <li>申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列</li>    
 \* <li>设定两个指针，最初位置分别为两个已经排序序列的起始位置</li>    
 \* <li>比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置</li>    
 \* <li>重复步骤3直到某一指针达到序列尾</li>    
 \* <li>将另一序列剩下的所有元素直接复制到合并序列尾</li>    
 \* </ul>    
 \*     
 \*  @param  numbers    
  \*/     
 public   static   void  mergeSort( int \[\] numbers,  int  left,  int  right) \{     
     int  t  =   1 ; //  每组元素个数      
      int  size  =  right  \-  left  \+   1 ;     
     while  (t  <  size) \{     
         int  s  =  t; //  本次循环每组元素个数      
         t  =   2   \*  s;     
         int  i  =  left;     
         while  (i  \+  (t  \-   1 )  <  size) \{     
            merge(numbers, i, i  \+  (s  \-   1 ), i  \+  (t  \-   1 ));     
            i  \+=  t;     
        \}     
         if  (i  \+  (s  \-   1 )  <  right)     
            merge(numbers, i, i  \+  (s  \-   1 ), right);     
    \}     
\}     
 /\*\*     
 \* 归并算法实现    
 \*     
 \*  @param  data    
 \*  @param  p    
 \*  @param  q    
 \*  @param  r    
  \*/     
 private   static   void  merge( int \[\] data,  int  p,  int  q,  int  r) \{     
     int \[\] B  =   new   int \[data.length\];     
     int  s  =  p;     
     int  t  =  q  \+   1 ;     
     int  k  =  p;     
     while  (s  <=  q  &&  t  <=  r) \{     
         if  (data\[s\]  <=  data\[t\]) \{     
            B\[k\]  =  data\[s\];     
            s \++ ;     
        \}  else  \{     
            B\[k\]  =  data\[t\];     
            t \++ ;     
        \}     
        k \++ ;     
    \}     
     if  (s  ==  q  \+   1 )     
        B\[k \++ \]  =  data\[t \++ \];     
     else     
        B\[k \++ \]  =  data\[s \++ \];     
     for  ( int  i  =  p; i  <=  r; i \++ )     
        data\[i\]  =  B\[i\];     
\}

![复制代码][copycode.gif]

将之前介绍的所有排序算法整理成NumberSort类，代码

![复制代码][copycode.gif]

![ExpandedBlockStart.gif][] 代码

package  test.sort;     
 import  java.util.Random;     
 // Java实现的排序类     
 public   class  NumberSort \{     
     // 私有构造方法，禁止实例化     
      private  NumberSort() \{     
         super ();     
    \}      
     // 冒泡法排序    
      public   static   void  bubbleSort( int \[\] numbers) \{     
         int  temp;  //  记录临时中间值      
          int  size  =  numbers.length;  //  数组大小      
          for  ( int  i  =   0 ; i  <  size  \-   1 ; i \++ ) \{     
             for  ( int  j  =  i  \+   1 ; j  <  size; j \++ ) \{     
                 if  (numbers\[i\]  <  numbers\[j\]) \{  //  交换两数的位置      
                     temp  =  numbers\[i\];     
                    numbers\[i\]  =  numbers\[j\];     
                    numbers\[j\]  =  temp;     
                \}     
            \}     
        \}     
    \}     
     // 快速排序   
      public   static   void  quickSort( int \[\] numbers,  int  start,  int  end) \{     
         if  (start  <  end) \{     
             int  base  =  numbers\[start\];  //  选定的基准值（第一个数值作为基准值）      
              int  temp;  //  记录临时中间值      
              int  i  =  start, j  =  end;     
             do  \{     
                 while  ((numbers\[i\]  <  base)  &&  (i  <  end))     
                    i \++ ;     
                 while  ((numbers\[j\]  >  base)  &&  (j  >  start))     
                    j \-- ;     
                 if  (i  <=  j) \{     
                    temp  =  numbers\[i\];     
                    numbers\[i\]  =  numbers\[j\];     
                    numbers\[j\]  =  temp;     
                    i \++ ;     
                    j \-- ;     
                \}     
            \}  while  (i  <=  j);     
             if  (start  <  j)     
                quickSort(numbers, start, j);     
             if  (end  >  i)     
                quickSort(numbers, i, end);     
        \}     
    \}     
     // 选择排序    
      public   static   void  selectSort( int \[\] numbers) \{     
         int  size  =  numbers.length, temp;     
         for  ( int  i  =   0 ; i  <  size; i \++ ) \{     
             int  k  =  i;     
             for  ( int  j  =  size  \-   1 ; j  >  i; j \-- ) \{     
                 if  (numbers\[j\]  <  numbers\[k\])     
                    k  =  j;     
            \}     
            temp  =  numbers\[i\];     
            numbers\[i\]  =  numbers\[k\];     
            numbers\[k\]  =  temp;     
        \}     
    \}     
     // 插入排序      
     //  @param numbers     
      public   static   void  insertSort( int \[\] numbers) \{     
         int  size  =  numbers.length, temp, j;     
         for  ( int  i  =   1 ; i  <  size; i \++ ) \{     
            temp  =  numbers\[i\];     
             for  (j  =  i; j  >   0   &&  temp  <  numbers\[j  \-   1 \]; j \-- )     
                numbers\[j\]  =  numbers\[j  \-   1 \];     
            numbers\[j\]  =  temp;     
        \}     
    \}     
     // 归并排序     
      public   static   void  mergeSort( int \[\] numbers,  int  left,  int  right) \{     
         int  t  =   1 ; //  每组元素个数      
          int  size  =  right  \-  left  \+   1 ;     
         while  (t  <  size) \{     
             int  s  =  t; //  本次循环每组元素个数      
             t  =   2   \*  s;     
             int  i  =  left;     
             while  (i  \+  (t  \-   1 )  <  size) \{     
                merge(numbers, i, i  \+  (s  \-   1 ), i  \+  (t  \-   1 ));     
                i  \+=  t;     
            \}     
             if  (i  \+  (s  \-   1 )  <  right)     
                merge(numbers, i, i  \+  (s  \-   1 ), right);     
        \}     
    \}      
     // 归并算法实现     
      private   static   void  merge( int \[\] data,  int  p,  int  q,  int  r) \{     
         int \[\] B  =   new   int \[data.length\];     
         int  s  =  p;     
         int  t  =  q  \+   1 ;     
         int  k  =  p;     
         while  (s  <=  q  &&  t  <=  r) \{     
             if  (data\[s\]  <=  data\[t\]) \{     
                B\[k\]  =  data\[s\];     
                s \++ ;     
            \}  else  \{     
                B\[k\]  =  data\[t\];     
                t \++ ;     
            \}     
            k \++ ;     
        \}     
         if  (s  ==  q  \+   1 )     
            B\[k \++ \]  =  data\[t \++ \];     
         else     
            B\[k \++ \]  =  data\[s \++ \];     
         for  ( int  i  =  p; i  <=  r; i \++ )     
            data\[i\]  =  B\[i\];     
    \}     
    
\}

![复制代码][copycode.gif]

数字排序算法通常用来作为算法入门课程的基本内容，在实际应用（尤其是普通商业软件）中使用的频率较低，但是通过排序算法的实现，可以深入了解计算机语言的特点，可以以此作为学习各种编程语言的基础。

[copycode.gif]: /images/20220714/af7c2bc04ca84389b2b57c883a3eeb1b.png
[ExpandedBlockStart.gif]: /images/20220714/a650f6199bd74b84966982b140b99e1a.png

发表评论取消回复

表情：

评论列表（有 0 条评论，212人围观）

还没有评论，来说两句吧...

相关阅读

相关几种常见排序

1. 归并排序【图来自[归并排序][Link 1]】 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_

ゝ一纸荒年。/ 2023年07月14日 13:59/ 0 赞/ 20 阅读

相关时间排序_几种常见排序方法的实现及时间对比（JAVA）

![220ac7ce6c81f3b514b4fc12b6ad68a3.png][] 首先贴出工具类 ArrayUtil: import org.apache.

清疚/ 2023年01月06日 04:27/ 0 赞/ 132 阅读

相关几种常见的排序算法

排序的基本知识点 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ib

逃离我推掉我的手/ 2022年11月21日 14:59/ 0 赞/ 267 阅读

相关 Java实现几种常见排序方法

日常操作中常见的排序方法有：冒泡排序、快速排序、选择排序、插入排序、希尔排序，甚至还有基数排序、鸡尾酒排序、桶排序、鸽巢排序、归并排序等。冒泡排序是一种简单的排序算法。它重

悠悠/ 2022年07月14日 10:51/ 0 赞/ 213 阅读

相关 java几种常见的排序：冒泡排序，快速排序

下面给大家简单介绍几种常用的内部排序：简单的内部排序分为：插入排序（直接插入排序、希尔排序），选择排序（简单选择排序、堆排序），交换排序（冒泡排序、快速排序），归并

冷不防/ 2022年07月12日 02:07/ 0 赞/ 222 阅读

相关几种常见的内部排序

排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。排序分为内部排序和外部排序。随着计算机的内存不断扩大和查找算

以你之姓@/ 2022年06月02日 06:42/ 0 赞/ 252 阅读

相关几种排序的方法

1、冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个

你的名字/ 2022年05月21日 06:11/ 0 赞/ 310 阅读

相关常见的几种排序算法

转载：[http://www.cnblogs.com/eniac12/p/5329396.html\s1　][http_www.cnblogs.com_eniac12_p_5

蔚落/ 2022年05月21日 04:24/ 0 赞/ 293 阅读

相关实现数组排序的几种方法

冒泡排序这里先介绍一下冒泡排序。 1. 其原理就是相邻的两个元素进行比较，如果第一个元素大于第二个元素，则交换这两个元素的位置。如此两两比较然后交换，一轮下来，最大的元

男娘i/ 2022年04月18日 02:16/ 0 赞/ 291 阅读

相关 Java的几种常见排序算法

　　一、所谓[排序][Link 1]，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多

阳光穿透心脏的1/2处/ 2021年12月14日 10:39/ 0 赞/ 377 阅读