【转】Java工具类——数组操作ArrayUtil

package com.luang.util.common;import java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.Map;import java.util.Random;import java.util.TreeMap;/** *  * ArrayUtil.java * * &＃64;desc 数组操作工具 * &＃64;author Guoxp * &＃64;datatime Apr 7, 2013 4:03:49 PM * */public class ArrayUtil {        /**     * 排序算法的分类如下&＃xff1a;     * 1.插入排序&＃xff08;直接插入排序、折半插入排序、希尔排序&＃xff09;&＃xff1b;     * 2.交换排序&＃xff08;冒泡泡排序、快速排序&＃xff09;&＃xff1b;     * 3.选择排序&＃xff08;直接选择排序、堆排序&＃xff09;&＃xff1b;      * 4.归并排序&＃xff1b;      * 5.基数排序。     *     * 关于排序方法的选择&＃xff1a;     * (1)若n较小(如n≤50)&＃xff0c;可采用直接插入或直接选择排序。     * (2)若文件初始状态基本有序(指正序)&＃xff0c;则应选用直接插人、冒泡或随机的快速排序为宜&＃xff1b;     * (3)若n较大&＃xff0c;则应采用时间复杂度为O(nlgn)的排序方法&＃xff1a;快速排序、堆排序或归并排序。     *     */             /**      * 交换数组中两元素      *      * &＃64;since 1.1      * &＃64;param ints      *            需要进行交换操作的数组      * &＃64;param x      *            数组中的位置1      * &＃64;param y      *            数组中的位置2      * &＃64;return 交换后的数组      */      public static int[] swap(int[] ints, int x, int y) {          int temp &＃61; ints[x];          ints[x] &＃61; ints[y];          ints[y] &＃61; temp;          return ints;      }        /**      * 冒泡排序 方法&＃xff1a;相邻两元素进行比较 性能&＃xff1a;比较次数O(n^2),n^2/2&＃xff1b;交换次数O(n^2),n^2/4      *      * &＃64;since 1.1      * &＃64;param source      *            需要进行排序操作的数组      * &＃64;return 排序后的数组      */      public static int[] bubbleSort(int[] source) {          for (int i &＃61; 1; i for (int j &＃61; 0; j if (source[j] > source[j &＃43; 1]) {                      swap(source, j, j &＃43; 1);                  }              }          }          return source;      }        /**      * 直接选择排序法 方法&＃xff1a;每一趟从待排序的数据元素中选出最小&＃xff08;或最大&＃xff09;的一个元素&＃xff0c; 顺序放在已排好序的数列的最后&＃xff0c;直到全部待排序的数据元素排完。      * 性能&＃xff1a;比较次数O(n^2),n^2/2 交换次数O(n),n      * 交换次数比冒泡排序少多了&＃xff0c;由于交换所需CPU时间比比较所需的CUP时间多&＃xff0c;所以选择排序比冒泡排序快。      * 但是N比较大时&＃xff0c;比较所需的CPU时间占主要地位&＃xff0c;所以这时的性能和冒泡排序差不太多&＃xff0c;但毫无疑问肯定要快些。      *      * &＃64;since 1.1      * &＃64;param source      *            需要进行排序操作的数组      * &＃64;return 排序后的数组      */      public static int[] selectSort(int[] source) {            for (int i &＃61; 0; i for (int j &＃61; i &＃43; 1; j if (source[i] > source[j]) {                      swap(source, i, j);                  }              }          }          return source;      }        /**      * 插入排序 方法&＃xff1a;将一个记录插入到已排好序的有序表&＃xff08;有可能是空表&＃xff09;中,从而得到一个新的记录数增1的有序表。 性能&＃xff1a;比较次数O(n^2),n^2/4      * 复制次数O(n),n^2/4 比较次数是前两者的一般&＃xff0c;而复制所需的CPU时间较交换少&＃xff0c;所以性能上比冒泡排序提高一倍多&＃xff0c;而比选择排序也要快。      *      * &＃64;since 1.1      * &＃64;param source      *            需要进行排序操作的数组      * &＃64;return 排序后的数组      */      public static int[] insertSort(int[] source) {            for (int i &＃61; 1; i for (int j &＃61; i; (j > 0) && (source[j] 1]); j--) {                  swap(source, j, j - 1);              }          }          return source;      }        /**      * 快速排序 快速排序使用分治法&＃xff08;Divide and conquer&＃xff09;策略来把一个序列&＃xff08;list&＃xff09;分为两个子序列&＃xff08;sub-lists&＃xff09;。 步骤为&＃xff1a;      * 1. 从数列中挑出一个元素&＃xff0c;称为 "基准"&＃xff08;pivot&＃xff09;&＃xff0c; 2.      * 重新排序数列&＃xff0c;所有元素比基准值小的摆放在基准前面&＃xff0c;所有元素比基准值大的摆在基准的后面      * &＃xff08;相同的数可以到任一边&＃xff09;。在这个分割之后&＃xff0c;该基准是它的最后位置。这个称为分割&＃xff08;partition&＃xff09;操作。 3.      * 递归地&＃xff08;recursive&＃xff09;把小于基准值元素的子数列和大于基准值元素的子数列排序。      * 递回的最底部情形&＃xff0c;是数列的大小是零或一&＃xff0c;也就是永远都已经被排序好了      * 。虽然一直递回下去&＃xff0c;但是这个算法总会结束&＃xff0c;因为在每次的迭代&＃xff08;iteration&＃xff09;中&＃xff0c;它至少会把一个元素摆到它最后的位置去。      *      * &＃64;since 1.1      * &＃64;param source      *            需要进行排序操作的数组      * &＃64;return 排序后的数组      */      public static int[] quickSort(int[] source) {          return qsort(source, 0, source.length - 1);      }        /**      * 快速排序的具体实现&＃xff0c;排正序      *      * &＃64;since 1.1      * &＃64;param source      *            需要进行排序操作的数组      * &＃64;param low      *            开始低位      * &＃64;param high      *            结束高位      * &＃64;return 排序后的数组      */      private static int[] qsort(int source[], int low, int high) {          int i, j, x;          if (low while (i while (i x) {                      j--;                  }                  if (i while (i if (i 1);              qsort(source, i &＃43; 1, high);          }          return source;      }      ///      //排序算法结束      //      /**      * 二分法查找 查找线性表必须是有序列表      *      * &＃64;since 1.1      * &＃64;param source      *            需要进行查找操作的数组      * &＃64;param key      *            需要查找的值      * &＃64;return 需要查找的值在数组中的位置&＃xff0c;若未查到则返回-1      */      public static int binarySearch(int[] source, int key) {          int low &＃61; 0, high &＃61; source.length - 1, mid;          while (low <&＃61; high) {              mid &＃61; (low &＃43; high) >>> 1;              if (key &＃61;&＃61; source[mid]) {                  return mid;              } else if (key 1;              } else {                  low &＃61; mid &＃43; 1;              }          }          return -1;      }        /**      * 反转数组      *      * &＃64;since 1.1      * &＃64;param source      *            需要进行反转操作的数组      * &＃64;return 反转后的数组      */      public static int[] reverse(int[] source) {          int length &＃61; source.length;          int temp &＃61; 0;          for (int i &＃61; 0; i >1; i&＃43;&＃43;) {              temp &＃61; source[i];              source[i] &＃61; source[length - 1 - i];              source[length - 1 - i] &＃61; temp;          }          return source;      }     /**     * 在当前位置插入一个元素,数组中原有元素向后移动;     * 如果插入位置超出原数组&＃xff0c;则抛IllegalArgumentException异常     * &＃64;param array     * &＃64;param index     * &＃64;param insertNumber     * &＃64;return     */      public static int[] insert(int[] array, int index, int insertNumber) {          if (array &＃61;&＃61; null || array.length &＃61;&＃61; 0) {              throw new IllegalArgumentException();          }          if (index-1 > array.length || index <&＃61; 0) {              throw new IllegalArgumentException();          }          int[] dest&＃61;new int[array.length&＃43;1];          System.arraycopy(array, 0, dest, 0, index-1);          dest[index-1]&＃61;insertNumber;          System.arraycopy(array, index-1, dest, index, dest.length-index);          return dest;      }            /**      * 整形数组中特定位置删除掉一个元素,数组中原有元素向前移动;      * 如果插入位置超出原数组&＃xff0c;则抛IllegalArgumentException异常      * &＃64;param array      * &＃64;param index      * &＃64;return      */      public static int[] remove(int[] array, int index) {          if (array &＃61;&＃61; null || array.length &＃61;&＃61; 0) {              throw new IllegalArgumentException();          }          if (index > array.length || index <&＃61; 0) {              throw new IllegalArgumentException();          }          int[] dest&＃61;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个数组合并&＃xff0c;形成一个新的数组      * &＃64;param array1      * &＃64;param array2      * &＃64;return      */      public static int[] merge(int[] array1,int[] array2) {          int[] dest&＃61;new int[array1.length&＃43;array2.length];          System.arraycopy(array1, 0, dest, 0, array1.length);          System.arraycopy(array2, 0, dest, array1.length, array2.length);          return dest;      }    /**      * 数组中有n个数据&＃xff0c;要将它们顺序循环向后移动k位&＃xff0c;      * 即前面的元素向后移动k位&＃xff0c;后面的元素则循环向前移k位&＃xff0c;      * 例如&＃xff0c;0、1、2、3、4循环移动3位后为2、3、4、0、1。      * &＃64;param array      * &＃64;param offset      * &＃64;return      */      public static int[] offsetArray(int[] array,int offset){          int length &＃61; array.length;            int moveLength &＃61; length - offset;           int[] temp &＃61; Arrays.copyOfRange(array, moveLength, length);          System.arraycopy(array, 0, array, offset, moveLength);            System.arraycopy(temp, 0, array, 0, offset);          return array;      }      /**      * 随机打乱一个数组      * &＃64;param list      * &＃64;return      */      public static List shuffle(List list){          java.util.Collections.shuffle(list);          return list;      }        /**      * 随机打乱一个数组      * &＃64;param array      * &＃64;return      */      public int[] shuffle(int[] array) {          Random random &＃61; new Random();          for (int index &＃61; array.length - 1; index >&＃61; 0; index--) {              // 从0到index处之间随机取一个值&＃xff0c;跟index处的元素交换              exchange(array, random.nextInt(index &＃43; 1), index);          }          return array;      }        // 交换位置      private void exchange(int[] array, int p1, int p2) {          int temp &＃61; array[p1];          array[p1] &＃61; array[p2];          array[p2] &＃61; temp;      }  /**      * 对两个有序数组进行合并,并将重复的数字将其去掉      *       * &＃64;param a&＃xff1a;已排好序的数组a      * &＃64;param b&＃xff1a;已排好序的数组b      * &＃64;return 合并后的排序数组      */      private static List mergeByList(int[] a, int[] b) {          // 用于返回的新数组&＃xff0c;长度可能不为a,b数组之和&＃xff0c;因为可能有重复的数字需要去掉          List c &＃61; new ArrayList();          // a数组下标          int aIndex &＃61; 0;          // b数组下标          int bIndex &＃61; 0;          // 对a、b两数组的值进行比较&＃xff0c;并将小的值加到c&＃xff0c;并将该数组下标&＃43;1&＃xff0c;          // 如果相等&＃xff0c;则将其任意一个加到c&＃xff0c;两数组下标均&＃43;1          // 如果下标超出该数组长度&＃xff0c;则退出循环          while (true) {              if (aIndex > a.length - 1 || bIndex > b.length - 1) {                  break;              }              if (a[aIndex] else if (a[aIndex] > b[bIndex]) {                  c.add(b[bIndex]);                  bIndex&＃43;&＃43;;              } else {                  c.add(a[aIndex]);                  aIndex&＃43;&＃43;;                  bIndex&＃43;&＃43;;              }          }          // 将没有超出数组下标的数组其余全部加到数组c中          // 如果a数组还有数字没有处理          if (aIndex <&＃61; a.length - 1) {              for (int i &＃61; aIndex; i <&＃61; a.length - 1; i&＃43;&＃43;) {                  c.add(a[i]);              }              // 如果b数组中还有数字没有处理          } else if (bIndex <&＃61; b.length - 1) {              for (int i &＃61; bIndex; i <&＃61; b.length - 1; i&＃43;&＃43;) {                  c.add(b[i]);              }          }          return c;      }      /**      * 对两个有序数组进行合并,并将重复的数字将其去掉      * &＃64;param a:已排好序的数组a      * &＃64;param b:已排好序的数组b      * &＃64;return合并后的排序数组,返回数组的长度&＃61;a.length &＃43; b.length,不足部分补0      */      private static int[] mergeByArray(int[] a, int[] b){          int[] c &＃61; new int[a.length &＃43; b.length];            int i &＃61; 0, j &＃61; 0, k &＃61; 0;            while (i if (a[i] <&＃61; b[j]) {                  if (a[i] &＃61;&＃61; b[j]) {                      j&＃43;&＃43;;                  } else {                      c[k] &＃61; a[i];                      i&＃43;&＃43;;                      k&＃43;&＃43;;                  }              } else {                  c[k] &＃61; b[j];                  j&＃43;&＃43;;                  k&＃43;&＃43;;              }          }          while (i while (j return c;      }      /**      * 对两个有序数组进行合并,并将重复的数字将其去掉      * &＃64;param a&＃xff1a;可以是没有排序的数组      * &＃64;param b&＃xff1a;可以是没有排序的数组      * &＃64;return合并后的排序数组      * 打印时可以这样&＃xff1a;      * Map map&＃61;sortByTreeMap(a,b);         Iterator iterator &＃61;  map.entrySet().iterator();            while (iterator.hasNext()) {               Map.Entry mapentry &＃61; (Map.Entry)iterator.next();               System.out.print(mapentry.getValue()&＃43;" ");            }      */      private static Map mergeByTreeMap(int[] a, int[] b) {          Map map&＃61;new TreeMap();          for(int i&＃61;0;ifor(int i&＃61;0;ireturn map;      }      /**      * 在控制台打印数组&＃xff0c;之间用逗号隔开,调试时用      * &＃64;param array      */      public static String print(int[] array){          StringBuffer sb&＃61;new StringBuffer();          for(int i&＃61;0;i","&＃43;array[i]);          }          System.out.println(sb.toString().substring(1));          return sb.toString().substring(1);      }      public static void main(String[] args){          ArrayUtil util&＃61;new ArrayUtil();          int[] array0&＃61;{21,24,13,46,35,26,14,43,11};          int[] array1&＃61;{1,2,3,4,5,6};          int[] array2&＃61;{11,22,33,44,55,66};          int[] temp&＃61;util.quickSort(array0);          print(temp);                }  }  转自【http://blog.csdn.net/guoxuepeng123/article/details/8797920】