Java实现字符串数组和字符串排序

在Java环境下，对字符串数组或者对字符串排序都是一件很容易的事情，只要调用java.util包下的Arrays类的sort方法即可对其排序。

有没有想过，我们自己也可以利用排序算法编写一个属于自己的字符串数组和字符串排序，我就是这么做的，我利用了快速排序的思想：

* 一趟快速排序是：
 *1，随机产生一数列，选取第一个数（这里也可选其他的数）作为比较的基石，假设这个数为X,这样X=A[0]；设两个变量i=0，j=n-1；n是这个数列的长度
 *2，从前面开始找，找到第一个比A[0]大的数，找到了就与X交换
 *3，从后面开始找，找到第一个比A[0]小的数，找到了就与X交换
 *4，重复步骤2，3，直到i=j；
 *这样一趟快速排序就完成了；第一趟完成之后，X左边的数就全部小于X了，X右边的数九全部大于X，然后采用递归方式对X左边的数和X右边的数进行快速排序。 

字符串数排序代码如下：

package com.org.tool;

/** 
 * 字符串数组排序,利用快排的思想
 * @author xiaobangsky
 * time:2014-10-13
 *
 */
public class P4_8 {

	public static void quickSort(String[] pData,int left,int right)   
    {   
      int i,j;   
      String first,temp;   
      i = left;   
      j = right;   
      first = pData[left]; //这里选其他的数也行，不过一般选第一个  
      //一趟快速排序   
      while(true)   
      {   
      //从第二个数开始找大于中枢的数 ,从前面开始找大于pData[left]的数  
          while((++i)<right-1 && pData[i].compareTo(first)<0);   
          //从最后一个数开始找第一个小于中枢pData[left]的数   
          while((--j)>left && pData[j].compareTo(first)>0);   
          if(i>=j)   
              break;   
          //交换两边找到的数   
          temp = pData[i];   
          pData[i] = pData[j];   
          pData[j] = temp;   
   
      }   
      //交换中枢   
      pData[left] = pData[j];   
      pData[j] = first;   
      //递归快排中枢左边的数据   
      if(left<j)   
        quickSort(pData,left,j);   
      //递归快排中枢右边的数据   
      if(right>i)   
        quickSort(pData,i,right);   
    }   
	
	public static void main(String[] args) {
		String[] arr = new String[]{"one","onad","Dream","Beijing","Olympic"};
		quickSort(arr, 0, 5);
		for(String s:arr){
			System.out.print(s+" ");
		}
	}
}

package com.org.tool;

/**
 * 字符排序，快排思想
 * @author xiaobangsky
 * time:2014-10-13
 */
public class P4_9 {
	
	public static void quickSort(char[] pData,int left,int right)   
    {   
      int first,i,j;   
      char temp;   
      i = left;   
      j = right;   
      first = pData[left]; //这里选其他的数也行，不过一般选第一个  
      //一趟快速排序   
      while(true)   
      {   
      //从第二个数开始找大于中枢的数 ,从前面开始找大于pData[left]的数  
          while((++i)<right-1 && pData[i] < first);   
          //从最后一个数开始找第一个小于中枢pData[left]的数   
          while((--j)>left && pData[j]>first);   
          if(i>=j)   
              break;   
          //交换两边找到的数   
          temp = pData[i];   
          pData[i] = pData[j];   
          pData[j] = temp;   
   
      }   
      //交换中枢   
      pData[left] = pData[j];   
      pData[j] = (char) first;   
      //递归快排中枢左边的数据   
      if(left<j)   
        quickSort(pData,left,j);   
      //递归快排中枢右边的数据   
      if(right>i)   
        quickSort(pData,i,right);   
    }   
	
	public static void main(String[] args) {
		char[] arr = "xarvfwegfe".toCharArray();
		quickSort(arr, 0, 10);
		for(char s:arr){
			System.out.print(s);
		}
	}
}