basicsort.java

数据结构综合实验,有各种排序算法和计算排序时间,最短路径算法,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];
      }

      ////////////////////////基数排序//////////////////////////////
    public int[] binsort(int[] b,int n, int k, int r, int[] cnt)
    {	//k是最大的数的位数;r是进制;cnt相应桶的大小;返回的结果a;临时数组b;n是要排序的个数
      int j;
      for(int i = 0, rtok = 1; i < k; i ++, rtok *=r)
       {
        for(j = 0; j < r; j ++)
            cnt[j] = 0;
        for(j = 0; j < n; j ++)
            cnt[(array[j] / rtok) % r] ++;
        for(j = 1; j < r; j ++)
            cnt[j] = cnt[j - 1] + cnt[j];
        for(j = n - 1; j >= 0; j --)
            b[-- cnt[(array[j] / rtok) % r]] = array[j];
        for(j = 0; j < n; j ++)
            array[j] = b[j];

       }
       return array;
      }

      //////////////////////////////////////////////////////////////
      ///////////////快速排序/////////////////////////////////////////
      public int[] quickSort()
         {
         recQuickSort(0, array.length-1);
         // insertionSort(0, nElems-1); // the other option
         return array;
      }
      //-------------------------------------------------------------
      public void recQuickSort(int left, int right)
            {
            int size = right-left+1;
            if(size < 10)                   // insertion sort if small
               insertionSort(left, right);
            else                            // quicksort if large
               {
               long median = medianOf3(left, right);
               int partition = partitionIt(left, right, median);
               recQuickSort(left, partition-1);
               recQuickSort(partition+1, right);
               }
      }  // end recQui
      //-------------------------------------------------------------
      public long medianOf3(int left, int right)
         {
         int center = (left+right)/2;
                                          // order left & center
         if( array[left] > array[center] )
            swap(left, center);
                                          // order left & right
         if( array[left] > array[right] )
            swap(left, right);
                                          // order center & right
         if( array[center] > array[right] )
            swap(center, right);

         swap(center, right-1);           // put pivot on right
         return array[right-1];        // return median value
         }  // end medianOf3()
//--------------------------------------------------------------
      public void swap(int dex1, int dex2)  // swap two elements
         {
         int temp = array[dex1];        // A into temp
         array[dex1] = array[dex2];   // B into A
         array[dex2] = temp;             // temp into B
         }  // end swap(
//--------------------------------------------------------------
       public int partitionIt(int left, int right, long pivot)
          {
          int leftPtr = left;             // right of first elem
          int rightPtr = right - 1;       // left of pivot
          while(true)
             {
             while( array[++leftPtr] < pivot )  // find bigger
                ;                                  // (nop)
             while( array[--rightPtr] > pivot ) // find smaller
                ;                                  // (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-1);         // restore pivot
          return leftPtr;                 // return pivot location
          }  // end partitionIt()
//--------------------------------------------------------------
                                          // insertion sort
      public void insertionSort(int left, int right)
         {
         int in, out;
                                          //  sorted on left of out
         for(out=left+1; out<=right; out++)
            {
            int temp = array[out];    // remove marked item
            in = out;                     // start shifts at out
                                          // until one is smaller,
            while(in>left && array[in-1] >= temp)
               {
               array[in] = array[in-1]; // shift item to right
               --in;                      // go left one position
               }
            array[in] = temp;          // insert marked item
            }  // end for
      }
      /////////////////////////////////////////////////////////////
      ///////////////////堆排序/////////////////////////////////////

}