请高手看看问题出在哪里？

我想实现一下“最优算法”的排序：把随即的100个数按升序排列.代码如下：
（ps:不考虑资源 浪费问题，只是想实现一下算法，当然有更好的，发个看看啊~~）
import java.util.*;
public class SimperTest 
{
static int cunt;
static boolean boo;
public void chang(LinkedList ll,LinkedList ll2,int indexA,int indexB) throws Exception
{
int a=(Integer) ll.get(indexA);
int b=(Integer) ll.get(indexB);
boo=true;
if(a>b)
{
ll.set(indexB, a);
ll.set(indexA, b);
cunt++;
}
else if(a<b)
{
ll.offer(ll.remove(indexB));
}else
{
boo=false;
ll2.add(ll.remove(indexB));
}
}
public void fn(LinkedList ll,int firstIndex,int lastIndex)throws Exception
{
LinkedList ll2=new LinkedList();
cunt=0;
//for(int i=firstIndex+1;i<=lastIndex;i+=(ll2.size()+1)){
int i=firstIndex+1;
do
{
chang(ll,ll2,firstIndex+cunt,i);
if(boo)
{
i++;
}
}while (i<ll.size());
int subcunt=firstIndex+cunt;
ll.addAll(subcunt,ll2);
int n=ll2.size();
if((subcunt-1)>firstIndex&&(lastIndex-subcunt-1)>n)
{
fn(ll,firstIndex,subcunt-1);
fn(ll,subcunt+n+1,lastIndex);
}
else if((subcunt-1)==firstIndex&&(lastIndex-subcunt-1)>n)
{
fn(ll,subcunt+n+1,lastIndex);
}
else if((subcunt-1)>firstIndex&&(lastIndex-subcunt-1)==n)
{
fn(ll,firstIndex,subcunt-1);
}
}
/**
 * @param args
 */
public static void main(String[] args)throws Exception
{
// TODO Auto-generated method stub
LinkedList ll=new LinkedList();
for(int i=0;i<=99;i++)
{
ll.add(new Integer((int)(100*Math.random())));
}
System.out.println("size="+ll.size());
SimperTest st=new SimperTest();
st.fn(ll,0, 99);
for(int i=0;i<100;i++)
{
System.out.print(ll.get(i).toString()+"\t");
if((i+1)%10==0)
{
System.out.println("");
}
}
}}
结果就是是不对~~郁闷中，高手帮忙看看改改！！

