Java commonly used sorting algorithm and performance test collection
- 2020-04-01 02:02:28
- OfStack
Now go back to the understanding, combined with their own experience, choose the best way to describe these algorithms, in order to understand how they work and programming skills. This article is suitable for Java interview preparation materials to read.
Attached is a test report:
Array length: 20000
The bubbleSort: 766 ms
BubbleSortAdvanced: 662 ms
BubbleSortAdvanced2:647 ms
SelectSort: 252 ms
InsertSort: 218 ms
InsertSortAdvanced: 127 ms
InsertSortAdvanced2:191 ms
BinaryTreeSort: 3 ms
ShellSort: 2 ms
ShellSortAdvanced: 2 ms
ShellSortAdvanced2:1 ms
MergeSort: 3 ms
QuickSort: 1 ms
HeapSort: 2 ms
By testing, it can be argued that bubble sort is perfectly justified in the bin. The only reason it exists is probably best understood. The efficiency of hill sort is something I didn't expect; Heap sort is more difficult to understand and write, to have a macro thinking.
package algorithm.sort;
import java.lang.reflect.Method;
import java.util.Arrays;
import java.util.Date;
/**
* Java Commonly used sorting algorithm and performance test set
*
* This program set covers the preparation of common sorting algorithms, and in the comments with very simple special cases explained the working principle of various algorithms, in order to facilitate understanding and absorption;
* There was a lot of wikipedia and other people in the process blog The above examples, combined with their own thinking, choose and improve the most easy to understand the writing method
* (especially quicksort, which I think is the best algorithm to understand).
* Includes a centralized performance test and correctness test method for easy observation.
* @author /link.php?url=http://blog.csdn.net/sunxing007
* Please quote from /link.php?url=http://blog.csdn.net/sunxing007
*/
public class SortUtil {
//The set of methods being tested
static String[] methodNames = new String[]{
"bubbleSort",
"bubbleSortAdvanced",
"bubbleSortAdvanced2",
"selectSort",
"insertSort",
"insertSortAdvanced",
"insertSortAdvanced2",
"binaryTreeSort",
"shellSort",
"shellSortAdvanced",
"shellSortAdvanced2",
"mergeSort",
"quickSort",
"heapSort"
};
public static void main(String[] args) throws Exception{
//correctnessTest();
performanceTest(20000);
}
public static void correctnessTest() throws Exception{
int len = 10;
int[] a = new int[len];
for(int i=0; i<methodNames.length; i++){
for(int j=0; j<a.length; j++){
a[j] = (int)Math.floor(Math.random()*len*2);
}
Method sortMethod = null;
sortMethod = SortUtil.class.getDeclaredMethod(methodNames[i], a.getClass());
Object o = sortMethod.invoke(null, a);
System.out.print(methodNames[i] + " : ");
if(o==null){
System.out.println(Arrays.toString(a));
}
else{
//Both mergeSort, its sorting results in the form of a return value;
System.out.println(Arrays.toString((int[])o));
}
}
}
public static void performanceTest(int len) throws Exception{
int[] a = new int[len];
int times = 20;
System.out.println("Array length: " + a.length);
for(int i=0; i<methodNames.length; i++){
Method sortMethod = null;
sortMethod = SortUtil.class.getDeclaredMethod(methodNames[i], a.getClass());
int totalTime = 0;
for(int j=0; j<times; j++){
for(int k=0; k<len; k++){
a[k] = (int)Math.floor(Math.random()*20000);
}
long start = new Date().getTime();
sortMethod.invoke(null, a);
long end = new Date().getTime();
totalTime +=(end-start);
}
System.out.println(methodNames[i] + " : " + (totalTime/times) + " ms");
//System.out.println(Arrays.toString(a));
}
}
public static void bubbleSort(int[] a){
for(int i=0; i<a.length; i++){
for(int j=0; j<a.length-i-1; j++){
if(a[j]>a[j+1]){
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
}
}
public static void bubbleSortAdvanced(int[] a){
int k = a.length-1;
boolean flag = true;
while(flag){
flag = false;
for(int i=0;i<k;i++){
if(a[i]>a[i+1]){
int tmp = a[i];
a[i] = a[i+1];
a[i+1] = tmp;
//If there is exchange, the flag bit continues to be maintained;
flag = true;
}
}
k--;
}
}
public static void bubbleSortAdvanced2(int[] a){
int flag = a.length - 1;
int k;
while(flag>0){
k = flag;
flag = 0;
for(int i=0; i<k; i++){
if(a[i] > a[i+1]){
int tmp = a[i];
a[i] = a[i+1];
a[i+1] = tmp;
//Where an exchange occurs, the last place of comparison is recorded;
flag = i+1;
}
}
}
}
public static void insertSort(int[] a){
//Traverse from the unordered header;
for(int i=1; i<a.length; i++){
int j;
//Compare the elements of a[I] with the elements of an ordered table to find an appropriate location.
for(j=i-1;j>=0; j--){
if(a[j] < a[i]){
break;
}
}
//If the appropriate position is found, the element is moved back one space from that position to make room for the inserted element.
if(j!=(i-1)){
int tmp = a[i];
int k;
for(k = i-1; k>j;k--){
a[k+1] = a[k];
}
a[k+1] = tmp;
}
}
}
public static void insertSortAdvanced(int[] a){
//Traversing an unordered table;
for(int i=1; i<a.length; i++){
//If the unordered table head element is smaller than the ordered table tail, adjustment is needed;
if(a[i]<a[i-1]){
int tmp = a[i];
int j;
//Search and compare from the end of the ordered table, and move elements greater than a[I] back to make room;
for(j=i-1; j>=0&&a[j]>tmp;j--){
a[j+1] = a[j];
}
a[j+1] = tmp;
}
}
}
public static void insertSortAdvanced2(int[] a){
//Traversing the unordered table
for(int i=1; i<a.length; i++){
//Take a[I] start bubbling at the end of the ordered list;
for(int j=i-1; j>=0 && a[j] > a[j+1]; j--){//A [m + 1] is a [I]
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
}
public static void quickSort(int[] a, int low, int high){
if(low>=high){
return;
}
int low0 = low;
int high0 = high;
boolean forward = false;
while(low0!=high0){
if(a[low0]>a[high0]){
int tmp = a[low0];
a[low0] = a[high0];
a[high0] = tmp;
forward = !forward;
}
if(forward){
low0++;
}
else{
high0--;
}
}
low0--;
high0++;
quickSort(a, low, low0);
quickSort(a, high0, high);
}
public static void quickSort(int[] a){
quickSort(a, 0, a.length-1);
}
public static int[] merge(int[] a, int[] b){
int result[] = new int[a.length+b.length];
int i=0,j=0,k=0;
while(i<a.length&&j<b.length){
if(a[i]<b[j]){
result[k++] = a[i];
i++;
}
else{
result[k++] = b[j];
j++;
}
}
while(i<a.length){
result[k++] = a[i++];
}
while(j<b.length){
result[k++] = b[j++];
}
return result;
}
public static int[] mergeSort(int[] a){
if(a.length==1){
return a;
}
int mid = a.length/2;
int[] leftPart = new int[mid];
int[] rightPart = new int[a.length-mid];
System.arraycopy(a, 0, leftPart, 0, leftPart.length);
System.arraycopy(a, mid, rightPart, 0, rightPart.length);
leftPart = mergeSort(leftPart);
rightPart = mergeSort(rightPart);
return merge(leftPart, rightPart);
}
public static void selectSort(int[] a){
for(int i=0; i<a.length; i++){
int minIndex = i;
for(int j=i+1; j<a.length; j++){
if(a[j]<a[minIndex]){
minIndex = j;
}
}
int tmp = a[i];
a[i] = a[minIndex];
a[minIndex]= tmp;
}
}
/**
* Hill sorting <br>
* The idea is to have an array of equal steps (/ spacing ) Divide into multiple sub-sequences, do ordinary insertion sort for each sub-sequence, <br> Decrease the step size until 1 The last time I do a normal insertion sort;
* In an extreme example, I have the following sequence: <br>
* [1,2,3,4,5,6,7,8,9,10];<br>
* At the beginning, the step size gap=5 ; Then the subarray divided is [1,6], [2,7], [3,8], [4,9], [5,10];<br> Sort them separately ( Of course, because this array is special, the result is the same ) ; <br>
* then gap=2=5/2; Subarray for [1,3,5,7,9], [2,4,6,8,10]; <br>
* The last gap=1=2/2; Do a global sort; <br>
* <br>
* Hill sort overcomes insertion / The weakness of bubble sort ( You can only move an element one adjacent position at a time ), <br> Depending on the stride length, the element can be moved to the target position as soon as possible ( In or near the );<br>
* Hill sort is actually a variant of insertion sort. It is applicable to: when the array is generally ordered, the individual needs to adjust the case; And that's where the advantage of insertion sort comes in O(n) The efficiency; <br>
* An important factor affecting the hill algorithm is the selection of step size. The advantage of a good step size is that the short step size sort after will not destroy the long step sort before. <br>
* What makes sense of this destruction? The long step in front moves a smaller number to the left, but may be switched to the right after the smaller step ( Because it was assigned to a group with many smaller groups ) ; <br>
* For the step size, you can check http://zh.wikipedia.org The above page on hill sort; <br>
* The following program is the most basic way to write hill sort, suitable for understanding hill sort ideas; <br>
*/
public static void shellSort(int[] a){
//Control spacing; The spacing decreases until it is 1;
for(int gap = a.length/2; gap>0; gap/=2){
//Scan each subarray
for(int i=0; i<gap; i++){
//For each word group, scan the disordered area; Notice the increment;
//A [I] is the initial ordered region;
for(int j=i+gap; j<a.length; j+=gap){
//The first element of the disordered area is smaller than the last element of the ordered area, indicating that adjustment is needed
if(a[j]<a[j-gap]){
int tmp = a[j];
int k = j-gap;
//Search forward from the end of the ordered area to find the appropriate location;
while(k>=0&&a[k]>tmp){
a[k+gap] = a[k];
k-=gap;
}
a[k+gap] = tmp;
}
}
}
}
}
public static void shellSortAdvanced(int[] a){
//The control step
for(int gap = a.length/2; gap>0; gap/=2){
//Start from the unordered area, put multiple subarrays together processing;
for(int j=gap; j<a.length; j++){
//The following logic is the same as the above;
if(a[j]<a[j-gap]){
int tmp = a[j];
int k = j-gap;
while(k>=0&&a[k]>tmp){
a[k+gap] = a[k];
k-=gap;
}
a[k+gap] = tmp;
}
}
}
}
public static void shellSortAdvanced2(int[] a){
for(int gap = a.length/2; gap>0; gap/=2){
for(int i=gap; i<a.length; i++){
if(a[i]<a[i-gap]){
for(int j=i-gap; j>=0&&a[j+gap]>a[j]; j-=gap){
int tmp = a[j];
a[j] = a[j+gap];
a[j+gap] = tmp;
}
}
}
}
}
/**
* Heap sort <br>
* The definition of the heap: the heap is a complete, or nearly complete binary tree, the value of the heap top element is greater than the value of left and right children, left and right children also need to meet this condition; <br>
* By the definition of a heap, a heap can be a large top heap (maxHeap) Or small top pile (minHeap) ; <br>
* Arrays can be used to simulate binary trees, for any element i , left child for 2*i+1, Children right 2*i+2; The parent node is (i-1)/2;
* @param a
*/
public static void heapSort(int[] a){
//First from the last non-leaf node upward adjustment, so that the heap structure;
for(int i=(a.length-2)/2; i>=0; i--){
maxHeapAdjust(a, i, a.length);
}
//Swap the last node with the first one at a time, and then adjust the heap; Up to the top of the heap;
for(int i=a.length-1; i>0; i--){
int tmp = a[i]; a[i] = a[0]; a[0] = tmp;
maxHeapAdjust(a, 0, i);
}
}
public static void maxHeapAdjust(int[] a, int i, int len){
int tmp = a[i];
//J is the left child node
int j = i*2+1;
//
while(j<len){
//Choose the older of the two children
//J plus 1 is the right child node
if((j+1)<len && a[j+1]>a[j]){
j++;
}
//Find the right place and stop looking
if(a[j]<tmp){
break;
}
//Otherwise move the larger one up the tree;
a[i] = a[j];
//I pointed to the older child;
i = j;
//J points to the new left child node;
j = 2*i + 1;
}
//To adjust the node value to the appropriate location;
a[i] = tmp;
}
public static void binaryTreeSort(int[] a){
//A binary tree node inner class is constructed to implement binary tree sorting algorithm.
class BinaryNode{
int value;
BinaryNode left;
BinaryNode right;
public BinaryNode(int value){
this.value = value;
this.left = null;
this.right = null;
}
public void add(int value){
if(value>this.value){
if(this.right!=null){
this.right.add(value);
}
else{
this.right = new BinaryNode(value);
}
}
else{
if(this.left!=null){
this.left.add(value);
}
else{
this.left = new BinaryNode(value);
}
}
}
public void iterate(){
if(this.left!=null){
this.left.iterate();
}
//Turn off the output during testing to avoid affecting performance.
// System.out.print(value + ", ");
if(this.right!=null){
this.right.iterate();
}
}
}
BinaryNode root = new BinaryNode(a[0]);
for(int i=1; i<a.length; i++){
root.add(a[i]);
}
root.iterate();
}
}