Java development learning Java array manipulation tools
- 2020-06-19 10:12:47
- OfStack
See 1 section of the network on the operation of the array code, feel useful, here spare.
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.TreeMap;
/**
* @desc Array manipulation tool
* @author OuyangPeng
* @datatime 2013-5-11 10:31:02
*
*/
public class MyArrayUtils {
/**
* Sorting algorithms are classified as follows: 1. Insertion sort (direct insertion sort, half insertion sort, Hill sort); 2. Exchange sort (bubble sort, quick sort);
* 3. Select sort (direct select sort, heap sort); 4. Merge sort; 5. Radix sort.
*
* Selection of sorting methods: (1) if n smaller ( Such as n Or less 50) , can be directly inserted or directly selected sort.
* (2) If the initial state of the file is basically ordered ( The correct sequence ) , it is advisable to use direct insertion, bubbling or random quicksort;
* (3) if n Is large, the time complexity should be O(nlgn) Sort by quicksort, heap sort, or merge sort.
*
*/
/**
* Swap the two elements of an array
*
* @since 1.1
* @param ints
* Arrays that need to be swapped
* @param x
* Position in array 1
* @param y
* Position in array 2
* @return The swapped array
*/
public static int[] swap(int[] ints, int x, int y) {
int temp = ints[x];
ints[x] = ints[y];
ints[y] = temp;
return ints;
}
/**
* Bubble sort method : The two adjacent elements are compared Performance: Comparison times O(n^2),n^2/2 ; Switching frequency O(n^2),n^2/4<br>
* Bubble sort ( Bubble Sort ) is 1 A simple sorting algorithm. It repeatedly visits the sequence to be sorted, 1 To subcompare two elements, <br>
* If they're in the wrong order, swap them. The job of visiting the sequence is to repeat it until no exchange is needed, <br>
* So the sequence is sorted. The algorithm's name comes from the fact that the smaller the element, the smaller it is, floats slowly to the top of the list. <br>
The bubble sort algorithm works as follows :<br>
1. Compare adjacent elements. If the first 1 Than the first 2 Big, just swap them both. <br>
2. For each 1 Do the same thing for adjacent elements, starting at no 1 To the end of the end 1 right In this 1 Point, the last element should be the largest. <br>
3. Repeat the above steps for all elements except the last 1 A. <br>
4. Repeat the above steps for fewer and fewer elements each time until there are no more 1 The Numbers need to be compared. <br>
* @since 1.1
* @param source
* The array that needs to be sorted
* @return Sorted array
*/
public static int[] bubbleSort(int[] source) {
/*for (int i = 0; i < source.length - 1; i++) { // Most do n-1 Trip to sort
for (int j = 0; j < source.length - i - 1; j++) { // For the current unordered interval score[0......length-i-1] sorting (j The range is critical, and it's narrowing down )
if (source[j] > source[j + 1]) { // Swap the large value to the end
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;
}
/**
* Selective sorting Method: Select sort (Selection sort) is 1 The average time complexity of a simple and intuitive sorting algorithm is O(n2) .
* Here's how it works. Find the smallest element in the unsorted sequence, store it at the beginning of the sorted sequence, and then,
* From the remaining unsorted elements, continue to find the smallest element, and then put it at the end of the sorting sequence. And so on until all the elements are sorted.
* Performance: Select the sort of exchange operation between 0 and (n-1) Between the time, The comparison operation for select sort is n(n-1)/2 Between the time,
* The assignment operation for select sort is intermediate 0 and 3(n-1) The average time complexity is O(n2)
* The number of exchanges is much less than bubble sort because the exchanges are required CPU Time ratio to compare required CUP More time, so selection sort is faster than bubble sort.
* but N When it's larger, compare what you need CPU Time predominates, so the performance isn't too different from bubble sort, but it's definitely faster.
*
* @since 1.1
* @param source
* The array that needs to be sorted
* @return Sorted array
*/
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;
}
/**
* Insertion sort Methods: 1 Two records are inserted into an ordered (possibly empty) table , To get 1 New record number increase 1 In order. Performance: Comparison times O(n^2),n^2/4
* Copy number O(n),n^2/4 The comparison is between the first two 1 Like, while copying required CPU The time is less than swap, so the performance is better than bubble sort 1 It's twice as much, and it's faster than selective sorting.
*
* @since 1.1
* @param source
* The array that needs to be sorted
* @return Sorted array
*/
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;
}
/**
* Quick sort Quick sort USES divide and conquer ( Divide and conquer (Tactics come on 1 A sequence, list ) is divided into two subsequences ( sub-lists ). Steps as follows:
* 1. Pick it out from the list 1 The number of elements is called " The benchmark " ( pivot ), 2.
* Reorder the sequence so that all elements smaller than the base value are placed before the base value and all elements larger than the base value are placed after the base value
* The same number can be used anywhere 1 Edge). After this split, the benchmark is its last position. This is called segmentation ( partition ) operation. 3.
* Recursively ( recursive ) to sort the subsequences of elements below the base value and those above the base value.
* The bottom case of the recursion is that the size of the sequence is zero or zero 1 It's always sorted
* . although 1 But the algorithm always ends because in each iteration ( iteration ), it will at least put 1 Put the element in its last position.
*
* @since 1.1
* @param source
* The array that needs to be sorted
* @return Sorted array
*/
public static int[] quickSort(int[] source) {
return qsort(source, 0, source.length - 1);
}
/**
* Quick sort of concrete implementation, sorted positive order
*
* @since 1.1
* @param source
* The array that needs to be sorted
* @param low
* Start low
* @param high
* The end of the high
* @return Sorted array
*/
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;
}
// /////////////////////////////////////////////
// End of sorting algorithm
// ////////////////////////////////////////////
/**
* 2 Points method lookup The lookup linear table must be an ordered list
*
* @since 1.1
* @param source
* The array that needs to be searched
* @return The position of the value to be looked up in the array, or returned if not found -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;
}
/**
* Inversion array
*
* @since 1.1
* @param source
* The array that needs to be reversed
* @return The reversed array
*/
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;
}
/**
* Insert in the current position 1 An element , The original elements in the array are moved backwards ; If the insert position is outside the original array, it is thrown IllegalArgumentException abnormal
*
* @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;
}
/**
* Removes a specific position in the plastic array 1 An element , The original element in the array moves forward ; If the insert position is outside the original array, it is thrown IllegalArgumentException abnormal
*
* @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 A combination of Numbers to form 1 A new array
*
* @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;
}
/**
* There are in the array n I'm going to loop them back in order k position The previous element moves backwards k Bits, and the next element loops forward k position
* For example, 0 , 1 , 2 , 3 , 4 Recycling mobile 3 After a for 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;
}
/**
* Random disturb 1 An array
*
* @param list
* @return
*/
public static List shuffle(List list) {
java.util.Collections.shuffle(list);
return list;
}
/**
* Random disturb 1 An array
*
* @param array
* @return
*/
public int[] shuffle(int[] array) {
Random random = new Random();
for (int index = array.length - 1; index >= 0; index--) {
// from 0 to index Random between 1 A value, with index Exchange of elements at
exchange(array, random.nextInt(index + 1), index);
}
return array;
}
// Swap places
private void exchange(int[] array, int p1, int p2) {
int temp = array[p1];
array[p1] = array[p2];
array[p2] = temp;
}
/**
* Merge two ordered arrays , And delete the duplicate number
*
* @param a
* : An sorted array a
* @param b
* : An sorted array b
* @return The sorted array after merging
*/
private static List<Integer> mergeByList(int[] a, int[] b) {
// For a new array to return, the length may not be a,b The sum of the arrays, because there may be duplicate Numbers that need to be removed
List<Integer> c = new ArrayList<Integer>();
// a The array subscript
int aIndex = 0;
// b The array subscript
int bIndex = 0;
// right a , b Compare the values of the two arrays and add the smaller values to c , and subscript the array +1 .
// If they are equal, make them arbitrary 1 An added to the c , both array indices +1
// If the index exceeds the length of the array, exit the loop
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++;
}
}
// Adds the rest of the array that does not exceed the array index to the array c In the
// if a The array still has Numbers to work with
if (aIndex <= a.length - 1) {
for (int i = aIndex; i <= a.length - 1; i++) {
c.add(a[i]);
}
// if b There are still Numbers in the array that have not been processed
} else if (bIndex <= b.length - 1) {
for (int i = bIndex; i <= b.length - 1; i++) {
c.add(b[i]);
}
}
return c;
}
/**
* Merge two ordered arrays , And delete the duplicate number
*
* @param a
* : An sorted array a
* @param b
* : An sorted array b
* @return The sorted array after merging , Returns the length of the array =a.length + b.length, Deficiency partial compensation 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;
}
/**
* Merge two ordered arrays , And delete the duplicate number
*
* @param a
* : Can be an array without sorting
* @param b
* : Can be an array without sorting
* @return The sorted array after merging Print like this: 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;
}
/**
* Print arrays in the console, separated by commas , Used when debugging
*
* @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);
}
}