10 common sorting algorithms in Java
Abstract: Algorithm in daily programming is a very important knowledge point, today let us review the sorting, the following is commonly used in Java ten algorithm cases:
import java.util.ArrayList;
import java.util.Arrays;
public class Sort {
public static void main(String[] args) {
int[] arr = new int[20];
int index = 0;
for(int i = 20; i >0; i--) arr[index++] = i; System.out.println("Original array:");
System.out.println(Arrays.toString(arr));
System.out.println("Start sorting");
arr = InsertionSort(arr);
System.out.println("After sorting:");
System.out.println(Arrays.toString(arr));
}
// Tools: Swap the positions of the elements in the array
public static int[] swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}
// ****** 1. Insert sort ******
public static int[] InsertionSort(int[] arr){
if(arr.length == 0 || arr.length == 1)
return arr;
for(int i = 0; i < arr.length -1; i++){// Insert the number at position I +1 into the array between 0 and I, traversing backwards
// current refers to the position element of I +1, and pre refers to the pointer from 0 to I
int current = arr[i+1];
int pre = i;
while(pre >= 0 && current < arr[pre]){
arr[pre+1] = arr[pre];
pre--;
}
// Finally, place the elements in the original I +1 position at the correct position in the array between 0 and I +1
// The pre+1 is because it subtracted again at the end of the loop
arr[pre+1] = current;
// Prints the sorting result of this round
System.out.println(Arrays.toString(arr));
}
return arr;
}
// ****** 2. Hill sort ******
// The most important variable in hill sort is gap
public static int[] ShellSort(int[] arr){
if(arr.length == 0 || arr.length == 1)
return arr;
int current, gap = arr.length / 2;
while(gap > 0) {for(inti = gap; i < arr.length; i++){// Insert the number in the pre+gap position into the array between 0 and pre, traversing backwards
// Current refers to pre+gap position element
current = arr[i];
int pre = i - gap;
while(pre >= 0 && arr[pre] > current){
arr[pre+gap] = arr[pre];
pre -= gap;
}
arr[pre+gap] = current;
// Prints the sorting result of this round
System.out.println(Arrays.toString(arr));
}
gap /= 2;
}
return arr;
}
// ****** 3. Simple selection sort ******
public static int[] SelectionSort(int[] arr){
if(arr.length == 0 || arr.length == 1)
return arr;
for(int i = 0; i < arr.length -1; i++){// Each round picks the smallest element and swaps it with the elements at the increasing I position
int MinIndex = i;
for(intj = i; j < arr.length; j++){if(arr[j] < arr[MinIndex])
MinIndex = j;
}
arr = swap(arr,MinIndex,i);
// Prints the sorting result of this round
System.out.println(Arrays.toString(arr));
}
return arr;
}
// ****** 4. Heap sort ******
/ / the main function
public static int[] HeapSort(int[] arr){
if(arr.length == 0 || arr.length == 1)
return arr;
int len = arr.length;
// The first step in heap sort is to make the current array a maximum heap
arr = AdjustMaxHeap(arr, len-1);
while(len > 0) {// Swap the element at the top of the heap (the largest element) with the element at the end that has not yet been positioned
arr = swap(arr,0,len - 1);
// Prints the sorting result of this round
System.out.println(Arrays.toString(arr));
len--;
arr = AdjustMaxHeap(arr,len - 1);
}
return arr;
}
// Adjust to the maximum heap
public static int[] AdjustMaxHeap(int[] arr, int lastIndex){
for(int i = (lastIndex - 1) / 2; i>=0; i--){ arr = AdjustLocalHeap(arr,lastIndex,i); }return arr;
}
// Adjust the local heap to make it the local maximum heap
Parent = (child -1) /2 Left child = parent *2+1 Right child = parent *2+2 */
public static int[] AdjustLocalHeap(int[] arr,int lastIndex,int i){
// Find the largest element in the current node and left and right children (if any), and make the largest element the parent
int maxIndex = i;
if(i*2+1 <= lastIndex && arr[i] < arr[i*2+1])
maxIndex = i*2+1;
// Check whether the right child is greater than the left child
if(i*2+2 <= lastIndex && arr[i] < arr[i*2+2] && arr[i*2+1] < arr[i*2+2])
maxIndex = i*2+2;
// If the parent is not the largest of the three nodes, then make the largest node the parent
// Use recursion to see if the smaller parent can "sink" further
if(maxIndex ! = i){ arr = swap(arr,maxIndex,i); arr = AdjustLocalHeap(arr,lastIndex,maxIndex); }return arr;
}
// ****** 5. Bubble sort ******
public static int[] BubbleSort(int[] arr){
if(arr.length == 0 || arr.length ==1)
return arr;
for(int i = arr.length-1; i >0; i--){for(int j = 1; j <= i; j++){if(arr[j] < arr[j-1])
arr = swap(arr,j,j-1);
}
// Prints the sorting result of this round
System.out.println(Arrays.toString(arr));
}
return arr;
}
// ****** 6
/ / the main function
public static int[] QuickSort(int[] arr){
if(arr.length == 0 || arr.length ==1)
return arr;
arr = LocalQuickSort(arr,0,arr.length -1 );
return arr;
}
// Quicksort
public static int[] LocalQuickSort(int[] arr, int start, int last){
if(start >= last)
return arr;
// Benchmark refers to the number of positions to be determined in this round
int benchmark = start;
int left = start;
int right = last;
while(left < right){
// The right pointer must go first
while(arr[right] > arr[benchmark] && left < right) right--;
if(arr[right] <= arr[benchmark] && left < right) arr[left++] = arr[right];
while(arr[left] < arr[benchmark] && left < right) left++;
if(arr[right] >= arr[benchmark] && left < right) arr[right--] = arr[left];
}
arr[left] = arr[benchmark];
// Prints the sorting result of this round
System.out.println(Arrays.toString(arr));
// Use recursion to quickly sort the two sides of the number
arr = LocalQuickSort(arr,start,left-1);
arr = LocalQuickSort(arr,left+1,last);
return arr;
}
// ****** 7. Merge sort ******
/ / the main function
public static int[] MergeSort(int[] arr){
if(arr.length == 0 || arr.length ==1)
return arr;
arr = Merge(arr,0,arr.length-1);
return arr;
}
// merge sort
public static int[] Merge(int[] arr,int start,int last){
// The start < last judgment means that there must be at least two elements in the range specified by arR
if(start < last){
int mid = (start + last) / 2;
// The left and right parts are recursive respectively
arr = Merge(arr,start,mid);
arr = Merge(arr,mid+1,last);
// Recursive level: the left and right parts are integrated into one part from the inside out
arr = merge(arr,start,mid,last);
}
return arr;
}
public static int[] merge(int[] arr,int start,int mid,int last){
// tempArr is an extra array used to temporarily sort elements in the same region of the ARR
int[] tempArr = new int[arr.length];
// p1 refers to the left half of the arR range, p2 refers to the right half of the arR range, and p refers to the extra tempArr array
int p1 = start, p2 = mid+1, p = start;
// The smallest element from the left and right parts of the specified range is added to the extra array to complete the sorting within the specified range
while(p1 <= mid && p2 <= last){
if(arr[p1] <= arr[p2])
tempArr[p++] = arr[p1++];
else
tempArr[p++] = arr[p2++];
}
while(p1 <= mid) tempArr[p++] = arr[p1++];
while(p2 <= last) tempArr[p++] = arr[p2++];
// Overwrite the data in the additional array into the original ARR array
for(inti = start; i <= last; i++) arr[i] = tempArr[i]; System.out.println(Arrays.toString(arr));return arr;
}
// ****** 8
public static int[] RadixSort(int[] arr){
if(arr.length == 0 || arr.length ==1)
return arr;
MaxDigit indicates the number of digits in the maxDigit group
int max = arr[0];
for(int x:arr)
max = Math.max(x,max);
int maxDigit = 0;
while(max ! =0){
max /= 10;
maxDigit++;
}
// mod is used to take the remainder of an array. Div is used to take the remainder of an array into units
int mod = 10;
int div = 1;
ArrayList<ArrayList<Integer>> bucket = new ArrayList<ArrayList<Integer>>();
for(int j = 0; j <10; j++){ bucket.add(new ArrayList<Integer>());
}
for(int i = 0; i<maxDigit; i++,mod *=10,div *= 10) {// Prints the sorting result of this round
System.out.println(Arrays.toString(arr));
for(int j = 0; j < arr.length; j++){// num specifies the number of digits (ten, hundred, thousand) of the current element arr[j]
int num = (arr[j] % mod) / div;
bucket.get(num).add(arr[j]);
}
int index = 0;
for(int j = 0; j <10; j++){if(bucket.get(j).size() ! =0) {for(int x:bucket.get(j))
arr[index++] = x;
// Empty all the dynamic arrays in the bucket, otherwise there will still be data in the dynamic arrays when the second loop startsbucket.get(j).clear(); }}}return arr;
}
// ****** 9
public static int[] CountingSort(int[] arr){
if(arr.length ==0 || arr.length == 1)
return arr;
int min, max;
min = max = arr[0];
for(int x: arr){
if(x > max)
max = x;
if(x < min)
min = x;
}
// Bucket refers to the bucket used to store the number of occurrences of each element
int[] bucket = new int[max - min +1];
// Fill the bucket with 0, since it will add up later
Arrays.fill(bucket,0);
// The number of occurrences of each element is recorded at the corresponding position in the bucket
for(int x:arr){
bucket[x - min]++;
}
int index = 0;
// Overwrite the original ARR with the elements extracted from the bucket in turn
for(int i =0; i<bucket.length; i++){while(bucket[i] ! =0){ arr[index++] = i + min; bucket[i]--; }}return arr;
}
// ****** 10. Bucket sorting ******
/ / the main function
public static int[] BucketSort(int[] arr){
if(arr.length == 0 || arr.length == 1)
return arr;
arr = Bucket(arr,5);
return arr;
}
/ / bucket sorting
// bucketSize indicates the capacity of each bucket, and bucketCount indicates the number of buckets
public static int[] Bucket(int[] arr,int bucketSize){
int min,max;
min = max = arr[0];
for(int x:arr){
if(x > max)
max = x;
if(x > min)
min = x;
}
int bucketCount = (max - min) / bucketSize +1;
ArrayList<ArrayList<Integer>> bucket = new ArrayList<ArrayList<Integer>>();
for(int i = 0; i < bucketCount; i++) bucket.add(new ArrayList<Integer>());
for(int x: arr){
// Iterate over each bucket
for(int bucketIndex = 0; bucketIndex < bucketCount; bucketIndex++){// If the current arR element is in the range of the bucket, the element is placed in the bucket, and the loop through each bucket is completed
if(x >= min + bucketIndex*bucketSize && x < min + (bucketIndex+1)*bucketSize){
bucket.get(bucketIndex).add(x);
break; }}}int index = 0;
for(int i = 0; i < bucketCount; i++){// Use direct insert sort for each bucket to adjust the order of elements in the bucket
bucket.set(i,InsertionSortOfArrayList(bucket.get(i)));
for(int x:bucket.get(i))
arr[index++] = x;
}
return arr;
}
// Direct insertion sort for dynamic arrays
public static ArrayList<Integer> InsertionSortOfArrayList(ArrayList<Integer> arr){
if(arr.size() == 0 || arr.size() ==1)
return arr;
int current;
int pre;
for(int i = 0; i < arr.size() -1; i++){ pre = i; current = arr.get(i+1);
while(arr.get(pre) > current && pre >= 0){
arr.set(pre+1,arr.get(pre));
pre--;
}
arr.set(pre+1,current);
}
returnarr; }}Copy the code