Cracking the coding interview--Q9.2

原文：

Write a method to sort an array of strings so that all the anagrams are next to each other.

译文：

写一个函数对字符串数组排序，使得所有的变位词都相邻。

解答

首先需要理解什么是变位词？变位词就是字符组成的元素相同，只不过位置不同而已，例如：abc与bca是变位词；然后需要排序的话，可以调用集合的排序方法sort,但要使所有变位词相邻，则需要自定义排序，所以需要重写比较器Comparator接口，代码如下：

/**
 * 强行对某个对象collection进行整体排序的比较函数，可以将Comparator传递给Collections.sort或Arrays.sort。
 * 
 */
class StringComparator implements Comparator<String> {
	
	public String sortString(String str) {
		char[] chars = str.toCharArray();
		Arrays.sort(chars);
		return new String(chars);
	}
	// 具体比较方法
	public int compare(String str1, String str2) {
		return sortString(str1).compareTo(sortString(str2));
	}
}

或者自定义实现String类比较

/**
 * 强行对实现它的每个类的对象进行整体排序，实现此接口的对象列表（和数组）可以通过Collections.sort或Arrays.sort进行自动排序
 * 
 */
class MyString {
	private String str;
	
	public void setStr(String str) {
		this.str = str;
	}
	
	public String getStr() {
		return str;
	}
	
	public static String strSort(String str) {
		char[] chars = str.toCharArray();
		Arrays.sort(chars);
		return new String(chars);
	}
	
	/**
	  * @return 该对象小于、等于或大于指定对象object，分别返回负整数、零或正整数。 
	  */
	public int compareTo(Object object) {
		String str1 = strSort(this.str);
		String str2 = strSort(((MyString)object).getStr());
		return str1.compareTo(str2);
	}
}

总代码：

package chapter_9_SortingandSearching;

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


/**
 * 强行对某个对象collection进行整体排序的比较函数，可以将Comparator传递给Collections.sort或Arrays.sort。
 * 
 */
class StringComparator implements Comparator<String> {
	
	public String sortString(String str) {
		char[] chars = str.toCharArray();
		Arrays.sort(chars);
		return new String(chars);
	}
	// 具体比较方法
	public int compare(String str1, String str2) {
		return sortString(str1).compareTo(sortString(str2));
	}
}


/**
 * 强行对实现它的每个类的对象进行整体排序，实现此接口的对象列表（和数组）可以通过Collections.sort或Arrays.sort进行自动排序
 * 
 */
class MyString {
	private String str;
	
	public void setStr(String str) {
		this.str = str;
	}
	
	public String getStr() {
		return str;
	}
	
	public static String strSort(String str) {
		char[] chars = str.toCharArray();
		Arrays.sort(chars);
		return new String(chars);
	}
	
	/**
	  * @return 该对象小于、等于或大于指定对象object，分别返回负整数、零或正整数。 
	  */
	public int compareTo(Object object) {
		String str1 = strSort(this.str);
		String str2 = strSort(((MyString)object).getStr());
		return str1.compareTo(str2);
	}
}

/**
 * 
 * 写一个方法对一个字符串数组进行排序，并使所有变位词都相邻。
 * 
 */
public class Question_9_2 {
	
	public static int findPartion(MyString str[], int start, int end) {
		MyString string = str[start];
		while(start < end) {
			while(start < end && (str[end].compareTo(string)>=0)) {
				end --;
			}
			str[start] = str[end];
			while(start < end && (str[start].compareTo(string) < 0)) {
				start ++;
			}
			str[end] = str[start];
		}
		str[start] = string;
		return start;
	}
	
	/**
	 * @param str
	 * @param start
	 * @param end
	 * 
	 * 快速排序
	 * 
	 */
	public static void quickSort(MyString str[], int start, int end) {
		if(start < end) {
			int partion = findPartion(str, start, end);
			quickSort(str, start, partion-1);
			quickSort(str, partion+1, end);
		}
	}
	
	public static void main(String args[]) {
		Scanner scanner = new Scanner(System.in);
		String strs = scanner.nextLine();
		String str[] = strs.split(" ");
		Arrays.sort(str, new StringComparator());
		
		for(String string: str) {
			System.out.println("" + string);
		}
		
		strs = scanner.nextLine();
		str = strs.split(" ");
		MyString[] myStrings = new MyString[str.length];
		for(int i=0; i< str.length; i++) {
			myStrings[i] = new MyString();
			myStrings[i].setStr(str[i]);
		}
		
		quickSort(myStrings, 0, myStrings.length-1);
		for(MyString string: myStrings) {
			System.out.println("" + string.getStr());
		}
	}	
}