Java 데이터 구조에서 삽입 정렬과 Hill 정렬을 구현하는 방법

1. 텍스트

1. 정렬의 개념과 적용

1.1 정렬의 개념

Sorting: 소위 정렬은 하나 이상의 레코드를 만드는 것입니다. 일부 키 단어 크기를 오름차순 또는 내림차순으로 정렬하는 작업.

안정성: 정렬할 레코드 순서에 동일한 키워드를 가진 여러 레코드가 있다고 가정합니다. 정렬하면 이러한 레코드의 상대적 순서는 변경되지 않습니다. 즉, 원래 순서에서는 r[i]= r입니다. [j], r[i]가 r[j] 앞에 있고, 정렬된 시퀀스에서 r[i]가 여전히 r[j] 앞에 있으면 이 정렬 알고리즘은 안정적이라고 합니다. 그렇지 않으면 불안정하다고 합니다.

내부 정렬: 모든 데이터 요소가 메모리에 배치되는 정렬입니다.

외부 정렬: 동시에 메모리에 배치할 수 없는 데이터 요소가 너무 많습니다. 정렬 프로세스 요구 사항에 따라 데이터를 내부 메모리와 외부 메모리 간에 이동할 수 없습니다.

1.2 정렬 응용 프로그램

정렬의 기본 개념을 읽은 후 어떤 친구들은 정렬을 배워도 실생활에 도움이 될까요?라고 묻습니다. 사실 정렬은 삶의 모든 곳에 있습니다. 예를 들어 제품의 다양한 차원의 선택이나 대학 순위 등 사실 그 뒤에는 정렬을 배우는 아이디어가 있습니다. 차원은 삶의 모든 측면을 관찰하고 삶의 문제를 더 잘 해결하는 데 도움이 됩니다. ㅋㅋㅋ : 선택 정렬, 힙 정렬

3

교환 정렬: 버블 정렬, 퀵 정렬

4병합 정렬

: 병합 정렬

2. 삽입 정렬 알고리즘 구현

길이 관계로 인해 이 글에서는 삽입 정렬에는 직접 삽입 정렬과

힐 정렬

을 주로 소개하는데, 직접 삽입 정렬을 흔히 삽입 정렬이라고 합니다.

2.1 삽입 정렬

2.1.1 기본 개념

직접 삽입 정렬은 간단한 삽입 정렬 방법입니다 정렬할 레코드를 키 값의 크기에 따라 하나씩 삽입하는 것이 기본 개념입니다. 정렬된 순서대로 모든 레코드가 삽입될 때까지 새로운 순서의 순서가 얻어집니다

     

사실 포커를 할 때 우리는 삽입 정렬이라는 아이디어를 사용합니다.

새 카드를 뽑으면 자연스럽게 손에 들고 있는 기존 카드더미와 하나씩 비교하고, 비교 후 있어야 할 곳에 놓아두게 됩니다. 따라서 우리는 삽입 정렬이 무엇인지 알지 못할 수도 있지만, 우리의 잠재의식적 접근 방식은 정확히 삽입 정렬과 일치합니다. 2.1.2 직접 삽입 정렬

직접 삽입 정렬을 설명하려면 좀 더 다양한 언어를 사용하세요. i(i>=1) 요소를 삽입할 때 이전 array[0], array[1],&hellip ;, array[i-1]이 정렬되었습니다. 이때 array[i]의 정렬 코드를 사용하여 array[i-1], array[i-2],...의 정렬 코드 순서를 비교합니다. 삽입 위치를 찾으세요. 즉, array[i]가 삽입되고 원래 위치의 요소 순서가 뒤로 이동됩니다

하지만 일부 친구는 이해하지 못할 수도 있으므로 일반 용어로 설명하겠습니다. 이제

여러분 앞에 무질서한 배열이 있습니다. 우리의 목적은 이 무질서한 배열을 오름차순 또는 내림차순

으로 조정하는 것입니다.

          오름차순을 예로 들면 배열이 순서가 없으므로 배열의 두 번째 요소부터

정렬을 시작 해야 합니다. 왜 첫 번째가 아닌가? 숫자가 하나만 있으면 다른 요소와 비교할 수 없기 때문에 당연히 무질서가 발생하지 않습니다. 따라서 요소가 하나만 있으면 기본적으로 순서가 지정됩니다.

