Java Implement various internal sorting algorithms

Common internal sorting algorithm in data structure ：

Insertion sort ： Direct insert sort 、 Binary Insertion Sort 、 Shell Sort

Exchange sort ： Bubble sort 、 Quick sort

Selection sort ： Simple selection sort 、 Heap sort

Merge sort 、 Radix sorting 、 Count sorting

Direct insert sort ：

thought ： One record to be sorted at a time , Insert it into the previously ordered subsequence according to its keyword size , Until all records are inserted .

performance ： Time complexity ： best o(n)： Orderly , The worst o(n^2)： The reverse , Average o(n^2); Spatial complexity o(1); Stable

public int[] straightInsertSort(int array[]){
int temp;
for(int i=1; i<array.length; i++){ // In turn 1 To array.length-1 Elements to process
temp = array[i];
for(int j=0; j<i; j++){ // Ordered 0 To i-1 Elements
if(temp < array[j]){ // Insertion position j
for(int k=i-1;k>=j;k--){ // take j To i-1 Move elements back one position
array[k+1]=array[k]; // here array[i] Is the largest value in the ordered subarray
}
array[j] = temp; // Will be the first i Elements inserted into position j On
break;
}
}
}
return array;
}

Binary Insertion Sort ：

thought ： Use the method of half search to find the location of the element to be inserted , Then move all the elements after the position to be inserted , Finally, insert the element to be inserted into the corresponding position .

performance ： On average , Comparison times o(nlogn), Number of moves o(n^2)

Time complexity : best o(n)： Orderly , The worst o(n^2)： The reverse , Average o(n^2); Spatial complexity o(1); Stable

public int[] binaryInsertSort(int[] array){
int temp,low,high;
for(int i=1; i<array.length; i++){
temp = array[i];
// From ordered 0 To i-1 Of the elements , Find the location of the element to be inserted in half
low = 0;
high = i-1;
while(low <= high){
if(array[(low+high)/2] <= array[i]){
low = (low+high)/2 + 1;
}else{
high = (low+high)/2 - 1;
}
}
// Move the position to be inserted low To i-1 All the elements between
for(int j=i-1; j>=low; j-- ){
array[j+1] = array[j];
}
array[low] = temp;
}
return array;
}

Shell Sort ：

thought ： Divide the sort table into several shapes, such as L[i,i+d,i+2d,…,i+kd] Of “ special ” Sub table , Direct insertion sorting is carried out respectively , When the elements in the whole table have been rendered “ The basic order ” when , Do a direct insertion sort for all records again （d=1 when ）.

Step setting :d1=array.length/2;di=di/2, The last increment is 1;

performance ： Time complexity ： The worst o(n^2), Average o(n^1.3), Spatial complexity o(1), unstable

public int[] shellSort(int[] array){
for(int d=array.length/2; d>=1; d=d/2){ // Use the step value to control the number of cycles
for(int i=d;i<array.length;i++){
int temp = array[i];
if(temp < array[i-d]){ // take array[i] Inserted into an ordered increasing quantum table
int j;
for(j=i-d;j>=0 && temp<array[j];j-=d){
array[j+d]=array[j]; // Record back , Find the insertion position
}
array[j+d] = temp;
}
}
}
return array;
}

Bubble sort ：

thought ： For the sort table , Compare the values of adjacent elements from front to back , If it’s in reverse order , The exchange , Until the sequence comparison is complete . such , Each bubble will get the largest element in the current list to be sorted , And has been placed in the corresponding position .

performance ： Time complexity ： best o(n) Orderly , The worst o(n^2) The reverse , Average o(n^2), Spatial complexity o(1), Stable

public int[] bubbleSort(int[] array){
boolean flag = false; // Used to mark whether the sequence is ordered
for(int i=0;i<array.length-1;i++){ // do n-1 Bubbling
for(int j=0;j<array.length-i-1;j++){
if(array[j]>array[j+1]){
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
flag = true; // There's element exchange , Then the initial state of the sequence is not ordered
}
}
if(flag == false){ // There is no exchange after this traversal , The table is in order
return array;
}
}
return array;
}

Quick sort ：

thought ： Based on the idea of divide and rule ： Take any element in the table to be sorted pivot As a benchmark , The table to be sorted is divided into two parts by one-time sorting , Make all elements in a part less than or equal to pivot, All the elements in the other part are greater than pivot, be pivot In its final position , This process is called a quick sort . Then repeat the above process recursively for the two sub tables , Until there is only one element or empty in each part .

performance ：  Spatial complexity ： Recursive working stack is required ： The worst o(n), Average o(logn)

Time complexity ： The worst :o(n^2) The initial table is basically ordered or inversely ordered , Average o(n*logn)

unstable

public int[] quickSort(int[] array,int low,int high){
if(low<high){ // The conditions for recursion to jump out
int mid= partition(array, low, high); // Divide , Get the following table of pivot values
quickSort(array,low,mid-1); // Recursively sort the two tables in turn
quickSort(array,mid+1,high);
}
return array;
}
// Partition function for quick sort
public int partition(int[] array,int low, int high){
int pivot = array[low]; // Take the first element in the array as the benchmark
while(low < high){ // The conditions for jumping out of the loop
while(low<high && array[high] > pivot){ // Start on the right and find the first one less than or equal to pivot Value
high--;
}
while(low<high && array[low] < pivot){ // Start on the left and find the first greater than or equal to pivot Value
low++;
}
int temp = array[low]; // In exchange for
array[low] = array[high];
array[high] = temp;
if(low<high && array[low] == pivot && array[high] == pivot){ // A special case
low++;
}
}
return low;
}

