Java Tutorial/Collections/Array Sort Search — различия между версиями
Admin (обсуждение | вклад) м (1 версия) |
|
(нет различий)
|
Текущая версия на 08:04, 1 июня 2010
Содержание
- 1 FastQSorts the [l,r] partition (inclusive) of the specfied array of Rows, using the comparator.
- 2 Finds the index of the given object in the array.
- 3 Finds the index of the given object in the array starting at the given index.
- 4 Finds the last index of the given object in the array starting at the given index.
- 5 Finds the value in the range (start,limit) of the largest element (rank) where the count of all smaller elements in that range is less than or equals target.
- 6 Get the element index or last index among a boolean type array
- 7 Get the index and last index of an int type value array
- 8 Object Arrays: Searching for elements in a sorted object array
- 9 Produces a new array containing the elements between the start and end indices.
- 10 Returns an index into arra (or -1) where the character is not in the charset byte array.
- 11 Returns an int[] array of length segments containing the distribution count of the elements in unsorted int[] array with values between min and max (range).
- 12 Returns the minimum value in an array.
- 13 Returns true if all the references in array1 are equal to all the references in array2 (two null references are considered equal for this test).
- 14 Searching Arrays
- 15 Sort array utilities
- 16 Sorting Arrays
- 17 Sorting arrays of objects
- 18 Sorting a subset of array elements
- 19 Test the equality of two object arrays
FastQSorts the [l,r] partition (inclusive) of the specfied array of Rows, using the comparator.
<source lang="java">
/* Copyright (c) 1995-2000, The Hypersonic SQL Group.
* All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: * * Redistributions of source code must retain the above copyright notice, this * list of conditions and the following disclaimer. * * Redistributions in binary form must reproduce the above copyright notice, * this list of conditions and the following disclaimer in the documentation * and/or other materials provided with the distribution. * * Neither the name of the Hypersonic SQL Group nor the names of its * contributors may be used to endorse or promote products derived from this * software without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE HYPERSONIC SQL GROUP, * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * * This software consists of voluntary contributions made by many individuals * on behalf of the Hypersonic SQL Group. * * * For work added by the HSQL Development Group: * * Copyright (c) 2001-2009, The HSQL Development Group * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: * * Redistributions of source code must retain the above copyright notice, this * list of conditions and the following disclaimer. * * Redistributions in binary form must reproduce the above copyright notice, * this list of conditions and the following disclaimer in the documentation * and/or other materials provided with the distribution. * * Neither the name of the HSQL Development Group nor the names of its * contributors may be used to endorse or promote products derived from this * software without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG, * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */
/**
* FastQSorts the [l,r] partition (inclusive) of the specfied array of Rows, * using the comparator. * * Modified from the original method in Hypersonic with the addition of the * comparator. (fredt@users) * * @author Thomas Mueller (Hypersonic SQL Group) * @version 1.7.2 * @since 1.7.2 */
public class Sort {
public static final void sort(Object[] w, ObjectComparator comparator, int l, int r) { int i; int j; Object p; if (l > r) { return; } while (r - l > 10) { i = (r + l) >>> 1; if (comparator.rupare(w[l], w[r]) > 0) { swap(w, l, r); } if (comparator.rupare(w[i], w[l]) < 0) { swap(w, l, i); } else if (comparator.rupare(w[i], w[r]) > 0) { swap(w, i, r); } j = r - 1; swap(w, i, j); p = w[j]; i = l; while (true) { while (comparator.rupare(w[++i], p) < 0) { ; } while (comparator.rupare(w[--j], p) > 0) { ; } if (i >= j) { break; } swap(w, i, j); } swap(w, i, r - 1); sort(w, comparator, l, i - 1); l = i + 1; } for (i = l + 1; i <= r; i++) { Object t = w[i]; for (j = i - 1; j >= l && comparator.rupare(w[j], t) > 0; j--) { w[j + 1] = w[j]; } w[j + 1] = t; } } /** * Swaps the a"th and b"th elements of the specified Row array. */ private static void swap(Object[] w, int a, int b) { Object t = w[a]; w[a] = w[b]; w[b] = t; }
} interface ObjectComparator {
int compare(Object a, Object b);
}</source>
Finds the index of the given object in the array.
<source lang="java">
/* Copyright 2004 The Apache Software Foundation
* * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */
import java.lang.reflect.Array;
/**
* Operations on arrays, primitive arrays (likeint[]
) and * primitive wrapper arrays (likeInteger[]
). * * This class tries to handlenull
input gracefully. * An exception will not be thrown for anull
* array input. However, an Object array that contains anull
* element may throw an exception. Each method documents its behaviour. * * @author Stephen Colebourne * @author Moritz Petersen * @author * @author Maarten Coene * @since 2.0 * @version $Id: ArrayUtils.java 632503 2008-03-01 00:21:52Z ggregory $ */
public class Main {
/** * Finds the index of the given object in the array. * * This method returns {@link #INDEX_NOT_FOUND} (-1
) for anull
input array. * * @param array the array to search through for the object, may benull
* @param objectToFind the object to find, may benull
* @return the index of the object within the array, * {@link #INDEX_NOT_FOUND} (-1
) if not found ornull
array input */ public static int indexOf(Object[] array, Object objectToFind) { return indexOf(array, objectToFind, 0); } /** * Finds the index of the given object in the array starting at the given index. * * This method returns {@link #INDEX_NOT_FOUND} (-1
) for anull
input array. * * A negative startIndex is treated as zero. A startIndex larger than the array * length will return {@link #INDEX_NOT_FOUND} (-1
). * * @param array the array to search through for the object, may benull
* @param objectToFind the object to find, may benull
* @param startIndex the index to start searching at * @return the index of the object within the array starting at the index, * {@link #INDEX_NOT_FOUND} (-1
) if not found ornull
array input */ public static int indexOf(Object[] array, Object objectToFind, int startIndex) { if (array == null) { return -1; } if (startIndex < 0) { startIndex = 0; } if (objectToFind == null) { for (int i = startIndex; i < array.length; i++) { if (array[i] == null) { return i; } } } else { for (int i = startIndex; i < array.length; i++) { if (objectToFind.equals(array[i])) { return i; } } } return -1; }
}</source>
Finds the index of the given object in the array starting at the given index.
<source lang="java">
/* Copyright 2004 The Apache Software Foundation
* * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */
import java.lang.reflect.Array;
/**
* Operations on arrays, primitive arrays (likeint[]
) and * primitive wrapper arrays (likeInteger[]
). * * This class tries to handlenull
input gracefully. * An exception will not be thrown for anull
* array input. However, an Object array that contains anull
* element may throw an exception. Each method documents its behaviour. * * @author Stephen Colebourne * @author Moritz Petersen * @author * @author Maarten Coene * @since 2.0 * @version $Id: ArrayUtils.java 632503 2008-03-01 00:21:52Z ggregory $ */
public class Main {
/** * Finds the index of the given object in the array starting at the given index. * * This method returns {@link #INDEX_NOT_FOUND} (-1
) for anull
input array. * * A negative startIndex is treated as zero. A startIndex larger than the array * length will return {@link #INDEX_NOT_FOUND} (-1
). * * @param array the array to search through for the object, may benull
* @param objectToFind the object to find, may benull
* @param startIndex the index to start searching at * @return the index of the object within the array starting at the index, * {@link #INDEX_NOT_FOUND} (-1
) if not found ornull
array input */ public static int indexOf(Object[] array, Object objectToFind, int startIndex) { if (array == null) { return -1; } if (startIndex < 0) { startIndex = 0; } if (objectToFind == null) { for (int i = startIndex; i < array.length; i++) { if (array[i] == null) { return i; } } } else { for (int i = startIndex; i < array.length; i++) { if (objectToFind.equals(array[i])) { return i; } } } return -1; }
}</source>
Finds the last index of the given object in the array starting at the given index.
<source lang="java">
/* Copyright 2004 The Apache Software Foundation
* * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */
import java.lang.reflect.Array;
/**
* Operations on arrays, primitive arrays (likeint[]
) and * primitive wrapper arrays (likeInteger[]
). * * This class tries to handlenull
input gracefully. * An exception will not be thrown for anull
* array input. However, an Object array that contains anull
* element may throw an exception. Each method documents its behaviour. * * @author Stephen Colebourne * @author Moritz Petersen * @author * @author Maarten Coene * @since 2.0 * @version $Id: ArrayUtils.java 632503 2008-03-01 00:21:52Z ggregory $ */
public class Main {
/** * Finds the last index of the given object in the array starting at the given index. * * This method returns {@link #INDEX_NOT_FOUND} (-1
) for anull
input array. * * A negative startIndex will return {@link #INDEX_NOT_FOUND} (-1
). A startIndex larger than * the array length will search from the end of the array. * * @param array the array to traverse for looking for the object, may benull
* @param objectToFind the object to find, may benull
* @param startIndex the start index to travers backwards from * @return the last index of the object within the array, * {@link #INDEX_NOT_FOUND} (-1
) if not found ornull
array input */ public static int lastIndexOf(Object[] array, Object objectToFind, int startIndex) { if (array == null) { return -1; } if (startIndex < 0) { return -1; } else if (startIndex >= array.length) { startIndex = array.length - 1; } if (objectToFind == null) { for (int i = startIndex; i >= 0; i--) { if (array[i] == null) { return i; } } } else { for (int i = startIndex; i >= 0; i--) { if (objectToFind.equals(array[i])) { return i; } } } return -1; }
}</source>
Finds the value in the range (start,limit) of the largest element (rank) where the count of all smaller elements in that range is less than or equals target.
<source lang="java">
/* Copyright (c) 2001-2009, The HSQL Development Group
* All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: * * Redistributions of source code must retain the above copyright notice, this * list of conditions and the following disclaimer. * * Redistributions in binary form must reproduce the above copyright notice, * this list of conditions and the following disclaimer in the documentation * and/or other materials provided with the distribution. * * Neither the name of the HSQL Development Group nor the names of its * contributors may be used to endorse or promote products derived from this * software without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG, * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */
/**
* Collection of routines for counting the distribution of the values * in an int[] array. * * @author Fred Toussi (fredt@users dot sourceforge.net) * @version 1.7.2 * @since 1.7.2 */
public class ArrayCounter {
/** * Returns an int[] array of length segments containing the distribution * count of the elements in unsorted int[] array with values between min * and max (range). Values outside the min-max range are ignored * * A usage example is determining the count of people of each age group * in a large int[] array containing the age of each person. Called with * (array, 16,0,79), it will return an int[16] with the first element * the count of people aged 0-4, the second element the count of those * aged 5-9, and so on. People above the age of 79 are excluded. If the * range is not a multiple of segments, the last segment will be cover a * smaller sub-range than the rest. * */ public static int[] countSegments(int[] array, int elements, int segments, int start, int limit) { int[] counts = new int[segments]; long interval = calcInterval(segments, start, limit); int index = 0; int element = 0; if (interval <= 0) { return counts; } for (int i = 0; i < elements; i++) { element = array[i]; if (element < start || element >= limit) { continue; } index = (int) ((element - start) / interval); counts[index]++; } return counts; } /** * With an unsorted int[] array and with target a positive integer in the * range (1,array.length), finds the value in the range (start,limit) of the * largest element (rank) where the count of all smaller elements in that * range is less than or equals target. Parameter margin indicates the * margin of error in target * * In statistics, this can be used to calculate a median or quadrile value. * A usage example applied to an array of age values is to determine * the maximum age of a given number of people. With the example array * given in countSegments, rank(array, c, 6000, 18, 65, 0) will return an age * value between 18-64 (inclusive) and the count of all people aged between * 18 and the returned value(exclusive) will be less than or equal 6000. * */ public static int rank(int[] array, int elements, int target, int start, int limit, int margin) { final int segments = 256; int elementCount = 0; int currentLimit = limit; for (;;) { long interval = calcInterval(segments, start, currentLimit); int[] counts = countSegments(array, elements, segments, start, currentLimit); for (int i = 0; i < counts.length; i++) { if (elementCount + counts[i] < target) { elementCount += counts[i]; start += interval; } else { break; } } if (elementCount + margin >= target) { return start; } if (interval <= 1) { return start; } currentLimit = start + interval < limit ? (int) (start + interval) : limit; } } /** * Helper method to calculate the span of the sub-interval. Simply returns * the cieling of ((limit - start) / segments) and accounts for invalid * start and limit combinations. */ static long calcInterval(int segments, int start, int limit) { long range = limit - start; if (range < 0) { return 0; } int partSegment = (range % segments) == 0 ? 0 : 1; return (range / segments) + partSegment; }
}</source>
Get the element index or last index among a boolean type array
<source lang="java">
/* Copyright 2004 The Apache Software Foundation
* * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */
import java.lang.reflect.Array;
/**
* Operations on arrays, primitive arrays (likeint[]
) and * primitive wrapper arrays (likeInteger[]
). * * This class tries to handlenull
input gracefully. * An exception will not be thrown for anull
* array input. However, an Object array that contains anull
* element may throw an exception. Each method documents its behaviour. * * @author Stephen Colebourne * @author Moritz Petersen * @author * @author Maarten Coene * @since 2.0 * @version $Id: ArrayUtils.java 632503 2008-03-01 00:21:52Z ggregory $ */
public class Main {
/** * The index value when an element is not found in a list or array:-1
. * This value is returned by methods in this class and can also be used in comparisons with values returned by * various method from {@link java.util.List}. */ public static final int INDEX_NOT_FOUND = -1; // boolean IndexOf //----------------------------------------------------------------------- /** * Finds the index of the given value in the array. * * This method returns {@link #INDEX_NOT_FOUND} (-1
) for anull
input array. * * @param array the array to search through for the object, may benull
* @param valueToFind the value to find * @return the index of the value within the array, * {@link #INDEX_NOT_FOUND} (-1
) if not found ornull
array input */ public static int indexOf(boolean[] array, boolean valueToFind) { return indexOf(array, valueToFind, 0); } /** * Finds the index of the given value in the array starting at the given index. * * This method returns {@link #INDEX_NOT_FOUND} (-1
) for anull
input array. * * A negative startIndex is treated as zero. A startIndex larger than the array * length will return {@link #INDEX_NOT_FOUND} (-1
). * * @param array the array to search through for the object, may benull
* @param valueToFind the value to find * @param startIndex the index to start searching at * @return the index of the value within the array, * {@link #INDEX_NOT_FOUND} (-1
) if not found ornull
* array input */ public static int indexOf(boolean[] array, boolean valueToFind, int startIndex) { if (isEmpty(array)) { return INDEX_NOT_FOUND; } if (startIndex < 0) { startIndex = 0; } for (int i = startIndex; i < array.length; i++) { if (valueToFind == array[i]) { return i; } } return INDEX_NOT_FOUND; } /** * Finds the last index of the given value within the array. * * This method returns {@link #INDEX_NOT_FOUND} (-1
) if *null
array input. * * @param array the array to travers backwords looking for the object, may benull
* @param valueToFind the object to find * @return the last index of the value within the array, * {@link #INDEX_NOT_FOUND} (-1
) if not found ornull
array input */ public static int lastIndexOf(boolean[] array, boolean valueToFind) { return lastIndexOf(array, valueToFind, Integer.MAX_VALUE); } /** * Finds the last index of the given value in the array starting at the given index. * * This method returns {@link #INDEX_NOT_FOUND} (-1
) for anull
input array. * * A negative startIndex will return {@link #INDEX_NOT_FOUND} (-1
). A startIndex larger than * the array length will search from the end of the array. * * @param array the array to traverse for looking for the object, may benull
* @param valueToFind the value to find * @param startIndex the start index to travers backwards from * @return the last index of the value within the array, * {@link #INDEX_NOT_FOUND} (-1
) if not found ornull
array input */ public static int lastIndexOf(boolean[] array, boolean valueToFind, int startIndex) { if (isEmpty(array)) { return INDEX_NOT_FOUND; } if (startIndex < 0) { return INDEX_NOT_FOUND; } else if (startIndex >= array.length) { startIndex = array.length - 1; } for (int i = startIndex; i >= 0; i--) { if (valueToFind == array[i]) { return i; } } return INDEX_NOT_FOUND; } /** * Checks if the value is in the given array. * * The method returnsfalse
if anull
array is passed in. * * @param array the array to search through * @param valueToFind the value to find * @returntrue
if the array contains the object */ public static boolean contains(boolean[] array, boolean valueToFind) { return indexOf(array, valueToFind) != INDEX_NOT_FOUND; }
/** * Checks if an array of primitive doubles is empty ornull
. * * @param array the array to test * @returntrue
if the array is empty ornull
* @since 2.1 */ public static boolean isEmpty(boolean[] array) { if (array == null || array.length == 0) { return true; } return false; }
}</source>
Get the index and last index of an int type value array
<source lang="java">
/* Copyright 2004 The Apache Software Foundation
* * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */
import java.lang.reflect.Array;
/**
* Operations on arrays, primitive arrays (likeint[]
) and * primitive wrapper arrays (likeInteger[]
). * * This class tries to handlenull
input gracefully. * An exception will not be thrown for anull
* array input. However, an Object array that contains anull
* element may throw an exception. Each method documents its behaviour. * * @author Stephen Colebourne * @author Moritz Petersen * @author * @author Maarten Coene * @since 2.0 * @version $Id: ArrayUtils.java 632503 2008-03-01 00:21:52Z ggregory $ */
public class Main {
/** * The index value when an element is not found in a list or array:-1
. * This value is returned by methods in this class and can also be used in comparisons with values returned by * various method from {@link java.util.List}. */ public static final int INDEX_NOT_FOUND = -1; // int IndexOf //----------------------------------------------------------------------- /** * Finds the index of the given value in the array. * * This method returns {@link #INDEX_NOT_FOUND} (-1
) for anull
input array. * * @param array the array to search through for the object, may benull
* @param valueToFind the value to find * @return the index of the value within the array, * {@link #INDEX_NOT_FOUND} (-1
) if not found ornull
array input */ public static int indexOf(int[] array, int valueToFind) { return indexOf(array, valueToFind, 0); } /** * Finds the index of the given value in the array starting at the given index. * * This method returns {@link #INDEX_NOT_FOUND} (-1
) for anull
input array. * * A negative startIndex is treated as zero. A startIndex larger than the array * length will return {@link #INDEX_NOT_FOUND} (-1
). * * @param array the array to search through for the object, may benull
* @param valueToFind the value to find * @param startIndex the index to start searching at * @return the index of the value within the array, * {@link #INDEX_NOT_FOUND} (-1
) if not found ornull
array input */ public static int indexOf(int[] array, int valueToFind, int startIndex) { if (array == null) { return INDEX_NOT_FOUND; } if (startIndex < 0) { startIndex = 0; } for (int i = startIndex; i < array.length; i++) { if (valueToFind == array[i]) { return i; } } return INDEX_NOT_FOUND; } /** * Finds the last index of the given value within the array. * * This method returns {@link #INDEX_NOT_FOUND} (-1
) for anull
input array. * * @param array the array to travers backwords looking for the object, may benull
* @param valueToFind the object to find * @return the last index of the value within the array, * {@link #INDEX_NOT_FOUND} (-1
) if not found ornull
array input */ public static int lastIndexOf(int[] array, int valueToFind) { return lastIndexOf(array, valueToFind, Integer.MAX_VALUE); } /** * Finds the last index of the given value in the array starting at the given index. * * This method returns {@link #INDEX_NOT_FOUND} (-1
) for anull
input array. * * A negative startIndex will return {@link #INDEX_NOT_FOUND} (-1
). A startIndex larger than the * array length will search from the end of the array. * * @param array the array to traverse for looking for the object, may benull
* @param valueToFind the value to find * @param startIndex the start index to travers backwards from * @return the last index of the value within the array, * {@link #INDEX_NOT_FOUND} (-1
) if not found ornull
array input */ public static int lastIndexOf(int[] array, int valueToFind, int startIndex) { if (array == null) { return INDEX_NOT_FOUND; } if (startIndex < 0) { return INDEX_NOT_FOUND; } else if (startIndex >= array.length) { startIndex = array.length - 1; } for (int i = startIndex; i >= 0; i--) { if (valueToFind == array[i]) { return i; } } return INDEX_NOT_FOUND; } /** * Checks if the value is in the given array. * * The method returnsfalse
if anull
array is passed in. * * @param array the array to search through * @param valueToFind the value to find * @returntrue
if the array contains the object */ public static boolean contains(int[] array, int valueToFind) { return indexOf(array, valueToFind) != INDEX_NOT_FOUND; }
}</source>
Object Arrays: Searching for elements in a sorted object array
<source lang="java">
public static int binarySearch(Object array[], Object key) public static int binarySearch(Object array[], Object key, Comparator c)</source>
B H I L M N R Found M @ 4
Produces a new array containing the elements between the start and end indices.
<source lang="java">
import java.lang.reflect.Array; /*
* Licensed to the Apache Software Foundation (ASF) under one or more * contributor license agreements. See the NOTICE file distributed with * this work for additional information regarding copyright ownership. * The ASF licenses this file to You under the Apache License, Version 2.0 * (the "License"); you may not use this file except in compliance with * the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. * * */
/**
* @author Stephen Colebourne * @author Moritz Petersen * @author * @author Maarten Coene * @since 2.0 * @version $Id: ArrayUtils.java 632503 2008-03-01 00:21:52Z ggregory $ */
public class Main {
// Subarrays
//-----------------------------------------------------------------------
/**
* Produces a new array containing the elements between
* the start and end indices.
*
* The start index is inclusive, the end index exclusive.
* Null array input produces null output.
*
* The component type of the subarray is always the same as
* that of the input array. Thus, if the input is an array of type
* Date
, the following usage is envisaged:
*
* * Date[] someDates = (Date[])ArrayUtils.subarray(allDates, 2, 5); *
* * @param array the array * @param startIndexInclusive the starting index. Undervalue (<0) * is promoted to 0, overvalue (>array.length) results * in an empty array. * @param endIndexExclusive elements up to endIndex-1 are present in the * returned subarray. Undervalue (< startIndex) produces * empty array, overvalue (>array.length) is demoted to * array length. * @return a new array containing the elements between * the start and end indices. * @since 2.1 */ public static Object[] subarray(Object[] array, int startIndexInclusive, int endIndexExclusive) { if (array == null) { return null; } if (startIndexInclusive < 0) { startIndexInclusive = 0; } if (endIndexExclusive > array.length) { endIndexExclusive = array.length; } int newSize = endIndexExclusive - startIndexInclusive; Class type = array.getClass().getComponentType(); if (newSize <= 0) { return (Object[]) Array.newInstance(type, 0); } Object[] subarray = (Object[]) Array.newInstance(type, newSize); System.arraycopy(array, startIndexInclusive, subarray, 0, newSize); return subarray; }
}</source>
Returns an index into arra (or -1) where the character is not in the charset byte array.
<source lang="java">
/* Copyright (c) 2001-2009, The HSQL Development Group
* All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: * * Redistributions of source code must retain the above copyright notice, this * list of conditions and the following disclaimer. * * Redistributions in binary form must reproduce the above copyright notice, * this list of conditions and the following disclaimer in the documentation * and/or other materials provided with the distribution. * * Neither the name of the HSQL Development Group nor the names of its * contributors may be used to endorse or promote products derived from this * software without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG, * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */
/**
* Collection of static methods for operations on arrays * * @author Fred Toussi (fredt@users dot sourceforge.net) * @version 1.9.0 * @since 1.7.2 */
public class Main {
/** * Returns an index into arra (or -1) where the character is not in the * charset byte array. */ public static int findNotIn(byte[] arra, int start, int limit, byte[] charset) { int k = 0; for (; k < limit; k++) { for (int i = 0; i < charset.length; i++) { if (arra[k] == charset[i]) { continue; } } return k; } return -1; }
}</source>
Returns an int[] array of length segments containing the distribution count of the elements in unsorted int[] array with values between min and max (range).
<source lang="java">
/* Copyright (c) 2001-2009, The HSQL Development Group
* All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: * * Redistributions of source code must retain the above copyright notice, this * list of conditions and the following disclaimer. * * Redistributions in binary form must reproduce the above copyright notice, * this list of conditions and the following disclaimer in the documentation * and/or other materials provided with the distribution. * * Neither the name of the HSQL Development Group nor the names of its * contributors may be used to endorse or promote products derived from this * software without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG, * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */
/**
* Collection of routines for counting the distribution of the values * in an int[] array. * * @author Fred Toussi (fredt@users dot sourceforge.net) * @version 1.7.2 * @since 1.7.2 */
public class ArrayCounter {
/** * Returns an int[] array of length segments containing the distribution * count of the elements in unsorted int[] array with values between min * and max (range). Values outside the min-max range are ignored * * A usage example is determining the count of people of each age group * in a large int[] array containing the age of each person. Called with * (array, 16,0,79), it will return an int[16] with the first element * the count of people aged 0-4, the second element the count of those * aged 5-9, and so on. People above the age of 79 are excluded. If the * range is not a multiple of segments, the last segment will be cover a * smaller sub-range than the rest. * */ public static int[] countSegments(int[] array, int elements, int segments, int start, int limit) { int[] counts = new int[segments]; long interval = calcInterval(segments, start, limit); int index = 0; int element = 0; if (interval <= 0) { return counts; } for (int i = 0; i < elements; i++) { element = array[i]; if (element < start || element >= limit) { continue; } index = (int) ((element - start) / interval); counts[index]++; } return counts; } /** * With an unsorted int[] array and with target a positive integer in the * range (1,array.length), finds the value in the range (start,limit) of the * largest element (rank) where the count of all smaller elements in that * range is less than or equals target. Parameter margin indicates the * margin of error in target * * In statistics, this can be used to calculate a median or quadrile value. * A usage example applied to an array of age values is to determine * the maximum age of a given number of people. With the example array * given in countSegments, rank(array, c, 6000, 18, 65, 0) will return an age * value between 18-64 (inclusive) and the count of all people aged between * 18 and the returned value(exclusive) will be less than or equal 6000. * */ public static int rank(int[] array, int elements, int target, int start, int limit, int margin) { final int segments = 256; int elementCount = 0; int currentLimit = limit; for (;;) { long interval = calcInterval(segments, start, currentLimit); int[] counts = countSegments(array, elements, segments, start, currentLimit); for (int i = 0; i < counts.length; i++) { if (elementCount + counts[i] < target) { elementCount += counts[i]; start += interval; } else { break; } } if (elementCount + margin >= target) { return start; } if (interval <= 1) { return start; } currentLimit = start + interval < limit ? (int) (start + interval) : limit; } } /** * Helper method to calculate the span of the sub-interval. Simply returns * the cieling of ((limit - start) / segments) and accounts for invalid * start and limit combinations. */ static long calcInterval(int segments, int start, int limit) { long range = limit - start; if (range < 0) { return 0; } int partSegment = (range % segments) == 0 ? 0 : 1; return (range / segments) + partSegment; }
}</source>
Returns the minimum value in an array.
<source lang="java">
/*
* Licensed to the Apache Software Foundation (ASF) under one or more * contributor license agreements. See the NOTICE file distributed with * this work for additional information regarding copyright ownership. * The ASF licenses this file to You under the Apache License, Version 2.0 * (the "License"); you may not use this file except in compliance with * the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */
/**
* Provides extra functionality for Java Number classes. * * @author * @since 2.0 * @version $Id: NumberUtils.java 609475 2008-01-06 23:58:59Z bayard $ */
public class Main {
/** * Returns the minimum value in an array. * * @param array an array, must not be null or empty * @return the minimum value in the array * @throws IllegalArgumentException ifarray
isnull
* @throws IllegalArgumentException ifarray
is empty */ public static long min(long[] array) { // Validates input if (array == null) { throw new IllegalArgumentException("The Array must not be null"); } else if (array.length == 0) { throw new IllegalArgumentException("Array cannot be empty."); } // Finds and returns min long min = array[0]; for (int i = 1; i < array.length; i++) { if (array[i] < min) { min = array[i]; } } return min; }
}</source>
Returns true if all the references in array1 are equal to all the references in array2 (two null references are considered equal for this test).
<source lang="java">
/*
* JCommon : a free general purpose class library for the Java(tm) platform * * * (C) Copyright 2000-2005, by Object Refinery Limited and Contributors. * * Project Info: http://www.jfree.org/jcommon/index.html * * This library is free software; you can redistribute it and/or modify it * under the terms of the GNU Lesser General Public License as published by * the Free Software Foundation; either version 2.1 of the License, or * (at your option) any later version. * * This library is distributed in the hope that it will be useful, but * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public * License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this library; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, * USA. * * [Java is a trademark or registered trademark of Sun Microsystems, Inc. * in the United States and other countries.] * * ------------------- * ArrayUtilities.java * ------------------- * (C) Copyright 2003-2005, by Object Refinery Limited. * * Original Author: David Gilbert (for Object Refinery Limited); * Contributor(s): -; * * $Id: ArrayUtilities.java,v 1.7 2008/09/10 09:21:30 mungady Exp $ * * Changes * ------- * 21-Aug-2003 : Version 1 (DG); * 04-Oct-2004 : Renamed ArrayUtils --> ArrayUtilities (DG); * */
public class Main {
/** * Returnstrue
if all the references inarray1
* are equal to all the references inarray2
(two *null
references are considered equal for this test). * * @param array1 the first array (null
permitted). * @param array2 the second array (null
permitted). * * @return A boolean. */ public static boolean equalReferencesInArrays(final Object[] array1, final Object[] array2) { if (array1 == null) { return (array2 == null); } if (array2 == null) { return false; } if (array1.length != array2.length) { return false; } for (int i = 0; i < array1.length; i++) { if (array1[i] == null) { if (array2[i] != null) { return false; } } if (array2[i] == null) { if (array1[i] != null) { return false; } } if (array1[i] != array2[i]) { return false; } } return true; }
}</source>
Searching Arrays
<source lang="java">
public static int binarySearch(byte array[], byte key) public static int binarySearch(char array[], char key) public static int binarySearch(double array[], double key) public static int binarySearch(float array[], float key) public static int binarySearch(int array[], int key) public static int binarySearch(long array[], long key) public static int binarySearch(short array[], short key)</source>
Sorted array: [length: 10] -9, -7, -3, -2, 0, 2, 4, 5, 6, 8 Found 2 @ 5 Didn"t find 1 @ -6 With 1 added: [length: 11] -9, -7, -3, -2, 0, 1, 2, 4, 5, 6, 8
Sort array utilities
<source lang="java">
/*
* Copyright 2004, 2005, 2006 Odysseus Software GmbH * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */
import java.util.Arrays; import java.util.ruparator; import java.util.Iterator; import java.util.List; /**
* Utility class providing some useful static sort methods. The sort routines
* all return index permutations p such that data[p[0]],..,data[p[data.length-1]]
* is in sorted order. The data array itself is not modified.
* To actually rearrange the array elements, the inverse of p can be used to
* permute the array, such that data[0],..,data[data.length-1] is in sorted
* order. Use getIterator(p, data)
to iterate in sorted order.
* A code example may show you what to do next:
* * String[] colors = { "red", "green", "blue" }; * int[] p = SortUtils.sort(colors, new StringComparator()); * // --> (colors[p[0]], colors[p[1]], colors[p[2]]) == ("blue","green","red") * Iterator iter = SortUtils.getIterator(p, colors) * // --> (iter.next(), iter.next(), iter.next()) == ("blue","green","red") * SortUtils.permute(SortUtils.inverse(p), colors, true); * // --> (colors[0], colors[1], colors[2]) == ("blue","green","red") *
* Stable sorts (preserving order of equal elements) are supported. * Sorting is done using quick-sort mith median of 3 (and insertion-sort * for small ranges). * * @author Christoph Beck */
public class SortUtils {
/** * Helper class used to perform quicksort. * * @author Christoph Beck */ static final class QuickSorter { private static final int INSERTIONSORT_THRESHOLD = 7; private final Object[] data; QuickSorter(Object[] data) { this.data = data; } private int compare(Comparator cmp, boolean stable, int i, int j) { int result = cmp.rupare(data[i], data[j]); if (result == 0 && stable && i != j) { result = i < j ? -1 : 1; } return result; } private int med3(Comparator cmp, int a, int b, int c) { return (compare(cmp, false, a, b) < 0 ? (compare(cmp, false, b, c) < 0 ? b : compare(cmp, false, a, c) < 0 ? c : a) : (compare(cmp, false, b, c) > 0 ? b : compare(cmp, false, a, c) < 0 ? c : a)); } private int pivot(int[] indices, Comparator cmp, int lo, int hi) { return med3(cmp, indices[lo + 1], indices[(lo + hi) / 2], indices[hi - 1]); } private void swap(int[] indices, int i, int j) { int tmp = indices[i]; indices[i] = indices[j]; indices[j] = tmp; } private void insertionSort(int[] indices, Comparator cmp, boolean stable, int lo, int hi) { for (int i = lo; i <= hi; i++) { for (int j = i; j > lo && compare(cmp, stable, indices[j-1], indices[j]) > 0; j--) { swap(indices, j-1, j); } } } private void quickSort(int[] indices, Comparator cmp, boolean stable, int lo0, int hi0) { int pivot = pivot(indices, cmp, lo0, hi0); int lo = lo0, hi = hi0; while (lo <= hi) { while (lo < hi0 && compare(cmp, stable, pivot, indices[lo]) > 0) ++lo; while (hi > lo0 && compare(cmp, stable, pivot, indices[hi]) < 0) --hi; if (lo <= hi) { swap(indices, lo++, hi--); } } sort(indices, cmp, stable, lo0, hi); sort(indices, cmp, stable, lo, hi0); } void sort(int[] indices, Comparator cmp, boolean stable, int lo, int hi) { if (hi - lo < INSERTIONSORT_THRESHOLD) { insertionSort(indices, cmp, stable, lo, hi); } else { quickSort(indices, cmp, stable, lo, hi); } } void sort(int[] indices, Comparator cmp, boolean stable) { sort(indices, cmp, stable, 0, indices.length - 1); } int[] sort(Comparator cmp, boolean stable) { int[] indices = identity(data.length); sort(indices, cmp, stable); return indices; } } /** * Create identity permutation, that is{0, 1, ..., n}
*/ public static int[] identity(int n) { int[] indices = new int[n]; for (int i = 0; i < n; i++) indices[i] = i; return indices; } /** * Create reverse permutation, that is{n-1, .... 1, 0}
*/ public static int[] reverse(int n) { int[] indices = new int[n]; for (int i = 0; i < n; i++) indices[i] = n - i - 1; return indices; } /** * Compute inverse permutation */ public static int[] inverse(int[] p) { int[] pi = new int[p.length]; for (int i = 0; i < pi.length; i++) pi[p[i]] = i; return pi; } /** * Rearrange the specified data according to the specified permutation. * That is, the array is rearranged, such that *data_after[p[i]] == data_before[i]
. * @param data data to be permuted * @param p the permutation * @param clone if true, rearrange a clone instead of the original data; * @return the permuted array (which is the original reference if clone == false) */ public static Object[] permute(int[] p, Object[] data, boolean clone) { Object[] permuted = null; if (clone) { permuted = (Object[])data.clone(); for (int i = 0; i < data.length; i++) permuted[p[i]] = data[i]; } else { // run thru cycles int i = 0; while (i < p.length) { if (p[i] < 0 || p[i] == i) // skip already handled and cycles of length 1 ++i; else { // start a new cycle int j = p[i]; Object save = data[i]; while (p[j] >= 0) { Object tmp = data[j]; data[j] = save; save = tmp; i = j; j = p[j]; p[i] = -1; } } } permuted = data; } return permuted; } /** * Answer iterator, which iterates over specified data array according * to the specified permutation, that is *data[p[0]],..,data[p[data.length-1]]
*/ public static Iterator getIterator(final int[] p, final Object[] data) { return new Iterator() { int pos = 0; public boolean hasNext() { return pos < data.length; } public Object next() { return data[p[pos++]]; } public void remove() { throw new UnsupportedOperationException("Cannot remove from immutable iterator!"); } }; } /** * Answer iterator, which iterates over specified data list according * to the specified permutation, that is *data.get(p[0]),..,data.get(p[data.length-1])
*/ public static Iterator getIterator(final int[] p, final List data) { return new Iterator() { int pos = 0; public boolean hasNext() { return pos < data.size(); } public Object next() { return data.get(p[pos++]); } public void remove() { throw new UnsupportedOperationException("Cannot remove from immutable iterator!"); } }; }
// /** // * An improved heap builder. // * Assumes children of i at 2i and 2i+1 (requires i>0) // */ // private static void cheap(int[] indices, Object[] data, Comparator comparator, int i, int j) { // int k = (i << 1); // if (k > j) // return; // while (k < j) { // if (comparator.rupare(data[indices[k]], data[indices[k + 1]]) < 0) // k++; // k <<= 1; // } // if (k > j) // k >>= 1; // while (comparator.rupare(data[indices[k]], data[indices[i]]) < 0) // k >>= 1; // int t1 = indices[i], t2; // while (k > i) { // t2 = indices[k]; // indices[k] = t1; // k >>= 1; // t1 = indices[k]; // indices[k] = t2; // k >>= 1; // } // if (k == i) // indices[i] = t1; // } // // /** // * Do a (clever) heapsort. // * // * @param comparator Comparator object specifying the sort order. // */ // public static void cheapSort(int[] indices, Object[] data, Comparator comparator) { // int n = data.length; // if (n > 1) { // int i; // int m = 0; // for (i = 1; i < n; i++) // if (comparator.rupare(data[indices[i]], data[indices[m]]) < 0) // m = i; // if (m > 0) { // int t = indices[0]; // indices[0] = indices[m]; // indices[m] = t; // } // if (n > 2) { // for (i = n / 2; i > 1; i--) // cheap(indices, data, comparator, i, n - 1); // for (i = n - 1; i > 1; i--) { // cheap(indices, data, comparator, 1, i); // int t = indices[1]; // indices[1] = indices[i]; // indices[i] = t; // } // } // } // } // // /** // * Perform a cheapsort // */ // public static int[] cheapSort(Object[] data, Comparator comparator) { // int[] indices = identity(data.length); // cheapSort(indices, data, comparator); // return indices; // }
/** * Do a sort on indices. * @param data data to be sorted * @param comparator comparator to use * @param stable do a stable sort iff true * @param indices into data (any permutation of 0,..data.length-1). */ public static void sort(int[] indices, Object[] data, Comparator comparator, boolean stable) { new QuickSorter(data).sort(indices, comparator, stable); } /** * Do a sort on indices. * @param data data to be sorted * @param comparator comparator to use * @param stable do a stable sort iff true * @return permutation p such that data[p[0]],..,data[p[data.length-1]] is in sorted order */ public static int[] sort(Object[] data, Comparator comparator, boolean stable) { int[] indices = identity(data.length); sort(indices, data, comparator, stable); return indices; } /** * Do an unstable sort. * @param data data to be sorted * @param comparator comparator to use * @return permutation p such that data[p[0]],..,data[p[data.length-1]] is in sorted order */ public static int[] sort(Object[] data, Comparator comparator) { return sort(data, comparator, false); } /** * Do an unstable sort. * @param data data to be sorted * @param indices into data (permutation of 0,..data.length-1). */ public static void sort(int[] indices, Object[] data, Comparator comparator) { sort(indices, data, comparator, false); } /** * Test method */ public static void main(String[] args) { Comparator cmp = new Comparator() { public int compare(Object o1, Object o2) { return ((Comparable)o1).rupareTo(o2); } }; int n = 1000000; if (args.length == 1) try { n = Integer.parseInt(args[0]); } catch (Exception e) { System.err.println(e); } System.out.println("Generating " + n + " random integers..."); java.util.Random random = new java.util.Random(); Integer[] data = new Integer[n]; for (int i = 0; i < n; i++) { data[i] = new Integer(Math.abs(random.nextInt()));
// data[i] = new Integer(i);
} int[] indices; long time; System.out.print("Arrays.sort..."); time = System.currentTimeMillis(); Integer[] clone = (Integer[])data.clone(); Arrays.sort(clone, cmp); System.out.println(System.currentTimeMillis()-time + "ms"); System.out.print("quicksort..."); indices = identity(n); time = System.currentTimeMillis(); sort(indices, data, cmp, false); System.out.println(System.currentTimeMillis()-time + "ms"); for (int i = 1; i < n; i++) if (cmp.rupare(data[indices[i-1]], data[indices[i]]) > 0) System.err.println("proplem: quickSort at " + i); System.out.print("quicksort stable...");
// indices = identity(n);
time = System.currentTimeMillis(); sort(indices, data, cmp, true); System.out.println(System.currentTimeMillis()-time + "ms"); for (int i = 1; i < n; i++) { int res = cmp.rupare(data[indices[i-1]], data[indices[i]]); if (res > 0) System.err.println("proplem: quickSort stable at " + i); if (res == 0 && indices[i-1] > indices[i]) System.err.println("proplem: quickSort stable (not stable) at " + i); }
// System.out.print("cheapsort..."); // time = System.currentTimeMillis(); // indices = cheapSort(data, cmp); // System.out.println(System.currentTimeMillis()-time + "ms"); // for (int i = 1; i < n; i++) // if (cmp.rupare(data[indices[i-1]], data[indices[i]]) > 0) // System.err.println("proplem: cheapSort at " + i);
System.out.print("permutate copy..."); time = System.currentTimeMillis(); Object[] data_copy = permute(inverse(indices), data, true); System.out.println(System.currentTimeMillis()-time + "ms"); for (int i = 1; i < n; i++) if (cmp.rupare(data_copy[i-1], data_copy[i]) > 0) System.err.println("proplem: permute copy at " + i); System.out.print("permutate original..."); time = System.currentTimeMillis(); permute(inverse(indices), data, false); System.out.println(System.currentTimeMillis()-time + "ms"); for (int i = 1; i < n; i++) if (cmp.rupare(data[i-1], data[i]) > 0) System.err.println("proplem: permute original at " + i); }
}</source>
Sorting Arrays
<source lang="java">
public static void sort(byte array[]) public static void sort(byte array[], int fromIndex, int toIndex) public static void sort(char array[]) public static void sort(char array[], int fromIndex, int toIndex) public static void sort(double array[]) public static void sort(double array[], int fromIndex, int toIndex) public static void sort(float array[]) public static void sort(float array[], int fromIndex, int toIndex) public static void sort(int array[]) public static void sort(int array[], int fromIndex, int toIndex) public static void sort(long array[]) public static void sort(long array[], int fromIndex, int toIndex) public static void sort(short array[]) public static void sort(short array[], int fromIndex, int toIndex)</source>
-3 -2 2 5 6
Sorting arrays of objects
<source lang="java">
public static void sort(Object array[]) public static void sort(Object array[], int fromIndex, int toIndex) public static void sort(Object array[], Comparator c) public static void sort(Object array[], int fromIndex, int toIndex, Comparator c)</source>
A B C
Sorting a subset of array elements
<source lang="java">
import java.util.Arrays; public class MainClass {
public static void main(String[] a) { int array[] = { 2, 5, -2, 6, -3, 8, 0, -7, -9, 4 }; Arrays.sort(array, 3, 7); for (int i : array) { System.out.println(i); } }
}</source>
2 5 -2 -3 0 6 8 -7 -9 4
Test the equality of two object arrays
<source lang="java">
import java.lang.reflect.Array; /*
* JBoss, Home of Professional Open Source * Copyright 2005, JBoss Inc., and individual contributors as indicated * by the @authors tag. See the copyright.txt in the distribution for a * full listing of individual contributors. * * This is free software; you can redistribute it and/or modify it * under the terms of the GNU Lesser General Public License as * published by the Free Software Foundation; either version 2.1 of * the License, or (at your option) any later version. * * This software is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this software; if not, write to the Free * Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA * 02110-1301 USA, or see the FSF site: http://www.fsf.org. */
public class Main {
/** * Test the equality of two object arrays. * * @param a The first array. * @param b The second array. * @param deep True to traverse elements which are arrays. * @return True if arrays are equal. */ public static boolean equals(final Object[] a, final Object[] b, final boolean deep) { if (a == b) return true; if (a == null || b == null) return false; if (a.length != b.length) return false; for (int i=0; i<a.length; i++) { Object x = a[i]; Object y = b[i]; if (x != y) return false; if (x == null || y == null) return false; if (deep) { if (x instanceof Object[] && y instanceof Object[]) { if (! equals((Object[])x, (Object[])y, true)) return false; } else { return false; } } if (! x.equals(y)) return false; } return true; } /** * Test the equality of two object arrays. * * @param a The first array. * @param b The second array. * @return True if arrays are equal. */ public static boolean equals(final Object[] a, final Object[] b) { return equals(a, b, true); }
}</source>