解决方案 »

  1.   

    没时间了，网上找了几种，自己研究吧
    转自 http://blog.pfan.cn/lovemm插入排序:package org.rut.util.algorithm.support;import org.rut.util.algorithm.SortUtil;
    /**
     * @author treeroot
     * @since 2006-2-2
     * @version 1.0
     */
    public class InsertSort implements SortUtil.Sort{    /* (non-Javadoc)
         * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
         */
        public void sort(int[] data) {
            int temp;
            for(int i=1;i<data.length;i++){
                for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){
                    SortUtil.swap(data,j,j-1);
                }
            }        
        }}
    冒泡排序:package org.rut.util.algorithm.support;import org.rut.util.algorithm.SortUtil;/**
     * @author treeroot
     * @since 2006-2-2
     * @version 1.0
     */
    public class BubbleSort implements SortUtil.Sort{    /* (non-Javadoc)
         * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
         */
        public void sort(int[] data) {
            int temp;
            for(int i=0;i<data.length;i++){
                for(int j=data.length-1;j>i;j--){
                    if(data[j]<data[j-1]){
                        SortUtil.swap(data,j,j-1);
                    }
                }
            }
        }}选择排序:package org.rut.util.algorithm.support;import org.rut.util.algorithm.SortUtil;/**
     * @author treeroot
     * @since 2006-2-2
     * @version 1.0
     */
    public class SelectionSort implements SortUtil.Sort {    /*
         * (non-Javadoc)
         * 
         * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
         */
        public void sort(int[] data) {
            int temp;
            for (int i = 0; i < data.length; i++) {
                int lowIndex = i;
                for (int j = data.length - 1; j > i; j--) {
                    if (data[j] < data[lowIndex]) {
                        lowIndex = j;
                    }
                }
                SortUtil.swap(data,i,lowIndex);
            }
        }}快速排序:package org.rut.util.algorithm.support;import org.rut.util.algorithm.SortUtil;/**
     * @author treeroot
     * @since 2006-2-2
     * @version 1.0
     */
    public class QuickSort implements SortUtil.Sort{    /* (non-Javadoc)
         * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
         */
        public void sort(int[] data) {
            quickSort(data,0,data.length-1);        
        }
        private void quickSort(int[] data,int i,int j){
            int pivotIndex=(i+j)/2;
            //swap
            SortUtil.swap(data,pivotIndex,j);
            
            int k=partition(data,i-1,j,data[j]);
            SortUtil.swap(data,k,j);
            if((k-i)>1) quickSort(data,i,k-1);
            if((j-k)>1) quickSort(data,k+1,j);
            
        }
        /**
         * @param data
         * @param i
         * @param j
         * @return
         */
        private int partition(int[] data, int l, int r,int pivot) {
            do{
               while(data[++l]<pivot);
               while((r!=0)&&data[--r]>pivot);
               SortUtil.swap(data,l,r);
            }
            while(l<r);
            SortUtil.swap(data,l,r);        
            return l;
        }}
    改进后的快速排序:package org.rut.util.algorithm.support;import org.rut.util.algorithm.SortUtil;/**
     * @author treeroot
     * @since 2006-2-2
     * @version 1.0
     */
    public class ImprovedQuickSort implements SortUtil.Sort {    private static int MAX_STACK_SIZE=4096;
        private static int THRESHOLD=10;
        /* (non-Javadoc)
         * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
         */
        public void sort(int[] data) {
            int[] stack=new int[MAX_STACK_SIZE];
            
            int top=-1;
            int pivot;
            int pivotIndex,l,r;
            
            stack[++top]=0;
            stack[++top]=data.length-1;
            
            while(top>0){
                int j=stack[top--];
                int i=stack[top--];
                
                pivotIndex=(i+j)/2;
                pivot=data[pivotIndex];
                
                SortUtil.swap(data,pivotIndex,j);
                
                //partition
                l=i-1;
                r=j;
                do{
                    while(data[++l]<pivot);
                    while((r!=0)&&(data[--r]>pivot));
                    SortUtil.swap(data,l,r);
                }
                while(l<r);
                SortUtil.swap(data,l,r);
                SortUtil.swap(data,l,j);
                
                if((l-i)>THRESHOLD){
                    stack[++top]=i;
                    stack[++top]=l-1;
                }
                if((j-l)>THRESHOLD){
                    stack[++top]=l+1;
                    stack[++top]=j;
                }
                
            }
            //new InsertSort().sort(data);
            insertSort(data);
        }
        /**
         * @param data
         */
        private void insertSort(int[] data) {
            int temp;
            for(int i=1;i<data.length;i++){
                for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){
                    SortUtil.swap(data,j,j-1);
                }
            }       
        }}归并排序:package org.rut.util.algorithm.support;import org.rut.util.algorithm.SortUtil;/**
     * @author treeroot
     * @since 2006-2-2
     * @version 1.0
     */
    public class MergeSort implements SortUtil.Sort{    /* (non-Javadoc)
         * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
         */
        public void sort(int[] data) {
            int[] temp=new int[data.length];
            mergeSort(data,temp,0,data.length-1);
        }
        
        private void mergeSort(int[] data,int[] temp,int l,int r){
            int mid=(l+r)/2;
            if(l==r) return ;
            mergeSort(data,temp,l,mid);
            mergeSort(data,temp,mid+1,r);
            for(int i=l;i<=r;i++){
                temp[i]=data[i];
            }
            int i1=l;
            int i2=mid+1;
            for(int cur=l;cur<=r;cur++){
                if(i1==mid+1)
                    data[cur]=temp[i2++];
                else if(i2>r)
                    data[cur]=temp[i1++];
                else if(temp[i1]<temp[i2])
                    data[cur]=temp[i1++];
                else
                    data[cur]=temp[i2++];            
            }
        }}改进后的归并排序:package org.rut.util.algorithm.support;import org.rut.util.algorithm.SortUtil;/**
     * @author treeroot
     * @since 2006-2-2
     * @version 1.0
     */
    public class ImprovedMergeSort implements SortUtil.Sort {    private static final int THRESHOLD = 10;    /*
         * (non-Javadoc)
         * 
         * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
         */
        public void sort(int[] data) {
            int[] temp=new int[data.length];
            mergeSort(data,temp,0,data.length-1);
        }    private void mergeSort(int[] data, int[] temp, int l, int r) {
            int i, j, k;
            int mid = (l + r) / 2;
            if (l == r)
                return;
            if ((mid - l) >= THRESHOLD)
                mergeSort(data, temp, l, mid);
            else
                insertSort(data, l, mid - l + 1);
            if ((r - mid) > THRESHOLD)
                mergeSort(data, temp, mid + 1, r);
            else
                insertSort(data, mid + 1, r - mid);        for (i = l; i <= mid; i++) {
                temp[i] = data[i];
            }
            for (j = 1; j <= r - mid; j++) {
                temp[r - j + 1] = data[j + mid];
            }
            int a = temp[l];
            int b = temp[r];
            for (i = l, j = r, k = l; k <= r; k++) {
                if (a < b) {
                    data[k] = temp[i++];
                    a = temp[i];
                } else {
                    data[k] = temp[j--];
                    b = temp[j];
                }
            }
        }    /**
         * @param data
         * @param l
         * @param i
         */
        private void insertSort(int[] data, int start, int len) {
            for(int i=start+1;i<start+len;i++){
                for(int j=i;(j>start) && data[j]<data[j-1];j--){
                    SortUtil.swap(data,j,j-1);
                }
            }
        }}
      

  2.   

    5楼的还没研究，不过先要谢谢kingssman！
    我说下我的思路（新手，别嘲笑，哈）
    实际上我就是想重写下sort方法的当然我知道我的方法比真正的方法差了不知道多少倍；
    先说下我的思路：要排序一个数组，先随便找出一个数（我选第一个），逐个比较，如果小于它则
    归为“左边”大于或等于归于“右边”这样递归下去，最后的结果就是“左边”加“第一个数”加“右边”。
    我用的是LinkedList；chang()方法是为了比较两个数，然后排序：当小于“第一个数”则两个数位置互换；
    当大于“第一个数”则把被比较的数移到到linkedlist的尾部。若等于“第一个数”则移到新的linkedlist中。
    在后面的fn（）方法中再用addAll（）方法插入.
    后面的fn()方法应该很简单了吧，我觉得问题主要就出在这里，但是就是找不出来~~~
      

  3.   


    没有看明白楼主的排序方法，可以这么实现import java.util.*;
    public class SimperTest 
    {

         //冒泡排序  
         public LinkedList paiXu(LinkedList l1)  
         {  
            for(int i=0;i<l1.size();i++)
            {
                for(int j=l1.size()-1;j>i;j--)
                {
                int a=(Integer)l1.get(i);
             int b=(Integer)l1.get(j); 
           
            if(a>b)
            {
                l1.set(j, a);
                l1.set(i, b);
                
            }                       
                    
                }
            }
            return l1;
        
       }
        /**
         * @param args
         */
        public static void main(String[] args)throws Exception
        {
            // TODO Auto-generated method stub
            LinkedList ll=new LinkedList();
            for(int i=0;i<=99;i++)
            {
                ll.add(new Integer((int)(100*Math.random())));
            }
            System.out.println("size="+ll.size());
            System.out.println("排序前");
            for(int i=0;i<100;i++)
            {
                System.out.print(ll.get(i).toString()+"\t");
                if((i+1)%10==0)
                {
                    System.out.println("");
                }
            }
            SimperTest st=new SimperTest();
            st.paiXu(ll);
            System.out.println("排序后");
            for(int i=0;i<100;i++)
            {
                System.out.print(ll.get(i).toString()+"\t");
                if((i+1)%10==0)
                {
                    System.out.println("");
                }
            }
        }}
      

  4.   

    哦，sorry,排序法不是冒泡排序，整错了
      

  5.   

    Arrays.sort(数组)，直接就可排序了，嘿嘿，偷工减料的做法