basicsort.java~5~

数据结构综合实验,有各种排序算法和计算排序时间,最短路径算法,huffman编码解码.用图形界面实现.在jbuilder2006下运行通过.

package datas2;

public class Basicsort {
    private int[] array;
    public  Basicsort(int max)
    {
        array = new int[max];
        for (int i = 0; i < array.length; i++)
        {
            array[i] = (int)(java.lang.Math.random()*max);
        }
    }
    //插入排序
    public int[] insertsort()
    {
        int temp;
        int i, j;
        for(i = 1; i < array.length; i++ )
        {
            temp = array[i];
            for(j = i; j > 0 && temp < array[j - 1]; j--)
                array[j] = array[j - 1];
            array[j] = temp;
        }
        return array;
    }
    //冒泡排序
    public int[]  bubblesort()
    {
            int i,j;
            for(i = 0; i < array.length; i++)
                    for(j = array.length - 1; j > i; j--)
                            if(array[j] < array[j - 1])
                            swap(array,j,j-1);
            return array;
    }

    public static void swap(int[] a, int e1, int e2)
    {
            int temp = a[e1];
            a[e1] = a[e2];
            a[e2] = temp;
    }
    //选择排序
    public int[] selectionsort()
    {
            int i,j;
            int l = 0;
            for(i = 0; i < array.length; i++)
            {
                    for(j = i + 1; j < array.length; j++)
                            if(array[j] < array[l])
                                    l = j;
                    swap(array,l,i);
            }
            return array;
    }
    //希尔排序
    //--------------------------------------------------------------
       public int[] shellSort()
          {
          int inner, outer;
          int temp;
            //间隔h
          int h = 1;                     // find initial value of h
          while(h <= array.length/3)
             h = h*3 + 1;                // (1, 4, 13, 40, 121, ...)

          while(h>0)                     // decreasing h, until h=1
             {
                                         // h-sort the file
             for(outer=h; outer<array.length; outer++)
                {
                temp = array[outer];
                inner = outer;
                                         // one subpass (eg 0, 4, 8)
                while(inner > h-1 && array[inner-h] >=  temp)
                   {
                   array[inner] = array[inner-h];
                   inner -= h;
                   }
                array[inner] = temp;
                }   // end for
                //display();//打印出每次的排序结果
             h = (h-1) / 3;              // decrease h
             }
           return array;  // end while(h>0)
      }  // end shellSort()

      //归并排序///////////////////////////////////////////
      public int[] mergeSort()           // called by main()
         {                              // provides workspace
         int[] workSpace = new int[array.length];
         recMergeSort(workSpace, 0, array.length-1);
         return array;
         }
      //-------------------------------------------------
      public  void recMergeSort(int[] workSpace, int lowerBound,
                                                  int upperBound)
         {
         if(lowerBound == upperBound)            // if range is 1,
            return;                              // no use sorting
         else
            {                                    // find midpoint
            int mid = (lowerBound+upperBound) / 2;
                                                 // sort low half
            recMergeSort(workSpace, lowerBound, mid);
                                                 // sort high half
            recMergeSort(workSpace, mid+1, upperBound);
                                                 // merge them
            merge(workSpace, lowerBound, mid+1, upperBound);
            }  // end else
      }  // end recMergeSort()
      //---------------------------------------------------------------
      private void merge(int[] workSpace, int lowPtr,
                              int highPtr, int upperBound)
         {
         int j = 0;                             // workspace index
         int lowerBound = lowPtr;
         int mid = highPtr-1;
         int n = upperBound-lowerBound+1;       // # of items

         while(lowPtr <= mid && highPtr <= upperBound)
            if( array[lowPtr] < array[highPtr] )
               workSpace[j++] = array[lowPtr++];
            else
               workSpace[j++] = array[highPtr++];

         while(lowPtr <= mid)
            workSpace[j++] = array[lowPtr++];

         while(highPtr <= upperBound)
            workSpace[j++] = array[highPtr++];

         for(j=0; j<n; j++)
            array[lowerBound+j] = workSpace[j];
      }
}