/*
	  *   a -- 待排序的數(shù)組
	  *   n -- 數(shù)組的長度
	  */
	  public static void bubbleSort(int[] a, int n) {
	    int i,j;
 
	    for (i=n-1; i>0; i--) {
	      // 將a[0...i]中最大的數(shù)據(jù)放在末尾
	      for (j=0; j<i; j++) {
 
	        if (a[j] > a[j+1]) {
	          // 交換a[j]和a[j+1]
	          int tmp = a[j];
	          a[j] = a[j+1];
	          a[j+1] = tmp;
	        }
	      }
	    }
	   
	  }

int[] a = {20,40,30,10,60,50,70};
    String aa = "冒泡排序";
    bubbleSort(a,a.length);
 
 System.out.print(aa);
 for (int d : a) {
  System.out.print(d+",");
}

/**
	  *
	  * 參數(shù)說明：
	  *   a -- 待排序的數(shù)組
	  *   l -- 數(shù)組的左邊界(例如，從起始位置開始排序，則l=0)
	  *   r -- 數(shù)組的右邊界(例如，排序截至到數(shù)組末尾，則r=a.length-1)
	  */
	  public static void quickSort(int[] a, int l, int r) {
 
	    if (l < r) {
	      int i,j,x;
 
	      i = l;
	      j = r;
	      x = a[i];
	      while (i < j) {
	        while(i < j && a[j] > x)
	          j--; // 從右向左找第一個小于x的數(shù)
	        if(i < j)
	          a[i++] = a[j];
	        while(i < j && a[i] < x)
	          i++; // 從左向右找第一個大于x的數(shù)
	        if(i < j)
	          a[j--] = a[i];
	      }
	      a[i] = x;
	      quickSort(a, l, i-1); /* 遞歸調(diào)用 */
	      quickSort(a, i+1, r); /* 遞歸調(diào)用 */
	    }
	   
	  }

      String aa = "快速排序";
	    quickSort(a,0,a.length-1);
	    
 
	    
	    System.out.print(aa);
	    for (int d : a) {
	  	  System.out.print(d+",");
		  }

 /**
	  * @param 
	  *   a -- 待排序的數(shù)組
	  *   n -- 數(shù)組的長度
	  */
	  public static void insertSort(int[] a, int n) {
    int i, j, k;
 
    for (i = 1; i < n; i++) {
 
      //為a[i]在前面的a[0...i-1]有序區(qū)間中找一個合適的位置
      for (j = i - 1; j >= 0; j--)
        if (a[j] < a[i])
          break;
 
      //如找到了一個合適的位置
      if (j != i - 1) {
        //將比a[i]大的數(shù)據(jù)向后移
        int temp = a[i];
        for (k = i - 1; k > j; k--)
          a[k + 1] = a[k];
        //將a[i]放到正確位置上
        a[k + 1] = temp;
      }
    }
  }

/**
	  	 * 希爾排序
	  	 * @param list
	  	 */
	  public static void shellSort(int[] a) {
	    int gap = a.length / 2;
 
	    while (1 <= gap) {
	      // 把距離為 gap 的元素編為一個組，掃描所有組
	      for (int i = gap; i < a.length; i++) {
	        int j = 0;
	        int temp = a[i];
 
	        // 對距離為 gap 的元素組進(jìn)行排序
	        for (j = i - gap; j >= 0 && temp < a[j]; j = j - gap) {
	          a[j + gap] = a[j];
	        }
	        a[j + gap] = temp;
	      }
 
	      System.out.format("gap = %d:\t", gap);
	      printAll(a);
	      gap = gap / 2; // 減小增量
	    }
	  }
	  // 打印完整序列
	  public static void printAll(int[] a) {
	    for (int value : a) {
	      System.out.print(value + "\t");
	    }
	    System.out.println();
	  }

public class ListDG {
  // 鄰接表中表對應(yīng)的鏈表的頂點(diǎn)
  private class ENode {
    int ivex;    
    // 該邊所指向的頂點(diǎn)的位置
    ENode nextEdge; 
    // 指向下一條弧的指針
  }
 
  // 鄰接表中表的頂點(diǎn)
  private class VNode {
    char data;     
    // 頂點(diǎn)信息
    ENode firstEdge;  
    // 指向第一條依附該頂點(diǎn)的弧
  };
 
  private VNode[] mVexs; 
  // 頂點(diǎn)數(shù)組
 
  ...
}

