直接插入排序的再再改进

import java.util.Arrays;
import java.util.Scanner;

public class aaa {
		
	static void bubble(int a[],int n){
		for(int i=0;i<n-1;i++){
			for(int j=0;j<=n-2-i ;j++){
				if(a[j]>a[j+1]){ //循环遍历，枚举出i位置每个值，若大于后者则移动
					int temp=a[j];
					a[j]=a[j+1];
					a[j+1]=temp;					
				}
			}
		}
	}
	static int max(int a,int b){
		if(a<b) return b;
		return a;
	}
	static int min(int a,int b){
		if(a>b) return b;
		return a;
	}
	static void enhance(int a[],int n){
		for(int i=3;i<=n-3;i=i+3){ //进行2趟排序
			
			for(int j=i;j>=3;j=j-3){//枚举遍历出j的每个位置的值
				if( a[j]>a[j-3] ) break;
	if(  a[j]==a[j-3]  &&  max( a[j+1],a[j+2])>max(a[j-2],a[j-1]) ) break;
				if(  a[j]==a[j-3]  &&  
				max( a[j+1],a[j+2])== max(a[j-2],a[j-1]) &&
				min( a[j+1],a[j+2])>= min(a[j-2],a[j-1]) ) break;
				
				//进入交换
				int a1=a[j-3],a2=a[j-2],a3=a[j-1];
				a[j-3]=a[j]; a[j-2]=a[j+1];a[j-1]=a[j+2];
				a[j]=a1;  a[j+1]=a2;  a[j+2]=a3;
				
				//准备下次循环			
			}		
		}
	}
	
	


	static void enhance1(int a[],int n){
		for(int i=3;i<=n-3;i=i+3){
			int a0=a[i],a1=a[i+1],a2=a[i+2];//挖坑
			int j=i-3;
			for(;j>=0;j=j-3){
				if(a[j]>a0 || (a[j]==a0&&max(a[j+1],a[j+2])>max(a1,a2))||
						a[j]==a0&&max(a[j+1],a[j+2])==max(a1,a2)&&
						min(a[j+1],a[j+2])>min(a1,a2))//则需要移动
					{a[j+3]=a[j];a[j+4]=a[j+1];a[j+5]=a[j+2];}
				else 
					break;//则不需要移动
				
			}
			if((j+3)!=i) {a[j+3]=a0;a[j+4]=a1;a[j+5]=a2;}
		}
		System.out.println(Arrays.toString(a));
	}
	
	


	static void delete(int a[],int n){
		int i=0;//指向有序表
		if(a[2]>a[1]) {int temp =a[1]; a[1]=a[2];a[2]=temp;}
		for(int j=3;j<n;j=j+3){//一直向后枚举遍历
			if( a[j]==a[i] && 
			    max(a[j+1],a[j+2]) ==max(a[i+1],a[i+2]) &&
			    min(a[j+1],a[j+2]) ==min(a[i+1],a[i+2])
			   )
				continue;
				
			i = i+3;
			a[i] = a[j]; 
		   //操纵一片区域
		    if( a[j+1]>a[j+2] ) {a[i+1]=a[j+1];a[i+2]=a[j+2];}
		    else {int b1=a[j+2]; int b2= a[j+1];a[i+1]=b1;a[i+2]=b2;}
		}
		for(int k=0;k<=i;k=k+3){
			System.out.println(a[k]+" "+a[k+1]+" "+a[k+2]);
		}
	}
	/**
	 * 2 1 1
	 * 1 2 1
	 * 2 1 1
	 * 1 2 1
	 * 1 2 1
	 * 2 4 2
	 * 先进行按照第三位的关键字进行排序
	 * 对1分组，按照第二位的关键字进行排序
	 * 对2分组，按照第二位的关键字排序
	 */
	
	
	
	public static void main(String args[]){
		 Scanner s = new Scanner(System.in);
		 int i = s.nextInt(); //输入有多少次测试
		 for(int k=0;k<i;k++){
	     int i1 = s.nextInt(); //多少组
	     int array[]=new int[3*i1];
	     for(int k1=0;k1<3*i1;k1++){
	    	 array[k1]=s.nextInt();
	     }
		 enhance1(array,array.length);
		 delete(array,array.length);
		 }
		
	}

}