内部並べ替え

暇があっても大丈夫です.データ構造の内部並べ替えを復習して、午後の時間を利用して、適当に選択、快速並べ替え、内部並べ替えの実現を書きました.ここにコードを貼り付けます.自分の連絡先として使うだけです.
      

public class Program {



    public static void main(String[] args) {

        // TODO Auto-generated method stub

          

           int[] array = CreateRandomArray(20);

           Display(array);

           SelectSortClass.Sort(array);

           Display(array);

           QuickSortClass.Sort(array);

           Display(array);

           HeapSortClass.Sort(array);

           Display(array);

    }

    

    

    private static int[] CreateRandomArray(int n)

    {

        int[] array = new int[n];

        Random rnd = new Random();

        for(int i = 0;i<n;i++)

        {

            array[i] = rnd.nextInt(n*10);

        }

        return array;

    }

    

    private static void Display(int[] array)

    {

        for(int i =0;i<array.length;i++)

        {

            System.out.print(array[i] + "  ");

        }

        System.out.println();

        

    }

    

}

並べ替えを選択すると次のようになります.

public class SelectSortClass

{

       public static void Sort(int[] array)

    {

        for(int i = 0;i < array.length;i++)

        {

            int minIndex = i;

            for(int j = i +1;j<array.length;j++)

            {

                 if(array[minIndex] > array[j])

                       minIndex = j ;

            }

            if(minIndex != i)

            Swap(array,minIndex,i);

        }

    }



    private static void Swap(int[] array,int m,int n)

    {

         int temp = array[m];

         array[m] = array[n];

         array[n] = temp;

    }



}

クイックソートの実現は以下の通りです.

public class QuickSortClass 

{



    /**

     *     

     * @param array

     * @param left

     * @param right

     */

    public static void Sort(int[] array)

    {

        QuickSort(array,0,array.length -1);

    }

    

    private static void QuickSort(int[] array,int left,int right)

    {

        if(left<right)

        {

            int partion = Division(array,left,right);

            QuickSort(array,left,partion-1);

            QuickSort(array,partion +1 ,right);

        }

        

    }

    

    private static int Division(int[] array,int left,int right)

    {

        int temp = array[left];

        while(left < right)

        {

            while(left < right && temp <= array[right])

                right--;

            array[left] = array[right];

            while(left < right && temp >= array[left])

                left++;

            array[right] = array[left];

        }

        array[left] = temp;

        return left;

    }

}

積み上げ順序の実現は以下の通りである.

public class HeapSortClass {



    /**

     *    

     * @param array

     */

    public static void Sort(int[] array)

    {

        BuildMaxHeap(array); //     

        for(int i = array.length - 1;i>=0;i--)

        {

            Swap(array,0,i);//        ，       

            MaxHeapUpdate(array,0,i);// i        

        }

    }

    

    private static void BuildMaxHeap(int[] array)

    {

           for(int i = (array.length / 2) -1; i >= 0; i--)

           {

               MaxHeapUpdate(array,i,array.length);

           }

    }

    

    private static void MaxHeapUpdate(int[] array ,int i,int heapSize)

    {

        int left = i* 2;

        int right = i* 2 +1;

        int max = i;

        if(right < heapSize)

        {

             if(array[left] >= array[right])

             {

                 if(array[left] > array[i])

                     max = left;

             }

             else

             {

                 if(array[right] > array[i])

                     max = right;

             }

        }

        if(max != i)

        {

            Swap(array,max,i);

            MaxHeapUpdate(array,max,heapSize);

        }

    }

    

    private static void Swap(int[] array,int m,int n)

    {

         int temp = array[m];

         array[m] = array[n];

         array[n] = temp;

    }

    

}