How to implement insertion sort and Hill sort in Java data structure

1. Text

1. The concept of sorting and its application

1.1 The concept of sorting

Sort: The so-called sorting is the operation of arranging a string of records in ascending or descending order according to the size of one or some keywords in it.

Stability: Assume that there are multiple records with the same keywords in the record sequence to be sorted. If sorted, the relative order of these records remains unchanged, that is, in the original In the sequence, r[i]=r[j], and r[i] is before r[j], and in the sorted sequence, r[i] is still before r[j], it is called this sorting An algorithm is stable; otherwise it is said to be unstable.

Internal sorting: Sorting in which all data elements are placed in memory.

External sorting: There are too many data elements that cannot be placed in the memory at the same time. According to the requirements of the sorting process, the data cannot be moved between internal and external memory.

1.2 Sorting application

After reading the basic concepts of sorting, some friends may ask, even if I learn sorting, will it be of any use in real life? ? In fact, sorting is everywhere in life, such as the choice of different dimensions of a product, or the ranking of colleges and universities. In fact, there is the idea of ​​​​sorting behind it. Learn to sort well, and you can Help us observe all aspects of life from another dimension and help us better solve problems in life.

1.3 Common sorting algorithms

In the data structure, our common There are four sorting algorithms:

①Insertion sort: direct insertion sort, Hill sort

②Selection sort: selection sort, heap sort

③Exchange sort: Bubble sort, quick sort

④Merge sort: Merge sort

2 .Implementation of insertion sort algorithm

Due to space constraints, in this article we mainly introduce direct insertion sort and Hill sort in insertion sort. , and direct insertion sort is often called insertion sort.

2.1 Insertion sort

2.1.1 Basic idea

Direct insertion sort is a simple insertion sort method

Its The basic idea isInsert the records to be sorted into an already sorted ordered sequence one by one according to the size of their key values, until all records are inserted, and a new ordered sequence is obtained

                  In fact, when we play poker, we use the idea of ​​​​insertion sorting. When you draw a new card, you will naturally compare it one by one with the existing card pile in your hand, and put it into the position where it should be after comparison. So we may not know what insertion sort is, but our subconscious approach is exactly in line with insertion sort.

2.1.2 Direct insertion sort

Use a more written language to describe direct insertion sort: When inserting the i-th (i>=1) element, the previous The array[0], array[1],..., array[i-1] have been sorted. At this time, use the sort code of array[i] and array[i-1], array[i-2], …Compare the order of the sorting codes, find the insertion position and insert array[i], and the order of the elements at the original position will be moved back

But some friends may not understand it, so let’s put it in layman’s terms Let’s talk. Now there is a disordered array in front of you, our purpose is to adjust this disordered array into ascending or descending order .

Taking ascending order as an example, since the array is unordered, we need tostart sorting from the second element of the array. Why not the first one? Because when there is only one number, you cannot compare it with other elements. Naturally, there is no such thing as disorder. Therefore, when there is only one element, we default to it being ordered.

After understanding why we need to start sorting from the second element, now we have toinsert and sort the elements in sequence. The first is the insertion and sorting of the second element. In the picture below, we will find that the second element is 44. 44 is greater than the first element by 3, so there is no need to move the second element. Next is the insertion and sorting of the third element. We found that the third element 38 is smaller than the second element 44, which does not meet our expectations for ascending order, so we move 44 to the position of 38. Between the second and third elements, After sorting, we found that 38 is greater than 3, that is, the first and second elements are also in order, so there is no need to move the position of the first element. At this time, we have confirmed that 38 should be in the second element in the array. element, so we just insert 38 into the second element's position. I believe that the friends who have seen this should be able to insert and sort subsequent elements easily.

The next step is to write the code. In terms of code, how can we implement the insertion and sorting of the above elements? We have taken two main variables "des" and "end", des is the initial index of the element we want to insert, and end represents the sequence before insertion. The subscript of the last element, with the comparison of des, end will continue to move forward, so when will the movement of end stop, that is, the end of the comparison, which can be roughly divided into two situations : ①The element represented by des is greater than the element represented by end ②end has reached the first element of the sequence. At this time, des is either the first element or the second element.

The specific pictures and codes are as follows:

##

//插入排序[升序]
int* InsertSort(int* arr, int n)
{
 
	//整体排序
	for (int i = 1; i < n; i++)
	{
		int end = i - 1;
		int des = arr[i];
		//单趟排序
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			arr[end+1] = des;
		}
	}
}

Note:

is inserted directly Summary of sorting characteristics

①The closer the element set is to order, the higher the time efficiency of the direct insertion sort algorithm

②Time complexity: O(N^2)

③ Space complexity: O(1), it is a stable sorting algorithm

④ Stability: stable

2.1.3 Hill sorting (reducing increment Sorting)

Hill sorting method is also called the reducing increment method.

The basic idea of ​​Hill sorting method is: first select an integer, divide all the records in the file to be sorted into integer groups, put all the records with a distance of The records are sorted. Then repeat the above grouping and sorting work. When the integer equals 1, all records are sorted in the same group.

Generally speaking,

Hill sorting is multiple direct insertion sorting