두 번째 요소부터 정렬해야 하는 이유를 이해한 후에는 이제 요소를 순서대로 삽입하고 정렬해야 합니다. 첫 번째는 두 번째 요소의 삽입 및 정렬입니다. 아래 그림에서 두 번째 요소는 44입니다. 44는 첫 번째 요소보다 3만큼 크므로 두 번째 요소를 이동할 필요가 없습니다. 다음은 세 번째 요소의 삽입 및 정렬입니다. 세 번째 요소(38)가 두 번째 요소(44)보다 작아서 오름차순에 대한 기대를 충족하지 못하므로 44를 38의 위치로 이동합니다. 세 번째 요소, 정렬 결과 38이 3보다 큰 것을 확인했습니다. 즉, 첫 번째 요소와 두 번째 요소도 순서대로 있으므로 이때 첫 번째 요소의 위치를 ​​이동할 필요가 없음을 확인했습니다. 38은 배열 요소의 두 번째 요소에 있어야 하므로 두 번째 요소 위치에 38을 삽입하면 됩니다. 나는 여기에 후속 요소를 삽입하고 정렬하는 작업이 직접 이루어져야 한다고 생각합니다. 다음 단계는 코드를 작성하는 것입니다. 코드 측면에서 위 요소의 삽입 및 정렬을 어떻게 구현할 수 있습니까? 두 가지 주요 변수

"des"

및 "end"를 사용했습니다. des는 삽입하려는 요소의 초기 첨자이고, end는 삽입 전 시퀀스의 마지막 요소의 첨자를 나타냅니다. des, end는 계속해서 전진할 것이므로 end stop의 움직임, 즉 비교의 끝은 언제일 것인가? 크게 두 가지 상황으로 나눌 수 있다. ① des로 표현되는 요소가 end로 표현되는 요소보다 크다. ②end 요소는 시퀀스의 첫 번째 요소에 도달했습니다. 이때 des는 첫 번째 요소이거나 두 번째 요소입니다. ㅋㅋ 시간 복잡도: O(N^2)3 공간 복잡도: O(1), 안정적인 정렬 알고리즘4 안정성: 안정적

2.1.3 Hill 정렬(감소 증분 정렬)

Hill 정렬 방법은 축소 증분 방법이라고도 합니다.

Hill 정렬 방법의 기본 아이디어는 먼저 정수를 선택하고, 정렬할 파일의 모든 레코드를 정수 그룹으로 나누고, 거리가 있는 모든 레코드를 같은 그룹에 넣은 다음, 레코드를 정수 그룹으로 정렬하는 것입니다. 각 그룹 . 그런 다음 위의 그룹화 및 정렬 작업을 반복합니다. 정수가 1이면 모든 레코드가 동일한 그룹으로 정렬됩니다. ㅋㅋㅋ > 그래서 어떤 친구들은 이것을 보고 왜 다중 삽입 정렬을 수행하는지 묻습니다. 단일 삽입 정렬과 일반 삽입 정렬의 차이점은 무엇입니까? 걱정하지 마세요. 아래에서 하나씩 답변해드리겠습니다. ㅋㅋㅋ >                                                  . 따라서 Hill 정렬의 목적은 마지막 정렬이 일반적인 삽입 정렬이라는 점을 제외하고 요소 집합을 지속적으로 순서에 가깝도록 조정하는 것입니다.尔 그러면 마지막 삽입을 제외한 Hill 정렬과 일반 삽입 정렬의 차이점을 알아보세요. 위의 삽입 정렬 연구를 통해 무질서한 배열의 경우 요소가 올바른 위치에 도달하려면 다른 요소와 하나씩, 즉 단계별로 이동해야 함을 알 수 있습니다. 배열의 요소 수가 적을 때는 문제가 없지만 배열의 요소 수가 많을 때는 오름차순으로 배열의 가장 큰 요소가 배열의 첫 번째 위치에 있다고 상상해 보세요. 이 요소는 배열의 다른 요소와 하나씩 비교한 후에만 배열의 마지막 위치에 도달할 수 있습니다. 그러나 비교 속도를 높이면, 즉 비교되는 두 요소 사이의 거리가 늘어납니다. 이 요소는 그렇지 않으면 더 빨리 목적지에 도달할 수 있습니다

. 날아다니는 체스 상황을 가정하면, 삽입 정렬은 매번 1을 던지고, 마지막 삽입 정렬을 제외한 해시 정렬은 1의 포인트를 던지고, 나머지 삽입 정렬은 모두 1보다 크다. 따라서 해시 정렬이 가능하다고 생각된다. 정렬이 더 빨리 끝날 수 있습니다.

친구의 이해를 돕기 위해 코드의 이 부분을 두 부분으로 나눕니다: ① 고정 단계 직접 삽입 정렬 ② 해시 정렬.

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

//固定步伐的直接插入排序[升序]
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
위 내용은 Java 데이터 구조에서 삽입 정렬과 Hill 정렬을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!