import java.util.Arrays; 
import java.util.List; 
import java.util.Map; 
import java.util.Random; 
import java.util.TreeMap; 
 
/** 
 * @desc 數(shù)組操作工具 
 * @author OuyangPeng 
 * @datatime 2013-5-11 10:31:02 
 * 
 */ 
public class MyArrayUtils { 
 
  /** 
   * 排序算法的分類如下： 1.插入排序（直接插入排序、折半插入排序、希爾排序）； 2.交換排序（冒泡泡排序、快速排序）； 
   * 3.選擇排序（直接選擇排序、堆排序）； 4.歸并排序； 5.基數(shù)排序。 
   * 
   * 關(guān)于排序方法的選擇： (1)若n較小(如n≤50)，可采用直接插入或直接選擇排序。 
   * (2)若文件初始狀態(tài)基本有序(指正序)，則應(yīng)選用直接插人、冒泡或隨機的快速排序為宜； 
   * (3)若n較大，則應(yīng)采用時間復(fù)雜度為O(nlgn)的排序方法：快速排序、堆排序或歸并排序。 
   * 
   */ 
 
  /** 
   * 交換數(shù)組中兩元素 
   * 
   * @since 1.1 
   * @param ints 
   *      需要進行交換操作的數(shù)組 
   * @param x 
   *      數(shù)組中的位置1 
   * @param y 
   *      數(shù)組中的位置2 
   * @return 交換后的數(shù)組 
   */ 
  public static int[] swap(int[] ints, int x, int y) { 
    int temp = ints[x]; 
    ints[x] = ints[y]; 
    ints[y] = temp; 
    return ints; 
  } 
 
  /** 
   * 冒泡排序方法:相鄰兩元素進行比較 性能：比較次數(shù)O(n^2),n^2/2；交換次數(shù)O(n^2),n^2/4<br> 
   * 冒泡排序（Bubble Sort）是一種簡單的排序算法。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個元素，<br> 
   * 如果他們的順序錯誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進行直到?jīng)]有再需要交換，<br> 
   * 也就是說該數(shù)列已經(jīng)排序完成。這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端。<br> 
    　　冒泡排序算法的運作如下:<br> 
     1. 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。<br> 
     2. 對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。在這一點，最后的元素應(yīng)該會是最大的數(shù)。<br> 
     3. 針對所有的元素重復(fù)以上的步驟，除了最后一個。<br> 
     4. 持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。<br> 
   * @since 1.1 
   * @param source 
   *      需要進行排序操作的數(shù)組 
   * @return 排序后的數(shù)組 
   */ 
  public static int[] bubbleSort(int[] source) { 
    /*for (int i = 0; i < source.length - 1; i++) { // 最多做n-1趟排序 
      for (int j = 0; j < source.length - i - 1; j++) { // 對當(dāng)前無序區(qū)間score[0......length-i-1]進行排序(j的范圍很關(guān)鍵，這個范圍是在逐步縮小的) 
        if (source[j] > source[j + 1]) { // 把大的值交換到后面 
          swap(source, j, j + 1); 
        } 
      } 
    }*/ 
    for (int i = source.length - 1; i>0 ; i--) {  
      for (int j = 0; j < i; j++) {  
        if (source[j] > source[j + 1]) {  
          swap(source, j, j + 1); 
        } 
      } 
    } 
    return source; 
  } 
 
  /** 
   * 選擇排序法 方法：選擇排序(Selection sort)是一種簡單直觀的排序算法，其平均時間復(fù)雜度為O(n2)。 
   *   它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后， 
   *   再從剩余未排序元素中繼續(xù)尋找最小元素，然后放到排序序列末尾。以此類推，直到所有元素均排序完畢。 
   * 性能：選擇排序的交換操作介于0和(n-1)次之間， 選擇排序的比較操作為n(n-1)/2次之間， 
   *    選擇排序的賦值操作介于0和3(n-1)次之間，其平均時間復(fù)雜度為O(n2) 
   * 交換次數(shù)比冒泡排序少多了，由于交換所需CPU時間比比較所需的CUP時間多，所以選擇排序比冒泡排序快。 
   * 但是N比較大時，比較所需的CPU時間占主要地位，所以這時的性能和冒泡排序差不太多，但毫無疑問肯定要快些。 
   * 
   * @since 1.1 
   * @param source 
   *      需要進行排序操作的數(shù)組 
   * @return 排序后的數(shù)組 
   */ 
  public static int[] selectSort(int[] source) { 
    for (int i = 0; i < source.length; i++) { 
      for (int j = i + 1; j < source.length; j++) { 
        if (source[i] > source[j]) { 
          swap(source, i, j); 
        } 
      } 
    } 
    return source; 
  } 
 