, but the sorting except for the last direct insertion sorting is different from the original direct insertion sorting. So when some friends see this, they may ask why multiple insertion sorts are performed. What is the difference between single insertion sort and normal insertion sort? Don’t worry, we will answer them one by one below. First, why do we need to insert sort multiple times? After reading the above summary of the characteristics of insertion sort, we will find that

When the collection of elements is closer to order, the time efficiency of insert sorting will be The higher

. Therefore, the purpose of Hill sorting, except that the last sorting is normal insertion sorting, is to continuously adjust the set of elements so that it is constantly close to ordering. The next step is the difference between Hill sorting and normal insertion sorting except for the last insertion sorting. Through the above study of insertion sort, we will find that for a disordered array, if an element wants to reach the correct position, it must be compared with other elements one by one, that is, moved step by step. This kind of movement This is okay when the number of elements in the array is small, but when the number of elements in the array is large, in ascending order, imagine that the largest element in the array is located at the first position of the array, then is it necessary to This element can only reach the last position of the array after comparing it one by one with the other elements in the array. However, when we

increase the pace of comparison, that is, increase the distance between the two compared elements, then this Can the element get to where it should be faster

? Put in the situation of flying chess, insertion sort throws 1 every time, and hash sort except the last insertion sort throws a point of 1, the rest of the insertion sort throws are all greater than 1. , so it is conceivable that hash sorting can reach the end of sorting faster. In order to facilitate the understanding of friends, this part of the code is divided into two parts: ① fixed-step direct insertion sort ② hash sort.

        先是固定步伐的直接插入排序，先让我们通过图片来直观的看到数组数组内的元素通过这种操作后的变化。 

//固定步伐的直接插入排序[升序]
void ShellSort(int* arr, int n)
{
	int gap = 3;
	int end;
	//有两种写法，看你要控制end，还是des
	/*for (int i=0; i < n-gap; i++)
	{
		int end = i;
		int des = arr[end + gap];
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			arr[end + gap] = des;
		}
	}*/
 
	for (int i = gap; i < n ; i++)
	{
		int end = i-gap;
		int des = arr[end + gap];
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			arr[end + gap] = des;
		}
	}
}

         接着就是希尔排序

         上述的代码是gap=3的情况下的直接插入排序，那么对于希尔排序而言，我们该对gap该如何选择呢？对于不同gap值的插入排序来说，我们会发现：gap越大，元素跳得越快，数组越不接近有序；而gap越小，元素跳的越慢，数组越接近有序。由于数组的大小不定，因此希尔排序也没有一个合适gap值适用于所有数组，显然，这个gap值一定是动态变化的。

        对于gap的动态变化，常见的有两种：

①令gap等于数组的元素个数，每次插入排序后令gap除等2

②另一种则是令gap等于数组的元素个数，不过每次插入排序后令gap除以3再加1

        无论哪种处理都能使gap动态变化并最后等于1，对数组进行一次插入排序，达到最后想要的效果。

        代码如下：

//希尔排序
void ShellSortPlus(int* arr, int n)
{
	int gap=n;
	int end;
	while (gap > 1)
	{
	gap = gap / 2;
		
		for (int i=0; i < n - gap;i++)//有两种写法，看你要控制end，还是des
		{
			int end = i;
			int des = arr[end + gap];
			while (end >= 0)
			{
				if (des >= arr[end])
					break;
				if (des < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				arr[end + gap] = des;
			}
		}
 
	}
}

二、测试代码

        为了方便小伙伴们测试排序后的效果，为大家提供了测试的代码并包含排序的具体代码和包含的头文件。

#include 
#include 
#include 
 
//插入排序[升序]
int* InsertSort(int* arr, int n)
{
 
	//整体排序
	for (int i = 1; i < n; i++)
	{
		int end = i - 1;
		int des = arr[i];
		//单趟排序
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			arr[end+1] = des;
		}
	}
}
 
//固定步伐的直接插入排序[升序]
void ShellSort(int* arr, int n)
{
	int gap = 3;
	int end;
	//有两种写法，看你要控制end，还是des
	/*for (int i=0; i < n-gap; i++)
	{
		int end = i;
		int des = arr[end + gap];
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			arr[end + gap] = des;
		}
	}*/
 
	for (int i = gap; i < n ; i++)
	{
		int end = i-gap;
		int des = arr[end + gap];
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			arr[end + gap] = des;
		}
	}
}
 
 
//希尔排序
void ShellSortPlus(int* arr, int n)
{
	int gap=n;
	int end;
	while (gap > 1)
	{
	gap = gap / 2;
		
		for (int i=0; i < n - gap;i++)//有两种写法，看你要控制end，还是des
		{
			int end = i;
			int des = arr[end + gap];
			while (end >= 0)
			{
				if (des >= arr[end])
					break;
				if (des < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				arr[end + gap] = des;
			}
		}
 
	}
}
 
//打印排序好的数组
void PrintSort(int*arr,int n)
{
	for(int i=0;i
The above is the detailed content of How to implement insertion sort and Hill sort in Java data structure. For more information, please follow other related articles on the PHP Chinese website!