Simple selection sort ：

thought ： Suppose the sort table array[0,…,n-1], The first i The sequence is from array[0,…,n-1] Select the element with the smallest keyword and array[i] In exchange for , Each sort can determine the final position of an element , Go through like this n-1 You can get the whole sequence in order .

performance ： Time complexity ：o(n^2), Spatial complexity o(1), unstable

public int[] simpleSelectSort(int[] array){
for(int i=0;i<array.length -1;i++){ // A total of n-1 Trip to
int min = i; // Record minimum element position
for(int j=i+1;j<array.length;j++){ // stay array[i,...,n-1] Choose the smallest element in
if(array[j] < array[min]){
min = j; // Update the position of the smallest element
}
}
int temp = array[i]; // Combine the smallest element with the first i A place exchange
array[i] = array[min];
array[min] = temp;
}
return array;
}

Heap sort ：Java Implement heap sort （ Big root pile ）

Merge sort ：

thought ：“ Merger ” To combine two or more ordered tables into a new ordered table . Suppose the table to be sorted contains n A record , It can be seen as n An ordered sub table , The length of each sub table is 1, And then they merge , obtain （n/2） A length of 2 or 1 The order sheet ; And then we merge ,…, repeat , Until it’s merged into a length of n Order table of , This sorting method is called 2- Path merging and sorting .

Recursively 2- Path merging sorting algorithm is based on divide and conquer , The process is as follows ：

decompose ： Will contain n The list of elements to be sorted is divided into each containing n/2 Sub table of elements , use 2- The path merging sorting algorithm sorts two sub tables recursively ;

Merge ： Merge two sorted sub tables to get the sort result .

performance ： Spatial complexity ：o(n); Time complexity :o(nlogn); Stable

public int[] mergeSort(int[] array,int low, int high){
if(low < high){ // The condition for the end of recursion
int mid = (low + high)/2; // Two way merge sort , Divide two subsequences from the middle 【 The decomposition process 】
mergeSort(array, low, mid); // Sort the left subsequence recursively
mergeSort(array, mid+1, high); // Sort the right subsequence recursively
merge(array,low,mid,high); // Merger 【 Merging process 】
}
return array;
}
// Merge two adjacent ordered tables into one ordered table
private void merge(int[] array,int low, int mid, int high){
int[] tempArray = new int[array.length]; // Auxiliary array tempArray
for(int i=low;i<=high;i++){ // take array Array [low...high] Copy the elements of to the auxiliary array tempArray in
tempArray[i] = array[i];
}
int i,j,k;
for(i=low,j=mid+1,k=i;i<=mid && j<=high;k++){
if(tempArray[i]>tempArray[j]){ // Compare tempArray The elements in the left and right ends of
array[k] = tempArray[j++]; // Copy smaller values to array in
}else{
array[k] = tempArray[i++];
}
}
while(i<=mid){ // If the first table is not detected , Copy
array[k++] = tempArray[i++];
}
while(j<=high){ // If the second table is not checked out , Copy
array[k++] = tempArray[j++];
}
}

Press Ctrl+C Copy code

Radix sorting ：

  Based on the count sort ： Java To realize the cardinal sort based on the idea of bucket sort and count sort

  Based on queue assisted implementation ：

thought ： Cardinal sort is not based on comparison , But using the idea of multi keyword sorting , With the help of “ Distribute ” and “ collect ” Two operations sort single logical keywords .

  Cardinal sort is to use multiple keywords to achieve local order first , Readjust to achieve overall order .

performance ： Spatial complexity ：o(r); Time complexity ：o(d(n+r)); Stable

among ,r Cardinal number ,d Is the number of digits of the largest keyword （ Determines the number of times to sort ）,n Is the number of elements in the list to be sorted .

// Radix sort based on queue aided implementation
public int[] radixSort(int[] array){
// Find the largest element in the sequence to be sorted
int max = array[0];
for(int i=1; i<array.length;i++){
if(array[i] > max){
max = array[i];
}
}
// Determine the number of digits of the largest element maxBits
int maxBits = 0;
while(max > 0){
max = max/10;
maxBits ++;
}
// establish 10 A queue
Queue<Integer>[] queue = new LinkedList[10];
for(int i=0; i<queue.length; i++){
queue[i] = new LinkedList<Integer>();
}
// Conduct maxBits Sub distribution and collection
for(int i=0; i<maxBits;i++){
// Allocation array
for(int j=0; j<array.length;j++){
// Get the first of the elements maxBits position , Then insert the element into the corresponding position
queue[(array[j] % (int)Math.pow(10, i+1))/(int)Math.pow(10, i)].add(array[j]);
}
// Element counter
int count = 0;
// Collect queue elements
for(int k=0;k<queue.length;k++){
while(queue[k].size() > 0){
array[count++] = queue[k].poll().intValue();
}
}
}
return array;
}

Count sorting ：

Premise ： All the keywords in the to sort table must be different from each other ;

thought ： The count sort algorithm is for each record in the table , Scan the table to be sorted once , How many records in the statistical table have a smaller key than the key of the record , Suppose for a record , The count is calculated as c, Then the storage location of the record in the new ordered table is c.

performance ： Spatial complexity ：o(n); Time complexity :o(n^2);

public int[] countSort(int[] array){
int[] tempArray = new int[array.length]; // Introduce auxiliary array
for(int i=0;i<array.length;i++){
int count = 0;
for(int j=0;j<array.length;j++){
if(array[i]>array[j]){
count++;
}
}
tempArray[count] = array[i];
}
return tempArray;
}

Reference blog ：

https://www.cnblogs.com/CherishFX/p/4644996.html