  /** 
   * 插入排序 方法：將一個記錄插入到已排好序的有序表（有可能是空表）中,從而得到一個新的記錄數(shù)增1的有序表。 性能：比較次數(shù)O(n^2),n^2/4 
   * 復(fù)制次數(shù)O(n),n^2/4 比較次數(shù)是前兩者的一般，而復(fù)制所需的CPU時間較交換少，所以性能上比冒泡排序提高一倍多，而比選擇排序也要快。 
   * 
   * @since 1.1 
   * @param source 
   *      需要進行排序操作的數(shù)組 
   * @return 排序后的數(shù)組 
   */ 
  public static int[] insertSort(int[] source) { 
 
    for (int i = 1; i < source.length; i++) { 
      for (int j = i; (j > 0) && (source[j] < source[j - 1]); j--) { 
        swap(source, j, j - 1); 
      } 
    } 
    return source; 
  } 
 
  /** 
   * 快速排序 快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為兩個子序列（sub-lists）。 步驟為： 
   * 1. 從數(shù)列中挑出一個元素，稱為 "基準(zhǔn)"（pivot）， 2. 
   * 重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面 
   * （相同的數(shù)可以到任一邊）。在這個分割之后，該基準(zhǔn)是它的最后位置。這個稱為分割（partition）操作。 3. 
   * 遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。 
   * 遞回的最底部情形，是數(shù)列的大小是零或一，也就是永遠(yuǎn)都已經(jīng)被排序好了 
   * 。雖然一直遞回下去，但是這個算法總會結(jié)束，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去。 
   * 
   * @since 1.1 
   * @param source 
   *      需要進行排序操作的數(shù)組 
   * @return 排序后的數(shù)組 
   */ 
  public static int[] quickSort(int[] source) { 
    return qsort(source, 0, source.length - 1); 
  } 
 
  /** 
   * 快速排序的具體實現(xiàn)，排正序 
   * 
   * @since 1.1 
   * @param source 
   *      需要進行排序操作的數(shù)組 
   * @param low 
   *      開始低位 
   * @param high 
   *      結(jié)束高位 
   * @return 排序后的數(shù)組 
   */ 
  private static int[] qsort(int source[], int low, int high) { 
    int i, j, x; 
    if (low < high) { 
      i = low; 
      j = high; 
      x = source[i]; 
      while (i < j) { 
        while (i < j && source[j] > x) { 
          j--; 
        } 
        if (i < j) { 
          source[i] = source[j]; 
          i++; 
        } 
        while (i < j && source[i] < x) { 
          i++; 
        } 
        if (i < j) { 
          source[j] = source[i]; 
          j--; 
        } 
      } 
      source[i] = x; 
      qsort(source, low, i - 1); 
      qsort(source, i + 1, high); 
    } 
    return source; 
  } 
 
  // ///////////////////////////////////////////// 
  // 排序算法結(jié)束 
  // //////////////////////////////////////////// 
  /** 
   * 二分法查找 查找線性表必須是有序列表 
   * 
   * @since 1.1 
   * @param source 
   *      需要進行查找操作的數(shù)組 
   * @return 需要查找的值在數(shù)組中的位置，若未查到則返回-1 
   */ 
  public static int[] binarySearch(int[] source) { 
    int i,j; 
    int low, high, mid; 
    int temp; 
    for (i = 0; i < source.length; i++) { 
      temp=source[i]; 
      low=0; 
      high=i-1; 
      while (low <= high) { 
        mid = (low + high)/2; 
        if (source[mid]>temp) { 
          high=mid-1; 
        } else { 
          low = mid + 1; 
        } 
      } 
      for (j= i-1; j>high;j--)  
        source[j+1]=source[j]; 
      source[high+1]=temp; 
    } 
    return source; 
  } 
 
