import java.util.Random;
/**
* Sorting test class
*
* The classification of sorting algorithms is as follows: 1. Insertion sort (direct insertion sort, half insertion sort, Hill sort); 2. Exchange sort (bubble sort, quick sort);
* 3. Selection sort (direct selection sort, heap sort); 4. Merge sort; 5. Radix sort.
*
* Regarding the choice of sorting method: (1) If n is small (such as n≤50), direct insertion or direct selection sorting can be used.
* When the record size is small, direct insertion sorting is better; otherwise, because the number of records moved by direct selection is less than that of direct insertion, direct selection sorting is better.
* (2) If the initial state of the file is basically in order (referring to positive order), direct insertion, bubble or random quick sorting should be used;
* (3) If n is large, a sorting method with a time complexity of O(nlgn) should be used: quick sort, heap sort or merge sort.
*
*/
public class Sort {
/**
* Method to initialize test array
*
* @return an initialized array
*/
public int[] createArray() {
Random random = new Random();
int[] array = new int[10];
for (int i = 0; i < 10; i++) {
array[i] = random.nextInt(100) - random.nextInt(100); // Generate two random numbers and subtract them to ensure that there are negative numbers in the generated numbers.
}
System.out.println("==========original sequence==========");
printArray(array);
return array;
}
/**
* Print the elements in the array to the console
*
* @param source
*/
public void printArray(int[] data) {
for (int i : data) {
System.out.print(i + " ");
}
System.out.println();
}
/**
* Exchange the positions of the two specified elements in the array
*
* @param data
* @param x
* @param y
*/
private void swap(int[] data, int x, int y) {
int temp = data[x];
data[x] = data[y];
data[y] = temp;
}
/**
* Bubble sort----a type of exchange sort
* Method: Compare two adjacent elements and exchange them if necessary. After each cycle is completed, the largest element is ranked last (such as sorting from small to large). The next cycle will perform similar operations on other numbers.
* Performance: number of comparisons O(n^2),n^2/2; number of exchanges O(n^2),n^2/4
*
* @param data
* Array to be sorted
* @param sortType
* Sorting type
* @return
*/
public void bubbleSort(int[] data, String sortType) {
if (sortType.equals("asc")) { // Positive sorting, from small to large
// Number of rounds of comparison
for (int i = 1; i < data.length; i++) {
// Compare two adjacent numbers, and the larger number will bubble up.
for (int j = 0; j < data.length - i; j++) {
if (data[j] > data[j + 1]) {
// Swap two adjacent numbers
swap(data, j, j + 1);
}
}
}
} else if (sortType.equals("desc")) { // Sort in reverse order, from big to small
// Number of rounds of comparison
for (int i = 1; i < data.length; i++) {
// Compare two adjacent numbers, and the larger number will bubble up.
for (int j = 0; j < data.length - i; j++) {
if (data[j] < data[j + 1]) {
// Swap two adjacent numbers
swap(data, j, j + 1);
}
}
}
} else {
System.out.println("The sorting type you entered is wrong!");
}
printArray(data);//Output the array value after bubble sorting
}
/**
* Direct selection sorting method----a type of selection sorting
* Method: In each pass, the smallest (or largest) element is selected from the data elements to be sorted, and the order is placed at the end of the sorted array until all the data elements to be sorted are arranged.
* Performance: Number of comparisons O(n^2),n^2/2
* Number of exchanges O(n),n
* The number of exchanges is much less than that of bubble sort. Since exchange requires more CPU time than comparison, selection sort is faster than bubble sort.
* But when N is relatively large, the CPU time required for comparison dominates, so the performance at this time is not much different from that of bubble sort, but it is undoubtedly faster.
*
* @param data
* Array to be sorted
* @param sortType
* Sorting type
* @return
*
*/
public void selectSort(int[] data, String sortType) {
if (sortType.equals("asc")) { // Positive sorting, from small to large
int index;
for (int i = 1; i < data.length; i++) {
index = 0;
for (int j = 1; j <= data.length - i; j++) {
if (data[j] > data[index]) {
index = j;
}
}
//Exchange the two numbers at position data.length-i and index (maximum value)
swap(data, data.length - i, index);
}
} else if (sortType.equals("desc")) { // Sort in reverse order, from big to small
int index;
for (int i = 1; i < data.length; i++) {
index = 0;
for (int j = 1; j <= data.length - i; j++) {
if (data[j] < data[index]) {
index = j;
}
}
//Exchange the two numbers at position data.length-i and index (maximum value)
swap(data, data.length - i, index);
}
} else {
System.out.println("The sorting type you entered is wrong!");
}
printArray(data);//Output the array value after direct selection sorting
}
/**
*
* Insertion sort
*
* Method: Insert a record into a sorted ordered list (possibly an empty list), thereby obtaining a new ordered list with the number of records increased by 1.
* Performance: number of comparisons O(n^2),n^2/4
* Number of copies O(n),n^2/4
* The number of comparisons is average between the first two, and copying requires less CPU time than swapping, so the performance is more than double that of bubble sort and faster than selection sort.
*
* @param data
* Array to be sorted
* @param sortType
* Sorting type
*/
public void insertSort(int[] data, String sortType) {
if (sortType.equals("asc")) { // Positive sorting, from small to large
// Number of rounds of comparison
for (int i = 1; i < data.length; i++) {
// Ensure that the first i+1 numbers are sorted
for (int j = 0; j < i; j++) {
if (data[j] > data[i]) {
// Swap the two numbers at positions j and i
swap(data, i, j);
}
}
}
} else if (sortType.equals("desc")) { // Sort in reverse order, from big to small
// Number of rounds of comparison
for (int i = 1; i < data.length; i++) {
// Ensure that the first i+1 numbers are sorted
for (int j = 0; j < i; j++) {
if (data[j] < data[i]) {
// Swap the two numbers at positions j and i
swap(data, i, j);
}
}
}
} else {
System.out.println("The sorting type you entered is wrong!");
}
printArray(data);//Output the array value after insertion sorting
}
/**
*
* Method to reverse an array
*
* @param data
* source array
*/
public void reverse(int[] data) {
int length = data.length;
int temp = 0;//temporary variable
for (int i = 0; i < length / 2; i++) {
temp = data[i];
data[i] = data[length - 1 - i];
data[length - 1 - i] = temp;
}
printArray(data);//Output the value to the converted array
}
/**
*
* Quick sort
*
* Quick sort uses the divide and conquer strategy to divide a sequence (list) into two sub-sequences (sub-lists).
*
*The steps are:
* 1. Pick an element from the sequence, called "pivot",
* 2. Reorder the sequence so that all elements smaller than the base value are placed in front of the base, and all elements larger than the base value are placed behind the base (the same number can be placed on either side). After this split, the datum is in its final position. This is called a partition operation.
* 3. Recursively sort the subarray of elements smaller than the base value and the subarray of elements greater than the base value.
*
* The bottom case of recursion is when the size of the array is zero or one, that is, it has always been sorted. Although it keeps recursing, this algorithm will always end, because in each iteration (iteration), it will move at least one element to its final position.
*
* @param data
* Array to be sorted
* @param low
* @param high
* @see SortTest#qsort(int[], int, int)
* @see SortTest#qsort_desc(int[], int, int)
*
*/
public void quickSort(int[] data, String sortType) {
if (sortType.equals("asc")) { // Positive sorting, from small to large
qsort_asc(data, 0, data.length - 1);
} else if (sortType.equals("desc")) { // Sort in reverse order, from big to small
qsort_desc(data, 0, data.length - 1);
} else {
System.out.println("The sorting type you entered is wrong!");
}
}
/**
*
* Specific implementation of quick sorting, sorting in correct order
*
* @param data
* @param low
* @param high
*/
private void qsort_asc(int data[], int low, int high) {
int i, j, x;
if (low < high) { // This condition is used to end the recursion
i = low;
j = high;
x = data[i];
while (i < j) {
while (i < j && data[j] > x) {
j--; // Find the first number less than x from right to left
}
if (i < j) {
data[i] = data[j];
i++;
}
while (i < j && data[i] < x) {
i++; // Find the first number greater than x from left to right
}
if (i < j) {
data[j] = data[i];
j--;
}
}
data[i] = x;
qsort_asc(data, low, i - 1);
qsort_asc(data, i + 1, high);
}
}
/**
*
* Specific implementation of quick sort, sort in reverse order
*
* @param data
* @param low
* @param high
*
*/
private void qsort_desc(int data[], int low, int high) {
int i, j, x;
if (low < high) { // This condition is used to end the recursion
i = low;
j = high;
x = data[i];
while (i < j) {
while (i < j && data[j] < x) {
j--; // Find the first number less than x from right to left
}
if (i < j) {
data[i] = data[j];
i++;
}
while (i < j && data[i] > x) {
i++; // Find the first number greater than x from left to right
}
if (i < j) {
data[j] = data[i];
j--;
}
}
data[i] = x;
qsort_desc(data, low, i - 1);
qsort_desc(data, i + 1, high);
}
}
/**
*
* Binary search for the position of a specific integer in an integer array (recursive)
*
* Search linear list must be an ordered list
*
* @paramdataset
* @paramdata
* @parambeginIndex
* @paramendIndex
* @returnindex
*
*/
public int binarySearch(int[] dataset, int data, int beginIndex,int endIndex) {
int midIndex = (beginIndex + endIndex) >>> 1; // Equivalent to mid = (low + high)
// / 2, but the efficiency will be higher
if (data < dataset[beginIndex] || data > dataset[endIndex] || beginIndex > endIndex)
return -1;
if (data < dataset[midIndex]) {
return binarySearch(dataset, data, beginIndex, midIndex - 1);
} else if (data > dataset[midIndex]) {
return binarySearch(dataset, data, midIndex + 1, endIndex);
} else {
return midIndex;
}
}
/**
*
* Binary search for the position of a specific integer in an integer array (non-recursive)
*
* Search linear list must be an ordered list
*
* @paramdataset
* @paramdata
* @returnindex
*
*/
public int binarySearch(int[] dataset, int data) {
int beginIndex = 0;
int endIndex = dataset.length - 1;
int midIndex = -1;
if (data < dataset[beginIndex] || data > dataset[endIndex] || beginIndex > endIndex)
return -1;
while (beginIndex <= endIndex) {
midIndex = (beginIndex + endIndex) >>> 1; // Equivalent to midIndex =
// (beginIndex +
// endIndex) / 2, but the efficiency will be higher
if (data < dataset[midIndex]) {
endIndex = midIndex - 1;
} else if (data > dataset[midIndex]) {
beginIndex = midIndex + 1;
} else {
return midIndex;
}
}
return -1;
}
public static void main(String[] args) {
Sort sortTest = new Sort();
int[] array = sortTest.createArray();
System.out.println("==========After bubble sort (positive order)==========");
sortTest.bubbleSort(array, "asc");
System.out.println("==========After bubble sort (reverse order)==========");
sortTest.bubbleSort(array, "desc");
array = sortTest.createArray();
System.out.println("==========After reversing the array==========");
sortTest.reverse(array);
array = sortTest.createArray();
System.out.println("==========After selection sorting (positive order)==========");
sortTest.selectSort(array, "asc");
System.out.println("==========After selection sorting (reverse order)==========");
sortTest.selectSort(array, "desc");
array = sortTest.createArray();
System.out.println("==========After insertion sort (positive sequence)==========");
sortTest.insertSort(array, "asc");
System.out.println("==========After insertion sort (reverse order)==========");
sortTest.insertSort(array, "desc");
array = sortTest.createArray();
System.out.println("==========After quick sort (positive order)==========");
sortTest.quickSort(array, "asc");
sortTest.printArray(array);
System.out.println("==========After quick sort (reverse order)==========");
sortTest.quickSort(array, "desc");
sortTest.printArray(array);
System.out.println("==========Binary search in array==========");
System.out.println("The number you are looking for is at" + sortTest.binarySearch(array, 74)
+ "seats. (Subscript calculated from 0)");
}
}