간단한 정렬 알고리즘

오늘날의 IT 산업은 직원이 너무 많아서 주니어 프로그래머가 과잉되는 결과를 낳고, 이로 인해 간접적으로 회사의 채용 기준이 높아지고 프로그래머가 점점 더 많은 지식을 습득해야 합니다.

알고리즘은 오랫동안 논의되어 온 주제이기도 합니다. 프로그래머는 알고리즘을 마스터해야 할까요? 실제로 많은 회사에서는 알고리즘에 대한 특정 요구 사항을 가지고 있습니다. 일부 회사에서는 면접 중에 면접관이 직접 알고리즘 질문을 작성하도록 요구합니다. 이는 프로그래머의 기술적 요구 사항에 대한 큰 테스트입니다. 따라서 오늘날의 환경에 직면하여 향후 작업에서 자리를 차지하려면 알고리즘을 마스터해야 합니다.

그럼 다음에는 몇 가지 정렬 알고리즘에 대해 간략하게 소개하겠습니다. 도움이 되셨으면 좋겠습니다.

버블 정렬

버블 정렬(Bubble Sort)은 더 간단한 정렬 알고리즘입니다.

정렬할 요소의 열을 반복해서 방문하여 인접한 두 요소를 차례로 비교하고 순서(예: 큰 것에서 작은 것, 첫 글자는 A에서 Z까지)가 잘못된 경우 교체합니다. 요소를 방문하는 작업은 인접한 요소를 교환할 필요가 없을 때까지 반복됩니다. 이는 요소 열이 정렬되었음을 의미합니다.

이 알고리즘의 이름은 탄산 음료의 이산화탄소 거품이 결국 위로 떠오르는 것과 마찬가지로 더 큰 요소가 교환(오름차순 또는 내림차순으로 정렬)을 통해 시퀀스의 맨 위로 천천히 "부유"한다는 사실에서 유래되었습니다. 따라서 이름은 "버블 정렬"입니다.

데모:

코드는 다음과 같습니다:

@Test
public void bubbleSort() {
	int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
	// 统计比较次数
	int count = 0;
	// 第一轮比较
	for (int i = 0; i  arr[j + 1]) {
				// 交换位置
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
			count++;
		}
	}
	System.out.println(Arrays.toString(arr));
	System.out.println("一共比较了:" + count + "次");
}

실행 결과:

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
一共比较了:105次

선택 정렬

선택 정렬은 간단하고 직관적인 정렬 알고리즘입니다. 작동 원리는 먼저 정렬할 데이터 요소에서 가장 작은(또는 가장 큰) 요소를 선택하고 이를 시퀀스의 시작 부분에 저장한 다음 정렬되지 않은 나머지 요소에서 가장 작은(가장 큰) 요소를 찾아 배치하는 것입니다. 정렬된 순서가 끝나면 정렬할 모든 데이터 요소의 수가 0이 될 때까지 계속됩니다. 선택 정렬은 불안정한 정렬 방법입니다.

데모:

코드는 다음과 같습니다.

@Test
public void SelectionSort() {
	int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
	for (int i = 0; i <p>실행 결과: </p><pre class="brush:php;toolbar:false">[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

구현도 매우 간단합니다. 첫째, i의 값을 저장하기 위해 인덱스 변수가 정의됩니다. 반복되는 비교를 피하는 것입니다. 각 비교 라운드 후에 첫 번째 i 요소가 이미 정렬되어 있으므로 다시 비교할 필요가 없으며 i부터 시작하면 됩니다. 이후의 비교는 모두 인덱스 위치의 요소를 기준으로 합니다. 비교 후 인덱스 위치의 요소가 최소값인 경우 교환할 필요가 없으며 이동하지 마세요. 그리고 index 위치에 있는 요소보다 작은 요소가 발견되면 그 요소의 인덱스를 index에 할당하고, 비교가 완료될 때까지 계속해서 비교를 수행하며, 비교가 완료된 후 얻은 인덱스가 배열의 최소값이 됩니다. , 그러면 이때 인덱스 위치의 요소를 i 위치의 요소로 교체하면 됩니다.

삽입 정렬

삽입 정렬은 간단하고 직관적이며 안정적인 정렬 알고리즘입니다. 이미 정렬된 데이터 시퀀스가 ​​있고 정렬된 데이터 시퀀스에 숫자를 삽입해야 하지만 삽입 후에도 데이터 시퀀스가 ​​계속 정렬되는 경우 새로운 정렬 방법인 삽입 방법이 필요합니다. 삽입 정렬은 정렬된 데이터에 데이터를 삽입하여 숫자에 1을 더한 새로운 정렬된 데이터를 얻는 알고리즘입니다. 이 알고리즘은 적은 양의 데이터를 정렬하는 데 적합합니다. 시간 복잡도는 O(n입니다. ^2). 안정적인 정렬 방법입니다. 삽입 알고리즘은 정렬할 배열을 두 부분으로 나눕니다. 첫 번째 부분에는 마지막 요소를 제외한 배열의 모든 요소가 포함되며(배열에 삽입 위치를 확보할 수 있는 공간이 하나 더 추가됨) 두 번째 부분에는 이 요소만 포함됩니다. 하나의 요소(즉, 삽입할 요소). 첫 번째 부분이 정렬된 후 이 마지막 요소가 정렬된 첫 번째 부분에 삽입됩니다.

삽입 정렬의 기본 개념은 다음과 같습니다. 각 단계에서 정렬할 레코드가 모두 삽입될 때까지 키 값의 크기에 따라 이전에 정렬된 배열의 적절한 위치에 삽입됩니다.

Demonstration:

코드는 다음과 같습니다:

@Test
public void InsertionSort() {
	int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
	for (int i = 1; i = 0 && insertValue <p>실행 결과: </p><pre class="brush:php;toolbar:false">[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

여기에서는 배열 요소가 확실하지 않기 때문에 배열의 첫 번째 요소만 순서가 있는 것으로 간주할 수 있습니다. 하나의 시퀀스이므로 배열의 두 번째 요소부터 시작하여 삽입 위치를 찾는 데 필요한 요소입니다. 그래서 외부 루프는 1부터 시작하여 현재 두 번째 요소인 arr[i]를 저장한 다음 잠시 동안 삽입할 요소의 이전 요소 첨자인 i-1을 찾습니다. 비교할 루프입니다.

insertIndex가 0보다 작으면 루프를 종료해야 합니다. 이전의 모든 요소와 비교되었기 때문입니다. 비교 과정에서 삽입할 요소가 이전 요소보다 작은 경우 이전 요소를 뒤로 이동시킵니다. 즉, 삽입할 요소의 위치에 이전 요소의 값이 직접 대입됩니다. 삽입할 요소는 처음에 저장되어 있으므로 이전 요소에 삽입할 요소의 값만 대입하면 됩니다. insertIndex는 while 루프에서 자체 감소 연산을 수행하므로 이전 요소 첨자는 insertIndex + 1이어야 합니다. 그리고 삽입할 요소의 값이 이전 요소보다 크면 while 루프에 들어가지 않으므로 insertIndex + 1 이후의 위치는 여전히 자체 위치이므로 할당 후에도 값이 변경되지 않습니다. 후속 작업에 대해서도 마찬가지입니다.

위 내용은 간단한 정렬 알고리즘의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!