谁能写一个干净的快速排序的方法阿 thanks

Question

谁能写一个干净的快速排序的方法阿。就一个方法。方法里面对一个int数组排序。我在网络上找了半天都是互相抄袭。而且很多运行不出来

Answer 1

import java.util.Arrays;public class Test {    public static void main(String [] argc) {
        int [] test = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0};        Arrays.sort(test);        for(int i = 0 ; i < test.length; i ++) {
            System.out.println(test[i]);
        }
    }   
}明明一句话就能解决的事情，需要去写个算法么？

Answer 2

import java.util.*;
public class wo{

public static void main(String arg[]){ 
int[] a=new int[10];
Random r=new Random();
for(int i=0;i<a.length;i++)
{
a[i]=r.nextInt(100);
}
wo.QSort(a, 0, a.length-1);
for(int i=0;i<a.length;i++)
System.out.print(a[i]+" ");
} 
static int Partition(int[] a,int low,int high)
{
int key=a[low];
while(low<high)
{
while(low<high&&a[high]>=key)
--high;
a[low]=a[high];
while(low<high&&a[low]<=key)
++low;
a[high]=a[low];
}
a[low]=key;
return low;
}
static void QSort(int[] a,int low,int high)
{
int m;
if(low<high)
{
m=wo.Partition(a, low, high);
wo.QSort(a, low, m-1);
wo.QSort(a, m+1, high);
}
}
}
自己写的,试试

Answer 3

wangzhiqing(妄想分别执着) ( ) 信誉：104    Blog  2007-02-27 17:48:01  得分: 0  支持

Answer 4

class QuickSort 
{
public static void main(String[] args) 
{
int [] ints = {5, 4, 9, 3, 8, 2};
Sort(ints, 0, ints.length - 1); for (int i = 0; i < ints.length; i ++)
{
System.out.print(" " + ints[i]);
}
} public static void Sort(int[] arr, int begin, int end)
{
if ( begin < end)
{
int middle = begin;
for ( int i = begin + 1; i <= end ; i ++)
{ // middle will always point to the first of bigs that i meet. // even next small will make the middle point to the second
// but by this time, Swap happens, so, middle be its way again. if (arr[i] < arr[begin] && ++middle != i)
{
Swap(arr, i, middle);
}
} Swap(arr, begin, middle);
Sort(arr, begin, middle-1);
Sort(arr, middle+1, end);
}
} public static void Swap(int[]arr, int i, int j)
{
int val = arr[i];
arr[i] = arr[j];
arr[j] = val;
}
}

Answer 5

有个问题修正一下，那个middle指向的是大数的前面那个小数。
当if条件成立的时候，才指向第一个大数，然后交换发生。然后指向小数

Answer 6

class ArrayIns
   {
   private long[] theArray;          // ref to array theArray
   private int nElems;               // number of data items
//--------------------------------------------------------------
   public ArrayIns(int max)          // constructor
      {
      theArray = new long[max];      // create the array
      nElems = 0;                    // no items yet
      }
//--------------------------------------------------------------
   public void insert(long value)    // put element into array
      {
      theArray[nElems] = value;      // insert it
      nElems++;                      // increment size
      }
//--------------------------------------------------------------
   public void display()             // displays array contents
      {
      System.out.print("A=");
      for(int j=0; j<nElems; j++)    // for each element,
         System.out.print(theArray[j] + " ");  // display it
      System.out.println("");
      }
//--------------------------------------------------------------
   public void quickSort()
      {
      recQuickSort(0, nElems-1);
      }
//--------------------------------------------------------------
   public void recQuickSort(int left, int right)
      {
      if(right-left <= 0)              // if size <= 1,
          return;                      //    already sorted
      else                             // size is 2 or larger
         {
         long pivot = theArray[right];      // rightmost item
                                            // partition range
         int partition = partitionIt(left, right, pivot);
         recQuickSort(left, partition-1);   // sort left side
         recQuickSort(partition+1, right);  // sort right side
         }
      }  // end recQuickSort()
//--------------------------------------------------------------
    public int partitionIt(int left, int right, long pivot)
       {
       int leftPtr = left-1;           // left    (after ++)
       int rightPtr = right;           // right-1 (after --)
       while(true)
          {                            // find bigger item
          while( theArray[++leftPtr] < pivot )
             ;  // (nop)
                                       // find smaller item
          while(rightPtr > 0 && theArray[--rightPtr] > pivot)
             ;  // (nop)          if(leftPtr >= rightPtr)      // if pointers cross,
             break;                    //    partition done
          else                         // not crossed, so
             swap(leftPtr, rightPtr);  //    swap elements
          }  // end while(true)
       swap(leftPtr, right);           // restore pivot
       return leftPtr;                 // return pivot location
       }  // end partitionIt()
//--------------------------------------------------------------
   public void swap(int dex1, int dex2)  // swap two elements
      {
      long temp = theArray[dex1];        // A into temp
      theArray[dex1] = theArray[dex2];   // B into A
      theArray[dex2] = temp;             // temp into B
      }  // end swap(
//--------------------------------------------------------------
   }  // end class ArrayIns
////////////////////////////////////////////////////////////////
class QuickSort1App
   {
   public static void main(String[] args)
      {
      int maxSize = 16;             // array size
      ArrayIns arr;
      arr = new ArrayIns(maxSize);  // create array      for(int j=0; j<maxSize; j++)  // fill array with
         {                          // random numbers
         long n = (int)(java.lang.Math.random()*99);
         arr.insert(n);
         }
      arr.display();                // display items
      arr.quickSort();              // quicksort them
      arr.display();                // display them again
      }  // end main()
   }  
这个程序是最基础的,教材上的经典

Answer 7

为什么不用 Arrays.sort()？？
 顶一下

Answer 8

Arrays.sort()
这个最干净！！！

Answer 9

大家不要鄙视lz了，lz想做的也仅仅是知道一下快速排序的原理。或者lz要参加某个公司的笔试，要求不用java的collection系列的api写出快速排序的算法。hoho 

Answer 10

想做的也仅仅是知道一下快速排序的原理。或者lz要参加某个公司的笔试，要求不用java的collection系列的api写出快速排序的算法。hoho 

Answer 11

想做的也仅仅是知道一下快速排序的原理。或者lz要参加某个公司的笔试，要求不用java的collection系列的api写出快速排序的算法。hoho 
============================看来这么多人还是我最有见定。

Answer 12

给你一个网址，绝对有你要的，很容易找。
良葛格（林信良）写的。
http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/AlgorithmGossip.htm

Answer 13

楼主可以参考下这个，用递归实现，思路非常清晰：public class QuickSort{
public static void quickSort(int[] a, int low, int high){
int i, j;
int temp; i = low;
j = high;
temp = a[low];  //取第一个元素为标准数据元素 while(i < j){
//在数组的右端扫描
while(i < j && temp <= a[j]) j--;
if(i < j){
a[i] = a[j];
i++;
} //在数组的左端扫描
while(i < j && a[i] < temp) i++;
if(i < j){
a[j] = a[i];
j--;
}
}
a[i] = temp;

if(low < i) quickSort(a, low, i-1);  //对左端子集合递归
if(i < high) quickSort(a, j+1, high);  //对右端子集合递归
}

public static void main(String[] args){
int[] test = {60,55,48,37,10,90,84,36};
int n = 8;

quickSort(test, 0, 7);
for(int i = 0; i < n; i++)
System.out.print(test[i] + "  ");
}
}