  /** 
   * 反轉(zhuǎn)數(shù)組 
   * 
   * @since 1.1 
   * @param source 
   *      需要進行反轉(zhuǎn)操作的數(shù)組 
   * @return 反轉(zhuǎn)后的數(shù)組 
   */ 
  public static int[] reverse(int[] source) { 
    int length = source.length; 
    int temp = 0; 
    for (int i = 0; i < length >> 1; i++) { 
      temp = source[i]; 
      source[i] = source[length - 1 - i]; 
      source[length - 1 - i] = temp; 
    } 
    return source; 
  } 
 
  /** 
   * 在當(dāng)前位置插入一個元素,數(shù)組中原有元素向后移動; 如果插入位置超出原數(shù)組，則拋IllegalArgumentException異常 
   * 
   * @param array 
   * @param index 
   * @param insertNumber 
   * @return 
   */ 
  public static int[] insert(int[] array, int index, int insertNumber) { 
    if (array == null || array.length == 0) { 
      throw new IllegalArgumentException(); 
    } 
    if (index - 1 > array.length || index <= 0) { 
      throw new IllegalArgumentException(); 
    } 
    int[] dest = new int[array.length + 1]; 
    System.arraycopy(array, 0, dest, 0, index - 1); 
    dest[index - 1] = insertNumber; 
    System.arraycopy(array, index - 1, dest, index, dest.length - index); 
    return dest; 
  } 
 
  /** 
   * 整形數(shù)組中特定位置刪除掉一個元素,數(shù)組中原有元素向前移動; 如果插入位置超出原數(shù)組，則拋IllegalArgumentException異常 
   * 
   * @param array 
   * @param index 
   * @return 
   */ 
  public static int[] remove(int[] array, int index) { 
    if (array == null || array.length == 0) { 
      throw new IllegalArgumentException(); 
    } 
    if (index > array.length || index <= 0) { 
      throw new IllegalArgumentException(); 
    } 
    int[] dest = new int[array.length - 1]; 
    System.arraycopy(array, 0, dest, 0, index - 1); 
    System.arraycopy(array, index, dest, index - 1, array.length - index); 
    return dest; 
  } 
 
  /** 
   * 2個數(shù)組合并，形成一個新的數(shù)組 
   * 
   * @param array1 
   * @param array2 
   * @return 
   */ 
  public static int[] merge(int[] array1, int[] array2) { 
    int[] dest = new int[array1.length + array2.length]; 
    System.arraycopy(array1, 0, dest, 0, array1.length); 
    System.arraycopy(array2, 0, dest, array1.length, array2.length); 
    return dest; 
  } 
 
  /** 
   * 數(shù)組中有n個數(shù)據(jù)，要將它們順序循環(huán)向后移動k位， 即前面的元素向后移動k位，后面的元素則循環(huán)向前移k位， 
   * 例如，0、1、2、3、4循環(huán)移動3位后為2、3、4、0、1。 
   * 
   * @param array 
   * @param offset 
   * @return 
   */ 
  public static int[] offsetArray(int[] array, int offset) { 
    int length = array.length; 
    int moveLength = length - offset; 
    int[] temp = Arrays.copyOfRange(array, moveLength, length); 
    System.arraycopy(array, 0, array, offset, moveLength); 
    System.arraycopy(temp, 0, array, 0, offset); 
    return array; 
  } 
 
  /** 
   * 隨機打亂一個數(shù)組 
   * 
   * @param list 
   * @return 
   */ 
  public static List shuffle(List list) { 
    java.util.Collections.shuffle(list); 
    return list; 
  } 
 
  /** 
   * 隨機打亂一個數(shù)組 
   * 
   * @param array 
   * @return 
   */ 
  public int[] shuffle(int[] array) { 
    Random random = new Random(); 
    for (int index = array.length - 1; index >= 0; index--) { 
      // 從0到index處之間隨機取一個值，跟index處的元素交換 
      exchange(array, random.nextInt(index + 1), index); 
    } 
    return array; 
  } 
 
  // 交換位置 
  private void exchange(int[] array, int p1, int p2) { 
    int temp = array[p1]; 
    array[p1] = array[p2]; 
    array[p2] = temp; 
  } 
 
