import java.util.Scanner ;public class Selection{                         //选择排序	public static void selectionSort(Comparable[] a){		int n = a.length ;		for (int i=0;i<n-1;i++) {			int min = i ;			for (int j=i+1;j<n;j++) {				if (less(a[j],a[min])) {					min = j ;				}			}			exch(a,i,min) ;		}	}	private static boolean less(Comparable v, Comparable w){  //判断大小		if (v.compareTo(w)<0) {			return true ;		}else{			return false ;		}	}	private static void exch(Comparable[] a, int i, int j){  //交换元素 ；		Comparable temp = a[i] ;		a[i] = a[j] ;		a[j] = temp ;	}	private static void show(Comparable[] a){       //打印出来			for (int i=0;i<a.length;i++) {			System.out.print(a[i] + " ") ;		}		System.out.println() ;	}	public static boolean isSorted(Comparable[] a){  //判断是否已排序；		for(int i=1;i<a.length;i++){			if (less(a[i],a[i-1])) {				return false ;			}		}		return true ;	}	public static void main(String[] args){//测试；				System.out.println("please input the length of array:") ;				Scanner sc = new Scanner(System.in) ;		int len = sc.nextInt() ;		String[] a = new String[len] ;		System.out.println("please input the numbers of array:") ;		for (int i=0;i<len;i++) {			a[i] = sc.next() ;		}		if (!isSorted(a)) {			selectionSort(a) ;		}		show(a) ;	} }

import java.util.Scanner ;public class Bubble{           //冒泡排序；	public static void bubbleSort(Comparable[] a){		int n = a.length ;		for (int i=1;i<n;i++) {			for (int j=0;j<n-i;j++) {				if (less(a[j+1],a[j])) {					exch(a,j,j+1) ;				}			}		}	}	private static boolean less(Comparable v, Comparable w){ //判断元素大小；		if (v.compareTo(w)<0) {			return true ;		}else{			return false ;		}	}	private static void exch(Comparable[] a, int i, int j){   //交换元素；		Comparable temp = a[i] ;		a[i] = a[j] ;		a[j] = temp ;	}	private static void show(Comparable[] a){	//打印；		for (int i=0;i<a.length;i++) {			System.out.print(a[i] + " ") ;		}		System.out.println() ;	}	public static boolean isSorted(Comparable[] a){   //判断是否已排序；		for(int i=1;i<a.length;i++){			if (less(a[i],a[i-1])) {				return false ;			}		}		return true ;	}	public static void main(String[] args){//测试；				System.out.println("please input the length of array:") ;				Scanner sc = new Scanner(System.in) ;		int len = sc.nextInt() ;		String[] a = new String[len] ;		System.out.println("please input the numbers of array:") ;		for (int i=0;i<len;i++) {			a[i] = sc.next() ;		}		if (!isSorted(a)) {			bubbleSort(a) ;		}		show(a) ;	} }

import java.util.Scanner ;public class Insertion{            //插入排序；	public static void insertionSort(Comparable[] a){          //方法一；		int n = a.length ;		for (int i=1;i<n;i++) {			for (int j=i;j>0 && less(a[j],a[j-1]);j--) {				exch(a,j,j-1) ;			}		}	}	public static void insertionSort02(Comparable[] a){        //方法二；		int n = a.length ;		for (int i=1;i<n;i++) {			Comparable temp = a[i] ;			int j = i ;			for (j=i-1;j>=0 && less(temp,a[j]);j--) {				a[j+1] = a[j] ;			}			a[j+1] = temp ;		}	}	private static boolean less(Comparable v, Comparable w){  //判断元素大小；		if (v.compareTo(w)<0) {			return true ;		}else{			return false ;		}	}	private static void exch(Comparable[] a, int i, int j){   //交换元素；		Comparable temp = a[i] ;		a[i] = a[j] ;		a[j] = temp ;	}	private static void show(Comparable[] a){	    //打印；		for (int i=0;i<a.length;i++) {			System.out.print(a[i] + " ") ;		}		System.out.println() ;	}	public static boolean isSorted(Comparable[] a){    //判断是否已排序；		for(int i=1;i<a.length;i++){			if (less(a[i],a[i-1])) {				return false ;			}		}		return true ;	}	public static void main(String[] args){//测试；				System.out.println("please input the length of array:") ;				Scanner sc = new Scanner(System.in) ;		int len = sc.nextInt() ;		String[] a = new String[len] ;		System.out.println("please input the numbers of array:") ;		for (int i=0;i<len;i++) {			a[i] = sc.next() ;		}		if (!isSorted(a)) {			insertionSort02(a) ;		}		show(a) ;	} }

import java.util.Scanner ;public class Shell{                //希尔排序；	public static void shellSort(Comparable[] a){		int n = a.length ;		int h = 1 ;		while(h<n/3){			h = 3*h + 1 ;		}		while(h>=1){			for (int i=h;i<n;i++) {				for (int j=i;j>=h && less(a[j],a[j-h]);j=j-h) {					exch(a,j,j-h) ;				}			}			h = h/3 ;		}	}	private static boolean less(Comparable v, Comparable w){  //判断元素大小；		if (v.compareTo(w)<0) {			return true ;		}else{			return false ;		}	}	private static void exch(Comparable[] a, int i, int j){    //交换元素；		Comparable temp = a[i] ;		a[i] = a[j] ;		a[j] = temp ;	}	private static void show(Comparable[] a){	   //打印；		for (int i=0;i<a.length;i++) {			System.out.print(a[i] + " ") ;		}		System.out.println() ;	}	public static boolean isSorted(Comparable[] a){     //判断是否已排序；		for(int i=1;i<a.length;i++){			if (less(a[i],a[i-1])) {				return false ;			}		}		return true ;	}	public static void main(String[] args){  //测试；				System.out.println("please input the length of array:") ;				Scanner sc = new Scanner(System.in) ;		int len = sc.nextInt() ;		String[] a = new String[len] ;		System.out.println("please input the numbers of array:") ;		for (int i=0;i<len;i++) {			a[i] = sc.next() ;		}		if (!isSorted(a)) {			shellSort(a) ;		}		show(a) ;	} }

import java.util.Scanner ;public class Merge{//归并排序；	private static Comparable[] aux ;	public static void mergeSort(Comparable[] a){		aux = new Comparable[a.length] ;		mergeSort(a,0,a.length-1) ;	}	private static void mergeSort(Comparable[] a, int lo, int hi){		if (lo<hi) {			int mid = (lo+hi)/2 ;			mergeSort(a,lo,mid) ;			mergeSort(a,mid+1,hi) ;			merge(a,lo,mid,hi) ;		}else{			return ;		}	}	private static void merge(Comparable[] a, int lo, int mid, int hi){		int i = lo ;		int j = mid+1 ;		for (int k=lo;k<=hi;k++) {			aux[k] = a[k] ;		}		for (int k=lo;k<=hi;k++) {			if (i>mid) {				a[k] = aux[j] ;				j++ ;			}else if(j>hi){				a[k] = aux[i] ;				i++ ;			}else if(less(aux[i],aux[j])){				a[k] = aux[i] ;				i++ ;			}else{				a[k] = aux[j] ;				j++ ;			}		}	}	private static boolean less(Comparable v, Comparable w){  //判断元素大小；		if (v.compareTo(w)<0) {			return true ;		}else{			return false ;		}	}	private static void exch(Comparable[] a, int i, int j){   //交换元素；		Comparable temp = a[i] ;		a[i] = a[j] ;		a[j] = temp ;	}	private static void show(Comparable[] a){	//打印；		for (int i=0;i<a.length;i++) {			System.out.print(a[i] + " ") ;		}		System.out.println() ;	}	public static boolean isSorted(Comparable[] a){   //判断是否已排序；		for(int i=1;i<a.length;i++){			if (less(a[i],a[i-1])) {				return false ;			}		}		return true ;	}	public static void main(String[] args){//测试；				System.out.println("please input the length of array:") ;				Scanner sc = new Scanner(System.in) ;		int len = sc.nextInt() ;		String[] a = new String[len] ;		System.out.println("please input the numbers of array:") ;		for (int i=0;i<len;i++) {			a[i] = sc.next() ;		}		if (!isSorted(a)) {			mergeSort(a) ;		}		show(a) ;	} }

import java.util.Scanner ;public class Quick{       //快速排序；	public static void quickSort(Comparable[] a){		quickSort(a,0,a.length-1) ;	}	private static void quickSort(Comparable[] a, int lo, int hi){		if (lo<hi) {			int j = partition(a,lo,hi) ;			quickSort(a,lo,j-1) ;			quickSort(a,j+1,hi) ;		}else{			return ;		}	}	private static int partition(Comparable[] a, int lo, int hi){		int i = lo ;		int j = hi ;		Comparable temp = a[lo] ;		while(i!=j){			while(i<j && !less(a[j],temp)){				j-- ;			}			while(i<j && !less(temp,a[i])){				i++ ;			}			if (i!=j) {				exch(a,i,j) ;			}		}		exch(a,lo,i) ;		return j ;	}	private static boolean less(Comparable v, Comparable w){   //判断元素大小；		if (v.compareTo(w)<0) {			return true ;		}else{			return false ;		}	}	private static void exch(Comparable[] a, int i, int j){    //交换元素；		Comparable temp = a[i] ;		a[i] = a[j] ;		a[j] = temp ;	}	private static void show(Comparable[] a){	//打印；		for (int i=0;i<a.length;i++) {			System.out.print(a[i] + " ") ;		}		System.out.println() ;	}	public static boolean isSorted(Comparable[] a){   //判断是否已排序；		for(int i=1;i<a.length;i++){			if (less(a[i],a[i-1])) {				return false ;			}		}		return true ;	}	public static void main(String[] args){//测试；				System.out.println("please input the length of array:") ;				Scanner sc = new Scanner(System.in) ;		int len = sc.nextInt() ;		String[] a = new String[len] ;		System.out.println("please input the numbers of array:") ;		for (int i=0;i<len;i++) {			a[i] = sc.next() ;		}		if (!isSorted(a)) {			quickSort(a) ;		}		show(a) ;	} }