Summary of the hill sort of the Java sort algorithm
- 2020-04-01 03:50:15
- OfStack
This article illustrates the hill sort summary of the Java sort algorithm. Share with you for your reference. Specific analysis is as follows:
preface : Shell Sort is a type of insertion Sort. It is an improvement of direct insertion sort algorithm. This method, also known as reduced delta sort, got its name from dl.shell, which was proposed in 1959. This article focuses on how hill sort is implemented in Java.
Hill sort (reduction increment method) belongs to insertion sort, which is to divide the whole non-sequence into several small sub-sequences for insertion sort. The hill sort is not stable, O of 1 extra space, time order N times logN ^ 2. The worst case performance is comparable to the average performance.
Basic ideas:
Take an integer less than n, d1, as the first increment, and divide all the records in the file into d1 groups. All records of distance multiples of d1 are placed in the same group. First, direct insertion sort is performed in each group. And then you take the second increment, d2< D1 repeat the above grouping and sorting until the increment dt=1(dt< Dt - l< ... < D2 < D1), that is, until all records are placed in the same group for direct insertion sort.
Code implementation:
public class Test {
public static int[] a = { 10, 32, 1, 9, 5, 7, 12, 0, 4, 3 };
//Default data array
public static void main(String args[]) {
int i; //Loop count variable
int Index = a.length;//Data index variable
System.out.print(" Before ordering : ");
for (i = 0; i < Index - 1; i++)
System.out.printf("%3s ", a);
System.out.println("");
ShellSort(Index - 1); //Selection sort
//Sorted result
System.out.print(" After ordering : ");
for (i = 0; i < Index - 1; i++)
System.out.printf("%3s ", a);
System.out.println("");
}
public static void ShellSort(int Index) {
int i, j, k; //Loop count variable
int Temp; //Temporary variable
boolean Change; //Whether the data has changed or not
int DataLength; //The interval length of the split set
int Pointer; //The location where the processing takes place
DataLength = (int) Index / 2; //Length of initial set interval
while (DataLength != 0) //The sequence can still be partitioned
{
//The individual sets are processed
for (j = DataLength; j < Index; j++) {
Change = false;
Temp = a[j]; //Store the value of Data[j] temporarily to be exchanged
Pointer = j - DataLength; //Calculate the location of the processing
//Compare and exchange the values of the values in the set
while(Temp < a[Pointer] && Pointer >= 0 && Pointer <= Index){
a[Pointer + DataLength] = a[Pointer];
//Calculate the next position to be processed
Pointer = Pointer - DataLength;
Change = true;
if (Pointer < 0 || Pointer > Index)
break;
}
//With the final value
a[Pointer + DataLength] = Temp;
if (Change) {
//Print the current sorted results
System.out.print(" The sorting of : ");
for (k = 0; k < Index; k++)
System.out.printf("%3s ", a[k]);
System.out.println("");
}
}
DataLength = DataLength / 2; //Calculate the interval length of the next partition
}
}
}
Hill sort has almost no worst-case scenarios, whether it's positive order, reverse order, out of order, it doesn't take a lot of time, the additional storage is O (1), which is really good. Before you figure out quicksort, heap sort, it's a good choice. I hope I can help you.
I hope this article has been helpful to your Java programming.