  /** 
   * 對兩個有序數(shù)組進行合并,并將重復(fù)的數(shù)字將其去掉 
   * 
   * @param a 
   *      ：已排好序的數(shù)組a 
   * @param b 
   *      ：已排好序的數(shù)組b 
   * @return 合并后的排序數(shù)組 
   */ 
  private static List<Integer> mergeByList(int[] a, int[] b) { 
    // 用于返回的新數(shù)組，長度可能不為a,b數(shù)組之和，因為可能有重復(fù)的數(shù)字需要去掉 
    List<Integer> c = new ArrayList<Integer>(); 
    // a數(shù)組下標(biāo) 
    int aIndex = 0; 
    // b數(shù)組下標(biāo) 
    int bIndex = 0; 
    // 對a、b兩數(shù)組的值進行比較，并將小的值加到c，并將該數(shù)組下標(biāo)+1， 
    // 如果相等，則將其任意一個加到c，兩數(shù)組下標(biāo)均+1 
    // 如果下標(biāo)超出該數(shù)組長度，則退出循環(huán) 
    while (true) { 
      if (aIndex > a.length - 1 || bIndex > b.length - 1) { 
        break; 
      } 
      if (a[aIndex] < b[bIndex]) { 
        c.add(a[aIndex]); 
        aIndex++; 
      } else if (a[aIndex] > b[bIndex]) { 
        c.add(b[bIndex]); 
        bIndex++; 
      } else { 
        c.add(a[aIndex]); 
        aIndex++; 
        bIndex++; 
      } 
    } 
    // 將沒有超出數(shù)組下標(biāo)的數(shù)組其余全部加到數(shù)組c中 
    // 如果a數(shù)組還有數(shù)字沒有處理 
    if (aIndex <= a.length - 1) { 
      for (int i = aIndex; i <= a.length - 1; i++) { 
        c.add(a[i]); 
      } 
      // 如果b數(shù)組中還有數(shù)字沒有處理 
    } else if (bIndex <= b.length - 1) { 
      for (int i = bIndex; i <= b.length - 1; i++) { 
        c.add(b[i]); 
      } 
    } 
    return c; 
  } 
 
  /** 
   * 對兩個有序數(shù)組進行合并,并將重復(fù)的數(shù)字將其去掉 
   * 
   * @param a 
   *      :已排好序的數(shù)組a 
   * @param b 
   *      :已排好序的數(shù)組b 
   * @return合并后的排序數(shù)組,返回數(shù)組的長度=a.length + b.length,不足部分補0 
   */ 
  private static int[] mergeByArray(int[] a, int[] b) { 
    int[] c = new int[a.length + b.length]; 
 
    int i = 0, j = 0, k = 0; 
 
    while (i < a.length && j < b.length) { 
      if (a[i] <= b[j]) { 
        if (a[i] == b[j]) { 
          j++; 
        } else { 
          c[k] = a[i]; 
          i++; 
          k++; 
        } 
      } else { 
        c[k] = b[j]; 
        j++; 
        k++; 
      } 
    } 
    while (i < a.length) { 
      c[k] = a[i]; 
      k++; 
      i++; 
    } 
    while (j < b.length) { 
      c[k] = b[j]; 
      j++; 
      k++; 
    } 
    return c; 
  } 
 
  /** 
   * 對兩個有序數(shù)組進行合并,并將重復(fù)的數(shù)字將其去掉 
   * 
   * @param a 
   *      ：可以是沒有排序的數(shù)組 
   * @param b 
   *      ：可以是沒有排序的數(shù)組 
   * @return合并后的排序數(shù)組 打印時可以這樣： Map<Integer,Integer> map=sortByTreeMap(a,b); 
   *         Iterator iterator = map.entrySet().iterator(); while 
   *         (iterator.hasNext()) { Map.Entry mapentry = 
   *         (Map.Entry)iterator.next(); 
   *         System.out.print(mapentry.getValue()+" "); } 
   */ 
  private static Map<Integer, Integer> mergeByTreeMap(int[] a, int[] b) { 
    Map<Integer, Integer> map = new TreeMap<Integer, Integer>(); 
    for (int i = 0; i < a.length; i++) { 
      map.put(a[i], a[i]); 
    } 
    for (int i = 0; i < b.length; i++) { 
      map.put(b[i], b[i]); 
    } 
    return map; 
  } 
 
  /** 
   * 在控制臺打印數(shù)組，之間用逗號隔開,調(diào)試時用 
   * 
   * @param array 
   */ 
  public static String print(int[] array) { 
    StringBuffer sb = new StringBuffer(); 
    for (int i = 0; i < array.length; i++) { 
      sb.append("," + array[i]); 
    } 
    System.out.println("\n"+sb.toString().substring(1)); 
    return sb.toString().substring(1); 
  } 
}