package com.test;
import java.util.Random;
public class Sort {
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 minus each other to make sure that the generated number has a negative number
}
System.out.println("========== The original sequence ==========");
printArray(array);
return array;
}
public void printArray(int[] data) {
for (int i : data) {
System.out.print(i + " ");
}
System.out.println();
}
private void swap(int[] data, int x, int y) {
int temp = data[x];
data[x] = data[y];
data[y] = temp;
}
/**
* Bubble sort ---- Exchange sort
* Method: two adjacent elements are compared, and if necessary, they are exchanged. After each loop, the largest element is ranked last (such as sorting from small to large). The next loop is to perform similar operations on other Numbers.
* Performance: number of comparisons O(n^2),n^2/2 ; Switching frequency O(n^2),n^2/4
*
* @param data
* The array to sort
* @param sortType
* Sorting type
* @return
*/
public void bubbleSort(int[] data, String sortType) {
if (sortType.equals("asc")) { //Positive sort, from small to large
//Number of rounds of comparison
for (int i = 1; i < data.length; i++) {
//When two adjacent Numbers are compared, the larger number bubbles back
for (int j = 0; j < data.length - i; j++) {
if (data[j] > data[j + 1]) {
//Swap adjacent Numbers
swap(data, j, j + 1);
}
}
}
} else if (sortType.equals("desc")) { //Sort backwards, from large to small
//Number of rounds of comparison
for (int i = 1; i < data.length; i++) {
//When two adjacent Numbers are compared, the larger number bubbles back
for (int j = 0; j < data.length - i; j++) {
if (data[j] < data[j + 1]) {
//Swap adjacent Numbers
swap(data, j, j + 1);
}
}
}
} else {
System.out.println(" You entered the wrong sort type! ");
}
printArray(data);//Output bubble sorted array values
}
/**
* Direct selection sort ---- A selection sort
* Method: select the smallest (or largest) element from the data element to be sorted. The order is placed at the end of the sorted sequence until all the data elements to be sorted are sorted.
* Performance: number of comparisons O(n^2),n^2/2
* Switching frequency O(n),n
* Switching times are much less than bubble sort because switching is required CPU Compare the time required CUP More time, so select sort is faster than bubble sort.
* but N When larger, compare what is needed CPU Time is of the essence, so the performance isn't much different from bubble sort, but it's certainly faster.
*
* @param data
* The array to sort
* @param sortType
* Sorting type
* @return
*
*/
public void selectSort(int[] data, String sortType) {
if (sortType.equals("asc")) { //Positive sort, 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;
}
}
//Swap two Numbers at the position data.length-i and index(maximum)
swap(data, data.length - i, index);
}
} else if (sortType.equals("desc")) { //Sort backwards, from large 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;
}
}
//Swap two Numbers at the position data.length-i and index(maximum)
swap(data, data.length - i, index);
}
} else {
System.out.println(" You entered the wrong sort type! ");
}
printArray(data);//The output directly selects the sorted array value
}
/**
*
* Insertion sort
*
* Method: insert a record into a sorted (possibly empty) table , So you get a new record increment 1 An ordered list.
* Performance: number of comparisons O(n^2),n^2/4
* Copy number O(n),n^2/4
* The number of comparisons is about the same as the first two, and the number required for replication CPU Less time than switching, so performance is more than twice as good as bubble sort and faster than selection sort.
*
* @param data
* The array to sort
* @param sortType
* Sorting type
*/
public void insertSort(int[] data, String sortType) {
if (sortType.equals("asc")) { //Positive sort, from small to large
//Number of rounds of comparison
for (int i = 1; i < data.length; i++) {
//Make sure that I plus 1 is sorted
for (int j = 0; j < i; j++) {
if (data[j] > data[i]) {
//The swap is at j and I
swap(data, i, j);
}
}
}
} else if (sortType.equals("desc")) { //Sort backwards, from large to small
//Number of rounds of comparison
for (int i = 1; i < data.length; i++) {
//Make sure that I plus 1 is sorted
for (int j = 0; j < i; j++) {
if (data[j] < data[i]) {
//The swap is at j and I
swap(data, i, j);
}
}
}
} else {
System.out.println(" You entered the wrong sort type! ");
}
printArray(data);//Output the array value after insertion sort
}
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 rotated array
}
public void quickSort(int[] data, String sortType) {
if (sortType.equals("asc")) { //Positive sort, from small to large
qsort_asc(data, 0, data.length - 1);
} else if (sortType.equals("desc")) { //Sort backwards, from large to small
qsort_desc(data, 0, data.length - 1);
} else {
System.out.println(" You entered the wrong sort type! ");
}
}
private void qsort_asc(int data[], int low, int high) {
int i, j, x;
if (low < high) { //This condition is used to close the recursion
i = low;
j = high;
x = data[i];
while (i < j) {
while (i < j && data[j] > x) {
j--; //I'm looking from right to left for the first number that's less than x
}
if (i < j) {
data[i] = data[j];
i++;
}
while (i < j && data[i] < x) {
i++; //I'm going to go from left to right to find the first number that's greater than x
}
if (i < j) {
data[j] = data[i];
j--;
}
}
data[i] = x;
qsort_asc(data, low, i - 1);
qsort_asc(data, i + 1, high);
}
}
private void qsort_desc(int data[], int low, int high) {
int i, j, x;
if (low < high) { //This condition is used to close the recursion
i = low;
j = high;
x = data[i];
while (i < j) {
while (i < j && data[j] < x) {
j--; //I'm looking from right to left for the first number that's less than x
}
if (i < j) {
data[i] = data[j];
i++;
}
while (i < j && data[i] > x) {
i++; //I'm going to go from left to right to find the first number that's greater than x
}
if (i < j) {
data[j] = data[i];
j--;
}
}
data[i] = x;
qsort_desc(data, low, i - 1);
qsort_desc(data, i + 1, high);
}
}
public int binarySearch(int[] dataset, int data, int beginIndex,int endIndex) {
int midIndex = (beginIndex + endIndex) >>> 1; //So it's mid = low + high.
//PI over 2, but it's more efficient
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;
}
}
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; //MidIndex =
// (beginIndex +
// endIndex)PI over 2, but it's more efficient
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 the bubble sort ( Positive sequence )==========");
sortTest.bubbleSort(array, "asc");
System.out.println("========== After the bubble sort ( Reverse order )==========");
sortTest.bubbleSort(array, "desc");
array = sortTest.createArray();
System.out.println("========== I'm going to invert the array ==========");
sortTest.reverse(array);
array = sortTest.createArray();
System.out.println("========== After selection sort ( Positive sequence )==========");
sortTest.selectSort(array, "asc");
System.out.println("========== After selection sort ( 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 quicksort ( Positive sequence )==========");
sortTest.quickSort(array, "asc");
sortTest.printArray(array);
System.out.println("========== After quicksort ( Reverse order )==========");
sortTest.quickSort(array, "desc");
sortTest.printArray(array);
System.out.println("========== Array binary search ==========");
System.out.println(" The number you are looking for is no " + sortTest.binarySearch(array, 74)
+ " A seat. (subscript from 0 Computing) ");
}
}