Code666 (代码贴、代码片段)

[Java] java版快速排序法 →→→→→进入此内容的聊天室

来自 , 2020-10-19, 写在 Java, 查看 151 次.
URL http://www.code666.cn/view/d7532079
  1.  /*
  2.    
  3.     * 快速排序是最流行的排序算法，本质上通过把一个数组划分为两个子数组，
  4.    
  5.     * 然后递归地调用自身为每一个子数组进行快速排序来实现。
  6.    
  7.     * ArrayIns.java
  8.    
  9.     * linzhanghui@gmail.com
  10.    
  11.     */
  12.    
  13.     package linzhanghui.quicksort;
  14.    
  15.     public class ArrayIns {
  16.    
  17.     private long[] theArray;
  18.    
  19.     private int nElems;
  20.    
  21.     public ArrayIns（int max） {
  22.    
  23.     theArray = new long[max];
  24.    
  25.     nElems = 0;
  26.    
  27.     }
  28.    
  29.     public void insert（long value） {
  30.    
  31.     theArray[nElems] = value;
  32.    
  33.     nElems++;
  34.    
  35.     }
  36.    
  37.     public void display（） {
  38.    
  39.     System.out.print（"A="）；
  40.    
  41.     for（int j=0; j<nElems; j++）
  42.    
  43.     System.out.print（theArray[j] + " "）；
  44.    
  45.     System.out.println（""）；
  46.    
  47.     }
  48.    
  49.     public void quickSort（） {
  50.    
  51.     recQuickSort（0, nElems-1）；
  52.    
  53.     }
  54.    
  55.     public void recQuickSort（int left, int right） {
  56.    
  57.     if（right-left <= 0）
  58.    
  59.     return;
  60.    
  61.     else {
  62.    
  63.     long pivot = theArray[right];
  64.    
  65.     int partition = partitionIt（left, right, pivot）；
  66.    
  67.     recQuickSort（left, partition-1）；
  68.    
  69.     recQuickSort（partition+1, right）；
  70.    
  71.     }
  72.    
  73.     }
  74.    
  75.     public int partitionIt（int left, int right, long pivot） {
  76.    
  77.     int leftPtr = left-1;
  78.    
  79.     int rightPtr = right;
  80.    
  81.     while（true） {
  82.    
  83.     while（ theArray[++leftPtr] < pivot）
  84.    
  85.     ;
  86.    
  87.     while（rightPtr > 0 && theArray[--rightPtr] > pivot）
  88.    
  89.     ;
  90.    
  91.     if（leftPtr >= rightPtr）
  92.    
  93.     break;
  94.    
  95.     else
  96.    
  97.     swap（leftPtr, rightPtr）；
  98.    
  99.     }
  100.    
  101.     swap（leftPtr, right）；
  102.    
  103.     return leftPtr;
  104.    
  105.     }
  106.    
  107.     public void swap（int dex1, int dex2） {
  108.    
  109.     long temp = theArray[dex1];
  110.    
  111.     theArray[dex1] = theArray[dex2];
  112.    
  113.     theArray[dex2] = temp;
  114.    
  115.     }
  116.    
  117.     }
  118.    
  119.     /*
  120.    
  121.     * 程序随机产生16个2位随机数，显示这16个随机数后，对其进行快速排序并输出。
  122.    
  123.     * linzhanghui@gmail.com
  124.    
  125.     */
  126.    
  127.     package linzhanghui.quicksort;
  128.    
  129.     public class QuickSortApp {
  130.    
  131.     public static void main（String[] args） {
  132.    
  133.     int maxSize = 16;
  134.    
  135.     ArrayIns arr;
  136.    
  137.     arr = new ArrayIns（maxSize）；
  138.    
  139.     for（int j=0; j<maxSize; j++） {
  140.    
  141.     long n = （int）（java.lang.Math.random（）*99）；
  142.    
  143.     arr.insert（n）；
  144.    
  145.     }
  146.    
  147.     arr.display（）；
  148.    
  149.     arr.quickSort（）；
  150.    
  151.     arr.display（）；
  152.    
  153.     }
  154.    
  155.     }
  156. //java/4486

回复 "java版快速排序法"

这儿你可以回复上面这条便签

captcha

贴代码片段 - Code666