看到网上的一段关于对数组操作的代码觉得有用在此备用[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();
}
}