/*
* 拓?fù)渑判?
*
* 返回值：
*   -1 -- 失敗(由于內(nèi)存不足等原因?qū)е?
*   0 -- 成功排序，并輸入結(jié)果
*   1 -- 失敗(該有向圖是有環(huán)的)
*/
public int topologicalSort() {
  int index = 0;
  int num = mVexs.size();
  int[] ins;        
  // 入度數(shù)組
  char[] tops;       
  // 拓?fù)渑判蚪Y(jié)果數(shù)組，記錄每個節(jié)點(diǎn)的排序后的序號。
  Queue<Integer> queue;  
  // 輔組隊(duì)列
 
  ins  = new int[num];
  tops = new char[num];
  queue = new LinkedList<Integer>();
 
  // 統(tǒng)計(jì)每個頂點(diǎn)的入度數(shù)
  for(int i = 0; i < num; i++) {
 
    ENode node = mVexs.get(i).firstEdge;
    while (node != null) {
      ins[node.ivex]++;
      node = node.nextEdge;
    }
  }
 
  // 將所有入度為0的頂點(diǎn)入隊(duì)列
  for(int i = 0; i < num; i ++)
    if(ins[i] == 0)
      queue.offer(i);         
      // 入隊(duì)列
 
  while (!queue.isEmpty()) {       
  // 隊(duì)列非空
    int j = queue.poll().intValue();  
    // 出隊(duì)列。j是頂點(diǎn)的序號
    tops[index++] = mVexs.get(j).data; 
    // 將該頂點(diǎn)添加到tops中，tops是排序結(jié)果
    ENode node = mVexs.get(j).firstEdge;
    // 獲取以該頂點(diǎn)為起點(diǎn)的出邊隊(duì)列
 
    // 將與"node"關(guān)聯(lián)的節(jié)點(diǎn)的入度減1；
    // 若減1之后，該節(jié)點(diǎn)的入度為0；則將該節(jié)點(diǎn)添加到隊(duì)列中。
    while(node != null) {
      // 將節(jié)點(diǎn)(序號為node.ivex)的入度減1。
      ins[node.ivex]--;
      // 若節(jié)點(diǎn)的入度為0，則將其"入隊(duì)列"
      if( ins[node.ivex] == 0)
        queue.offer(node.ivex);  
        // 入隊(duì)列
 
      node = node.nextEdge;
    }
  }
 
  if(index != num) {
    System.out.printf("Graph has a cycle\n");
    return 1;
  }
 
  // 打印拓?fù)渑判蚪Y(jié)果
  System.out.printf("== TopSort: ");
  for(int i = 0; i < num; i ++)
    System.out.printf("%c ", tops[i]);
  System.out.printf("\n");
 
  return 0;
}

package sortdemo;
 
import java.util.Arrays;
 
/**
* Created by chengxiao on 2016/12/8.
*/
public class MergeSort {
 public static void main(String []args){
   int []arr = {9,8,7,6,5,4,3,2,1};
   sort(arr);
   System.out.println(Arrays.toString(arr));
 }
 public static void sort(int []arr){
   int []temp = new int[arr.length];
   //在排序前，先建好一個長度等于原數(shù)組長度的臨時(shí)數(shù)組，
   //避免遞歸中頻繁開辟空間
   sort(arr,0,arr.length-1,temp);
 }
 private static void sort(int[] arr,int left,int right,int []temp){
   if(left<right){
     int mid = (left+right)/2;
     sort(arr,left,mid,temp);
     //左邊歸并排序，使得左子序列有序
     sort(arr,mid+1,right,temp);
     //右邊歸并排序，使得右子序列有序
     merge(arr,left,mid,right,temp);
     //將兩個有序子數(shù)組合并操作
   }
 }
 private static void merge(int[] arr,int left,int mid,int right,int[] temp){
   int i = left;//左序列指針
   int j = mid+1;//右序列指針
   int t = 0;//臨時(shí)數(shù)組指針
   while (i<=mid && j<=right){
     if(arr[i]<=arr[j]){
       temp[t++] = arr[i++];
     }else {
       temp[t++] = arr[j++];
     }
   }
   while(i<=mid){//將左邊剩余元素填充進(jìn)temp中
     temp[t++] = arr[i++];
   }
   while(j<=right){//將右序列剩余元素填充進(jìn)temp中
     temp[t++] = arr[j++];
   }
   t = 0;
   //將temp中的元素全部拷貝到原數(shù)組中
   while(left <= right){
     arr[left++] = temp[t++];
   }
 }
}