1. Hill sorting

1.1 problems in simple insertion sorting

Let's look at the possible problems with simple insertion sorting
Array arr = {2,3,4,5,6,1} at this time, the number 1 to be inserted (minimum) is as follows:
{2,3,4,5,6,6}
{2,3,4,5,5,6}
{2,3,4,4,5,6}
{2,3,3,4,5,6}
{2,2,3,4,5,6}
{1,2,3,4,5,6}
Conclusion: when the number to be inserted is small, the number of backward shifts increases obviously, which has an effect on the efficiency

1.2 introduction to Hill sorting

Hill sorting is a sort algorithm put forward by Donald Shell in 1959. Hill sort is also a sort of insertion sort, which is a more efficient version of simple insertion sort after improvement, also known as reduced incremental sort.

1.3 basic idea of Hill's sorting method

Hill sorting is to group records by a certain increment of subscript, and use the direct insertion sorting algorithm to sort each group. As the increment gradually decreases, each group contains more and more keywords. When the increment is reduced to 1, the whole file is just divided into a group, and the algorithm is terminated.

1.4 schematic diagram of hill sorting method

1.5 the displacement Fisher sorting code is implemented as follows:

public static void shellSort(int[] arr){
			//Increment gap, and gradually reduce the increment
			for(int gap = arr.length/2; gap > 0 ; gap /= 2){
				//From the gap element, insert and sort the groups one by one
				for(int i = gap; i < arr.length; i++){
					int j = i;
					int temp = arr[j];
					//if(arr[j] < arr[j -gap]){
						while(j -gap >= 0 && temp < arr[j - gap]){
							//move
							arr[j] = arr[j - gap];
							j -= gap;
						}
						//When you exit while, you find the insertion position for arr[j]
						arr[j] = temp;
					//}
				}
			}
		}

Performance test of displacement Fisher sorting

public static void main(String[] args) {
		// TODO Auto-generated method stub

		//int[] arr = {8,9,1,7,2,3,5,4,6,0};
		int[] arr = new int[80000];
		for (int i = 0; i < 80000; i++) {
			arr[i] = (int) (Math.random() * 80000);// Generate a number between [080000]
		}
		Date date1 = new Date();
		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
		String date1Str = simpleDateFormat.format(date1);
		//System.out.println("array before sorting is" + Arrays.toString(arr));
		System.out.println("The time before sorting is:" + date1Str);
		shellSort(arr);//Displacement method
	//	System.out.println("sorted array is" + Arrays.toString(arr));
		Date date2 = new Date();
		String date2Str = simpleDateFormat.format(date2);
		System.out.println("The time after sorting is:"+date2Str);
	}

The test results are as follows:

2. Quick sorting

2.1 introduction to quick sorting method

Quicksort is an improvement of bubble sort. The basic idea is: divide the data to be sorted into two independent parts by a single sorting, all the data in one part is smaller than all the data in the other part, and then sort the two parts of data rapidly according to this method. The whole sorting process can be carried out recursively, so as to make the whole data into an ordered sequence.

2.2 schematic diagram of quick sorting method

3.3 code implementation of fast sorting

public static void quickSort(int[] arr,int left,int right){
		int l = left;//Left subscript
		int r = right;//Right subscript
		int pivot =  arr[(left + right) / 2];
		int temp = 0; //Temporary variable
		//The purpose of the while loop is to place values smaller than pivot on the left and values larger than pivot on the right
		while(l < r){
			//Find a value greater than or equal to pivot on the left side of pivot before exiting
			while(arr[l] < pivot){
				l += 1;
			}
			//Find all the way to the right of pivot, find the value less than or equal to pivot, and then exit
			while(arr[r] > pivot){
				r -= 1;
			}
			//If l > = R, it means that the left and right values of pivot are all values less than or equal to pivot according to the left, and the right values are all values greater than or equal to pivot
			if(l >= r){
				break;
			}
			//exchange
			temp = arr[l];
			arr[l] = arr[r];
			arr[r] = temp;
			//If the arr[l] == pivot value r moves forward after the exchange
			if(arr[l] == pivot){
				r -= 1;
			}
			//After the exchange, it is found that the arr[r] == pivot value moves backward in l + +
			if(arr[r] == pivot){
				l += 1;
			}
		}
		//If l ==r, l++,r -- is required, otherwise stack overflow occurs
		if(l == r){
			l += 1;
			r -= 1;
		}
		//Left recursion
		if(left < r){
			quickSort(arr, left, r);
		}
		//Recursion to the right
		if(right > l){
			quickSort(arr,l,right);
		}
		
	}

3.4 performance test of quick sorting:

public static void main(String[] args) {
		// TODO Auto-generated method stub

		// int[] arr = {-9,78,23,-567,70,0,-1};
		int[] arr = new int[80000];
		for(int i = 0 ; i < 80000; i++){
			arr[i] = (int)(Math.random() * 80000);//Generate a number between [0800000]
		}
		Date date1 = new Date();
		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
		String date1Str = simpleDateFormat.format(date1);
		System.out.println("The time before sorting is:"+date1Str);
		quickSort(arr, 0, arr.length - 1);
		//System.out.println("arr="+Arrays.toString(arr));
		Date date2 = new Date();
		String date2Str = simpleDateFormat.format(date2);
		System.out.println("The time after sorting is:"+date2Str);
	}

The test results are as follows: