Javaデータ構造とアルゴリズム--(59)スタックソート

スタック並べ替えの時間的複雑さはO(nlogn)である.
一、コード

package tree;

import java.util.Arrays;
/**
 *    
 * 1.               （    ，    ）。  ，                。
 * 2.            ，         。
 * 3.      n-1           （    ，    ），     n       。      ，           。
 * @author Lee
 *
 */
public class HeapSort {
	/**
	 *   
	 * 1.      。               （         ，       )。
	 * 2.               ，       。
	 * 3.        （    ，    ），             ，       。        、  、  。
	 * @param args
	 */
	
	//  
	// 1.            ，                 。
	// 2.             ，     " "     。
	// 3.       ，          ，                 ，      +    ，        。
	
	public static void main(String[] args) {
		//            ，       
		int[] arr = {4, 6, 8, 5, 9, 10, -2, 9, 25, 62};
		System.out.println("    ：" + Arrays.toString(arr));
		heapSort(arr);
		System.out.println("    ：" + Arrays.toString(arr));
	}
	
	//  ：   
	public static void heapSort(int[] arr) {
		System.out.println("--------------------        --------------------");
		
		/*
		//    
		//           
		adjustHeap(arr, 1, arr.length);
		System.out.println("           " + Arrays.toString(arr));
		//            
		adjustHeap(arr, 0, arr.length);
		System.out.println("            " + Arrays.toString(arr));
		//             ，       
		*/
		
		
		// 1.      。           ，                 。
		/*
		 *   ：
		 * 1.         ，                  （arr.length / 2 - 1）   ，      ，      
		 * 2.    for      ，                 ，   arr[0]    
		 */
		for(int i = arr.length / 2 - 1; i >= 0; i--) {
			adjustHeap(arr, i, arr.length);
		}
		
		// 2.       arr[0]       arr[arr.length - 1]   ，     " "       +       ，          
		//      ：j                 
		for(int j = arr.length - 1; j > 0; j--) {
			// 1.   
			//   ：            ，arr[0]              
			int temp = arr[j];
			arr[j] = arr[0];
			arr[0] = temp;
			
			//2.     
			//     ：                  i    0   ，  i                
			adjustHeap(arr, 0, j);
		}
	}
	
	//  ：             
	/**
	 *   ：     i           ，      。i                
	 *   ：int[] arr = {4, 6, 8, 5, 9} => i = 1 => adjustHeap(arr, i, arr.length) => arr = {4, 9, 8, 5, 6}
	 *             adjustHeap，     i = 0 => ，arr = {4, 9, 8, 5, 6} => arr = {9, 6, 8, 5, 4}（   ）
	 * @param arr       
	 * @param i            （  ）
	 * @param length         ，             ，length       
	 */
	public static void adjustHeap(int[] arr, int i, int length) {
		
		int temp = arr[i];//         ，       temp 
		
		//     
		//   
		// 1. for     ：            ，          
		// 2.     ，    i           k，  k = i * 2 + 1
		// 3.       ，    i               ，  k = k * 2 + 1
		// 4.   for              ，               ，             
		// 5.     for      ，    i         ，i           （  ）
		for(int k = i * 2 + 1; k < length; k = k * 2 + 1) {
			//    
			// 1.    i              
			// 2.     ，  i                 ，                   ， arr[k + 1] < length 
			// 3.                 ，  k      
			if(k + 1 < length && arr[k] < arr[k + 1]) {//                ，  k      
				k++;// k      
			}
			if(arr[k] > temp) {//           ，          （      ）
				arr[i] = arr[k];//          （      ）
				i = k;//  i   K，      
			}else {//   arr[k] <= temp，      i   （temp）        
				break;//           ，    ，                  
			}
		}
		//     for      ，    i         ，i           （  ）
		//    for      ，i       k，         arr[i]  （ temp  ）   arr[i]，                  
		arr[i] = temp;//  temp           
	}

}

二、結果

    ：[4, 6, 8, 5, 9, 10, -2, 9, 25, 62]
--------------------        --------------------
    ：[-2, 4, 5, 6, 8, 9, 9, 10, 25, 62]