• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

java版快速排序法

JAVA相关 水墨上仙 3059次浏览

java版快速排序法

 /*
    
    * 快速排序是最流行的排序算法,本质上通过把一个数组划分为两个子数组,
    
    * 然后递归地调用自身为每一个子数组进行快速排序来实现。
    
    * ArrayIns.java
    
    * linzhanghui@gmail.com
    
    */
    
    package linzhanghui.quicksort;
    
    public class ArrayIns {
    
    private long[] theArray;
    
    private int nElems;
    
    public ArrayIns(int max) {
    
    theArray = new long[max];
    
    nElems = 0;
    
    }
    
    public void insert(long value) {
    
    theArray[nElems] = value;
    
    nElems++;
    
    }
    
    public void display() {
    
    System.out.print("A=");
    
    for(int j=0; j<nElems; j++)
    
    System.out.print(theArray[j] + " ");
    
    System.out.println("");
    
    }
    
    public void quickSort() {
    
    recQuickSort(0, nElems-1);
    
    }
    
    public void recQuickSort(int left, int right) {
    
    if(right-left <= 0)
    
    return;
    
    else {
    
    long pivot = theArray[right];
    
    int partition = partitionIt(left, right, pivot);
    
    recQuickSort(left, partition-1);
    
    recQuickSort(partition+1, right);
    
    }
    
    }
    
    public int partitionIt(int left, int right, long pivot) {
    
    int leftPtr = left-1;
    
    int rightPtr = right;
    
    while(true) {
    
    while( theArray[++leftPtr] < pivot)
    
    ;
    
    while(rightPtr > 0 && theArray[--rightPtr] > pivot)
    
    ;
    
    if(leftPtr >= rightPtr)
    
    break;
    
    else
    
    swap(leftPtr, rightPtr);
    
    }
    
    swap(leftPtr, right);
    
    return leftPtr;
    
    }
    
    public void swap(int dex1, int dex2) {
    
    long temp = theArray[dex1];
    
    theArray[dex1] = theArray[dex2];
    
    theArray[dex2] = temp;
    
    }
    
    }
    
    /*
    
    * 程序随机产生16个2位随机数,显示这16个随机数后,对其进行快速排序并输出。
    
    * linzhanghui@gmail.com
    
    */
    
    package linzhanghui.quicksort;
    
    public class QuickSortApp {
    
    public static void main(String[] args) {
    
    int maxSize = 16;
    
    ArrayIns arr;
    
    arr = new ArrayIns(maxSize);
    
    for(int j=0; j<maxSize; j++) {
    
    long n = (int)(java.lang.Math.random()*99);
    
    arr.insert(n);
    
    }
    
    arr.display();
    
    arr.quickSort();
    
    arr.display();
    
    }
    
    }


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明java版快速排序法
喜欢 (0)
加载中……