スタックソートJavaコード実装

ヒープのソート
ヒープソート(Heapsort)とは、ヒープというデータ構造を用いて設計されたソートアルゴリズムのことである.スタックは、完全なツリーに近い構造であり、スタックの性質を満たすと同時に、サブノードのキー値またはインデックスが親ノードよりも常に小さい(または大きい)ということである.
アルゴリズムの説明

初期並べ替え対象キーワードシーケンス(R 1,R 2.....Rn)を、初期の無秩序領域である大きなトップスタックに構築する.

スタックトップ要素R[1]を最後の要素R[n]と交換すると、新しい無秩序領域(R 1,R 2,......Rn−1)と新しい秩序領域(Rn)が得られ、R[1,2...n−1]<=R[n]を満たす.

交換後の新しいスタックトップR[1]はスタックの性質に反する可能性があるため、現在の無秩序領域(R 1,R 2,......Rn−1)を新しいスタックに調整し、再びR[1]を無秩序領域の最後の要素と交換し、新しい無秩序領域(R 1,R 2....Rn−2)と新しい秩序領域(Rn−1,Rn)を得る必要がある.秩序領域の要素個数がn−1になるまで、このプロセスを繰り返し、ソートプロセス全体が完了する.

アルゴリズム解析

時間の複雑さ:

最適:T(n)=O(nlogn)

最悪:T(n)=O(nlogn)

平均:T(n)=O(nlogn)

空間複雑度:O(1)

安定性:不安定

コード実装

public class HeapSort {
    public static void heapSort(int[] arr) {
        if (arr == null || arr.length <= 1) return;
        //   。
        buildHeap(arr);
        int len = arr.length;
        while (len > 1) {
            //             。
            swap(arr, 0, len - 1);
            //      ，           。
            len--;
            //         。
            heapfy(arr, 0 , len);

            //               。
            print(arr);
        }
    }

    private static void buildHeap(int[] arr) {
        //          ：2i + 1 >= arr.length  -->  i >= (arr.length - 1) / 2
        for (int i = (arr.length - 1) / 2 - 1; i >= 0; i--) {
            heapfy(arr, i, arr.length);
        }
    }

    //       ，     。
    private static void heapfy(int[] arr, int i, int len) {
        while (true) {
            int maxPostion = i;
            int leftChild = 2 * i + 1;  //      。
            int rightChild = 2 * i + 2; //      。

            //          ，      。
            if (leftChild < len && arr[leftChild] > arr[maxPostion]) {
                maxPostion = leftChild;
            }

            //          ，      。
            if (rightChild < len && arr[rightChild] > arr[maxPostion]) {
                maxPostion = rightChild;
            }

            if (maxPostion == i) {
                break;  //         ，     。
            } else {
                swap(arr, i, maxPostion);   //       ，     。
                i = maxPostion;
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] =temp;
    }

    public static void main(String[] args) {
        int[] arr = {6, 9, 1, 4, 5, 8, 7, 0, 2, 3};

        System.out.print("   :  ");
        print(arr);

        heapSort(arr);

        System.out.print("   :  ");
        print(arr);
    }

    //     
    public static void print(int[] arr) {
        if (arr == null)    return;

        for(int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}
/*
   :  6 9 1 4 5 8 7 0 2 3 
8 6 7 4 5 1 3 0 2 9 
7 6 3 4 5 1 2 0 8 9 
6 5 3 4 0 1 2 7 8 9 
5 4 3 2 0 1 6 7 8 9 
4 2 3 1 0 5 6 7 8 9 
3 2 0 1 4 5 6 7 8 9 
2 1 0 3 4 5 6 7 8 9 
1 0 2 3 4 5 6 7 8 9 
0 1 2 3 4 5 6 7 8 9 
   :  0 1 2 3 4 5 6 7 8 9 
*/