preface

Sorting is a very important part of data structures and algorithms, and it permeates every aspect of programming.

The order by SQL
Greedy + custom sort
Handwritten fast row

However, there are many ways to implement the actual sorting algorithm. Different algorithms have different efficiency for different feature data, and different algorithms have different time complexity and space complexity.

For sorts, it is generally believed that there are eight (and nine) sorts. But in the large category of allocation, we often divide into insertion based sort (insertion sort, Hill sort); Sort based on swap (bubble sort, quick sort); Select-based sort (simple selection sort, heap sort), merge sort, and radix sort.

Insertion sort

The idea is the simplest
Until the last person in the line finishes the insertion

Although in the idea is very simple, maybe you think it is very simple to implement, the number of times, each student inserted into the appropriate position. But you would be wrong. You actually see the exact location in your mind and pass, pass, pass… The computer can only do one calculation at a time, so each time he wants to make sure he inserts it there, he has to compare it one by one. So this is order N squared. If you have a lot of data it’s actually very inefficient.

Insert sort

  • Pick the data from the first one
  • From this point to the previous point, all the way to find the first one less than you or to the first one
  • Insert to the corresponding position and repeat the first step to continue from the next element.

  • algorithmBetter for linked listsBecause lists are easier to insert and delete
  • forArray insertion, where the element is inserted in place of, byInsert and all subsequent elements move back oneIn fact this order table insertsA: it's a big spendingNot very friendly.
  • So this insertion sort if we’re using arrays we’re essentially swapping arrays multiple times to get the insertion. Refer to the data structure above for detailsThe order sheetColumn!

What about the head node of the array? Because you need to move all the way back after insertion. We just swap backwards every time we make a comparison to reduce the computation. Store the element in a temporary variable. And the leading node is the 0th one. Use the 0th as a temporary space. We also don’t need to determine if 0 is equal to 0, because 0 must be less than or equal to the element to be inserted. You can insert it right here!

Split insertion sort

What’s the connection between halfway insert sort and insert sort? First of all, the essence of half-cut insert sort is still insert sort, and it’s only partially optimized for insert sort. And the optimized part is the part that looks forward and compares. What it does is change the search from a violent enumeration to a binary search.

If it’s a long sequence
Looking up comparisons one by one might take too many times

Of course, it is a pity that halfcut insertion can reduce the number of searches, but it cannot change the time complexity of the whole algorithm (array implementation). Because while the look-up can go down to log’n on each insertion, you still have to move the swaps one by one as you move forward in the order list. Split insertion can be understood as the average time complexity for each location from O(N) lookup +O(N) swap move to O(logN) lookup +O(N) swap move. So, the total time complexity is still O(n2). However, don’t underestimate that optimization, in the case of large data, chain storage can actually save a lot of time!

Hill sorting

Because most of the sorting algorithms mentioned above are suitable for small amount of data, or in order to achieve better results. Countless awesome people are constantly trying to optimize and solve this problem. Finally, a great guy named Hill finally came up with a sort algorithm — Hill sort. The algorithm is designed by considering the two aspects of data volume and order. Also, hill sort is a combination of insertion sorts. The encyclopedia defines it as follows:

Shell’s Sort, also known as “Diminishing Increment Sort”, is a more efficient and improved version of direct insert Sort. Hill sort is an unstable sort algorithm. Hill sort is to group the records by a certain increment of the index and sort each group by direct insertion sort algorithm. As the increments decrease, each group contains more and more keywords, and when the increments decrease to 1, the entire file is exactly grouped and the algorithm terminates.

  1. Ordered sequences, because if ordered, each element is easy to find several or zero elements that are always larger than it, which is a slightly higher time complexity than the current level.
  2. Fewer elements. You can be as strong as you like, and a few elements are small potatoes no matter how square they are in front of a computer.

Clever use, segmentation
Long list of
According to some mathematical model
Take more than
Reduce the length to insert sort separately
Small numbers are in the back
Fewer times move to the front of the relative test
The sequence
More orderly

The previous grouping mod is equivalent to preprocessing according to this rule. By the last time it was very regular (at least odd and even numbers were ordered separately), the complexity of the whole insertion sort was greatly reduced, and there were very few numbers that had to be moved by a large amount.

Although hill sort looks like a few more sorts. But a few more times in front of a long string of data is younger than the squaring index. Although the proof of Hill sort is a problem, and the partition value is not the best theoretical proof. Marx once said: Practice is the sole criterion for testing truth. Practice tests it is good, it is good!

The implementation code

packageEight kinds;import java.util.Arrays;

public classDirectly inserted into the{

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int a[]= {21.25.8.7.45.2.8.18.9.88.3};
		int b[]=new int[10];
		a=insertsort(a);
		System.out.println(Arrays.toString(a));
		System.out.println();
		b=shellsort(a);
		System.out.println(Arrays.toString(a));
	}
		
	static int [] insertsort (int a[])
	{
		int team=0;
		for(int i=1; i<a.length; i++) { System.out.println(Arrays.toString(a)); team=a[i];for(int j=i-1; j>=0; j--) {if(a[j]>team)
				{
					a[j+1]=a[j];
					a[j]=team;	
				}	
				else {
					break; }}}return a;		
	}
	static int [] shellsort (int a[])
	{
		int d=a.length;
		int team=0;// Temporary variables
		for(; d>=1; d/=2)
		for(inti=d; i<a.length; i++) { System.out.println(Arrays.toString(a)); team=a[i];for(intj=i-d; j>=0; j-=d) {if(a[j]>team)
				{
					a[j+d]=a[j];
					a[j]=team;	
				}
				else {
					break; }}}returna; }}Copy the code

Finally, if you feel ok, please like!Keep sharing! Welcome to follow the author’s official account:bigsaiWelcome to exchange! IT circle is not too many friends, I also hope to be your friend,Learn together and make progress together!