熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> Java編程 >> Java核心技術 >> 正文

自己編寫的Java數組操作工具

2013-11-23 19:23:04  來源: Java核心技術 

  看到網上的一段關於對數組操作的代碼覺得有用在此備用[java]

  import javautilArrayList;

  import javautilArrays;

  import javautilList;

  import javautilMap;

  import javautilRandom;

  import javautilTreeMap;

  /**

  * @desc 數組操作工具

  * @author OuyangPeng

  * @datatime ::

  *

  */

  public class MyArrayUtils {

  /**

  * 排序算法的分類如下 插入排序(直接插入排序折半插入排序希爾排序); 交換排序(冒泡泡排序快速排序);

  * 選擇排序(直接選擇排序堆排序); 歸並排序; 基數排序

  *

  * 關於排序方法的選擇 ()若n較小(如n≤)可采用直接插入或直接選擇排序

  * ()若文件初始狀態基本有序(指正序)則應選用直接插人冒泡或隨機的快速排序為宜;

  * ()若n較大則應采用時間復雜度為O(nlgn)的排序方法快速排序堆排序或歸並排序

  *

  */

  /**

  * 交換數組中兩元素

  *

  * @since

  * @param ints

  * 需要進行交換操作的數組

  * @param x

  * 數組中的位置

  * @param y

  * 數組中的位置

  * @return 交換後的數組

  */

  public static int[] swap(int[] ints int x int y) {

  int temp = ints[x];

  ints[x] = ints[y];

  ints[y] = temp;

  return ints;

  }

  /**

  * 冒泡排序方法:相鄰兩元素進行比較 性能比較次數O(n^)n^/;交換次數O(n^)n^/

  * 冒泡排序(Bubble Sort)是一種簡單的排序算法它重復地走訪過要排序的數列一次比較兩個元素

  * 如果他們的順序錯誤就把他們交換過來走訪數列的工作是重復地進行直到沒有再需要交換

  * 也就是說該數列已經排序完成這個算法的名字由來是因為越小的元素會經由交換慢慢到數列的頂端

  冒泡排序算法的運作如下:

   比較相鄰的元素如果第一個比第二個大就交換他們兩個

   對每一對相鄰元素作同樣的工作從開始第一對到結尾的最後一對在這一點最後的元素應該會是最大的數

   針對所有的元素重復以上的步驟除了最後一個

   持續每次對越來越少的元素重復上面的步驟直到沒有任何一對數字需要比較

  * @since

  * @param source

  * 需要進行排序操作的數組

  * @return 排序後的數組

  */

  public static int[] bubbleSort(int[] source) {

  /*for (int i = ; i < sourcelength ; i++) { // 最多做n趟排序

  for (int j = ; j < sourcelength i ; j++) { // 對當前無序區間score[lengthi]進行排序(j的范圍很關鍵這個范圍是在逐步縮小的)

  if (source[j] > source[j + ]) { // 把大的值交換到後面

  swap(source j j + );

  }

  }

  }*/

  for (int i = sourcelength ; i> ; i) {

  for (int j = ; j < i; j++) {

  if (source[j] > source[j + ]) {

  swap(source j j + );

  }

  }

  }

  return source;

  }

  /**

  * 選擇排序法 方法選擇排序(Selection sort)是一種簡單直觀的排序算法其平均時間復雜度為O(n)

  * 它的工作原理如下首先在未排序序列中找到最小元素存放到排序序列的起始位置然後

  * 再從剩余未排序元素中繼續尋找最小元素然後放到排序序列末尾以此類推直到所有元素均排序完畢

  * 性能選擇排序的交換操作介於和(n)次之間 選擇排序的比較操作為n(n)/次之間

  * 選擇排序的賦值操作介於(n)次之間其平均時間復雜度為O(n)

  * 交換次數比冒泡排序少多了由於交換所需CPU時間比比較所需的CUP時間多所以選擇排序比冒泡排序快

  * 但是N比較大時比較所需的CPU時間占主要地位所以這時的性能和冒泡排序差不太多但毫無疑問肯定要快些

  *

  * @since

  * @param source

  * 需要進行排序操作的數組

  * @return 排序後的數組

  */

  public static int[] selectSort(int[] source) {

  for (int i = ; i < sourcelength; i++) {

  for (int j = i + ; j < sourcelength; j++) {

  if (source[i] > source[j]) {

  swap(source i j);

  }

  }

  }

  return source;

  }

  /**

  * 插入排序 方法將一個記錄插入到已排好序的有序表(有可能是空表)中從而得到一個新的記錄數增的有序表 性能比較次數O(n^)n^/

  * 復制次數O(n)n^/ 比較次數是前兩者的一般而復制所需的CPU時間較交換少所以性能上比冒泡排序提高一倍多而比選擇排序也要快

  *

  * @since

  * @param source

  * 需要進行排序操作的數組

  * @return 排序後的數組

  */

  public static int[] insertSort(int[] source) {

  for (int i = ; i < sourcelength; i++) {

  for (int j = i; (j > ) && (source[j] < source[j ]); j) {

  swap(source j j );

  }

  }

  return source;

  }

  /**

  * 快速排序 快速排序使用分治法(Divide and conquer)策略來把一個序列(list)分為兩個子序列(sublists) 步驟為

  * 從數列中挑出一個元素稱為 基准(pivot)

  * 重新排序數列所有元素比基准值小的擺放在基准前面所有元素比基准值大的擺在基准的後面

  * (相同的數可以到任一邊)在這個分割之後該基准是它的最後位置這個稱為分割(partition)操作

  * 遞歸地(recursive)把小於基准值元素的子數列和大於基准值元素的子數列排序

  * 遞回的最底部情形是數列的大小是零或一也就是永遠都已經被排序好了

  * 雖然一直遞回下去但是這個算法總會結束因為在每次的迭代(iteration)中它至少會把一個元素擺到它最後的位置去

  *

  * @since

  * @param source

  * 需要進行排序操作的數組

  * @return 排序後的數組

  */

  public static int[] quickSort(int[] source) {

  return qsort(source sourcelength );

  }

  /**

  * 快速排序的具體實現排正序

  *

  * @since

  * @param source

  * 需要進行排序操作的數組

  * @param low

  * 開始低位

  * @param high

  * 結束高位

  * @return 排序後的數組

  */

  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 );

  qsort(source i + high);

  }

  return source;

  }

  // /////////////////////////////////////////////

  // 排序算法結束

  // ////////////////////////////////////////////

  /**

  * 二分法查找 查找線性表必須是有序列表

  *

  * @since

  * @param source

  * 需要進行查找操作的數組

  * @return 需要查找的值在數組中的位置若未查到則返回

  */

  public static int[] binarySearch(int[] source) {

  int ij;

  int low high mid;

  int temp;

  for (i = ; i < sourcelength; i++) {

  temp=source[i];

  low=;

  high=i;

  while (low <= high) {

  mid = (low + high)/;

  if (source[mid]>temp) {

  high=mid;

  } else {

  low = mid + ;

  }

  }

  for (j= i; j>high;j)

  source[j+]=source[j];

  source[high+]=temp;

  }

  return source;

  }

  /**

  * 反轉數組

  *

  * @since

  * @param source

  * 需要進行反轉操作的數組

  * @return 反轉後的數組

  */

  public static int[] reverse(int[] source) {

  int length = sourcelength;

  int temp = ;

  for (int i = ; i < length >> ; i++) {

  temp = source[i];

  source[i] = source[length i];

  source[length i] = temp;

  }

  return source;

  }

  /**

  * 在當前位置插入一個元素數組中原有元素向後移動; 如果插入位置超出原數組則拋IllegalArgumentException異常

  *

  * @param array

  * @param index

  * @param insertNumber

  * @return

  */

  public static int[] insert(int[] array int index int insertNumber) {

  if (array == null || arraylength == ) {

  throw new IllegalArgumentException();

  }

  if (index > arraylength || index <= ) {

  throw new IllegalArgumentException();

  }

  int[] dest = new int[arraylength + ];

  Systemarraycopy(array dest index );

  dest[index ] = insertNumber;

  Systemarraycopy(array index dest index destlength index);

  return dest;

  }

  /**

  * 整形數組中特定位置刪除掉一個元素數組中原有元素向前移動; 如果插入位置超出原數組則拋IllegalArgumentException異常

  *

  * @param array

  * @param index

  * @return

  */

  public static int[] remove(int[] array int index) {

  if (array == null || arraylength == ) {

  throw new IllegalArgumentException();

  }

  if (index > arraylength || index <= ) {

  throw new IllegalArgumentException();

  }

  int[] dest = new int[arraylength ];

  Systemarraycopy(array dest index );

  Systemarraycopy(array index dest index arraylength index);

  return dest;

  }

  /**

  * 個數組合並形成一個新的數組

  *

  * @param array

  * @param array

  * @return

  */

  public static int[] merge(int[] array int[] array) {

  int[] dest = new int[arraylength + arraylength];

  Systemarraycopy(array dest arraylength);

  Systemarraycopy(array dest arraylength arraylength);

  return dest;

  }

  /**

  * 數組中有n個數據要將它們順序循環向後移動k位 即前面的元素向後移動k位後面的元素則循環向前移k位

  * 例如循環移動位後為

  *

  * @param array

  * @param offset

  * @return

  */

  public static int[] offsetArray(int[] array int offset) {

  int length = arraylength;

  int moveLength = length offset;

  int[] temp = pyOfRange(array moveLength length);

  Systemarraycopy(array array offset moveLength);

  Systemarraycopy(temp array offset);

  return array;

  }

  /**

  * 隨機打亂一個數組

  *

  * @param list

  * @return

  */

  public static List shuffle(List list) {

  javautilCollectionsshuffle(list);

  return list;

  }

  /**

  * 隨機打亂一個數組

  *

  * @param array

  * @return

  */

  public int[] shuffle(int[] array) {

  Random random = new Random();

  for (int index = arraylength ; index >= ; index) {

  // 從到index處之間隨機取一個值跟index處的元素交換

  exchange(array randomnextInt(index + ) index);

  }

  return array;

  }

  // 交換位置

  private void exchange(int[] array int p int p) {

  int temp = array[p];

  array[p] = array[p];

  array[p] = temp;

  }

  /**

  * 對兩個有序數組進行合並並將重復的數字將其去掉

  *

  * @param a

  * 已排好序的數組a

  * @param b

  * 已排好序的數組b

  * @return 合並後的排序數組

  */

  private static List mergeByList(int[] a int[] b) {

  // 用於返回的新數組長度可能不為ab數組之和因為可能有重復的數字需要去掉

  List c = new ArrayList();

  // a數組下標

  int aIndex = ;

  // b數組下標

  int bIndex = ;

  // 對ab兩數組的值進行比較並將小的值加到c並將該數組下標+

  // 如果相等則將其任意一個加到c兩數組下標均+

  // 如果下標超出該數組長度則退出循環

  while (true) {

  if (aIndex > alength || bIndex > blength ) {

  break;

  }

  if (a[aIndex] < b[bIndex]) {

  cadd(a[aIndex]);

  aIndex++;

  } else if (a[aIndex] > b[bIndex]) {

  cadd(b[bIndex]);

  bIndex++;

  } else {

  cadd(a[aIndex]);

  aIndex++;

  bIndex++;

  }

  }

  // 將沒有超出數組下標的數組其余全部加到數組c中

  // 如果a數組還有數字沒有處理

  if (aIndex <= alength ) {

  for (int i = aIndex; i <= alength ; i++) {

  cadd(a[i]);

  }

  // 如果b數組中還有數字沒有處理

  } else if (bIndex <= blength ) {

  for (int i = bIndex; i <= blength ; i++) {

  cadd(b[i]);

  }

  }

  return c;

  }

  /**

  * 對兩個有序數組進行合並並將重復的數字將其去掉

  *

  * @param a

  * :已排好序的數組a

  * @param b

  * :已排好序的數組b

  * @return合並後的排序數組返回數組的長度=alength + blength不足部分補

  */

  private static int[] mergeByArray(int[] a int[] b) {

  int[] c = new int[alength + blength];

  int i = j = k = ;

  while (i < alength && j < blength) {

  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 < alength) {

  c[k] = a[i];

  k++;

  i++;

  }

  while (j < blength) {

  c[k] = b[j];

  j++;

  k++;

  }

  return c;

  }

  /**

  * 對兩個有序數組進行合並並將重復的數字將其去掉

  *

  * @param a

  * 可以是沒有排序的數組

  * @param b

  * 可以是沒有排序的數組

  * @return合並後的排序數組 打印時可以這樣 Map map=sortByTreeMap(ab);

  * Iterator iterator = mapentrySet(erator(); while

  * (iteratorhasNext()) { MapEntry mapentry =

  * (MapEntry)iteratornext();

  * Systemoutprint(mapentrygetValue()+ ); }

  */

  private static Map mergeByTreeMap(int[] a int[] b) {

  Map map = new TreeMap();

  for (int i = ; i < alength; i++) {

  mapput(a[i] a[i]);

  }

  for (int i = ; i < blength; i++) {

  mapput(b[i] b[i]);

  }

  return map;

  }

  /**

  * 在控制台打印數組之間用逗號隔開調試時用

  *

  * @param array

  */

  public static String print(int[] array) {

  StringBuffer sb = new StringBuffer();

  for (int i = ; i < arraylength; i++) {

  sbappend( + array[i]);

  }

  Systemoutprintln(\n+sbtoString()substring());

  return sbtoString()substring();

  }

  }


From:http://tw.wingwit.com/Article/program/Java/hx/201311/26760.html
  • 上一篇文章:

  • 下一篇文章:
  • 推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.