안정적인 정렬 알고리즘은 무엇입니까?

안정적인 정렬 알고리즘은 다음과 같습니다. 1. 버블 정렬 3. 삽입 정렬 5. 병합 정렬 7. 힙 정렬

이 튜토리얼의 운영 환경: Windows 10 시스템, Dell G3 컴퓨터.

일반적인 정렬 알고리즘의 안정성을 분석하고 각각에 대한 간단한 이유를 설명합니다.

안정적인 정렬 알고리즘:

1. 버블 정렬

버블 정렬은 작은 요소를 앞으로 이동하거나 큰 요소를 뒤로 이동하는 것입니다. 비교는 인접한 두 요소를 비교하는 것이며, 이 두 요소 간에도 교환이 발생합니다. 그래서 두 요소가 동일하다면 지루하게 바꾸지는 않을 것이라고 생각합니다.

두 개의 동일한 요소가 인접하지 않은 경우 이전 쌍 교환을 통해 두 요소가 인접하더라도 이때는 교환되지 않으므로 동일한 요소의 순서는 변경되지 않았으므로 버블 정렬은 A 안정 정렬 알고리즘.

2. 선택 정렬

선택 정렬은 각 위치에 대해 가장 작은 요소를 선택하고, 나머지 요소 중 두 번째 요소에 대해 두 번째로 작은 요소를 선택합니다. n-1 요소까지는 n번째 요소가 남아 있는 유일한 가장 큰 요소이므로 선택할 필요가 없습니다. 그런 다음 선택에서 현재 요소가 요소보다 작고 작은 요소가 현재 요소와 동일한 요소 뒤에 나타나면 교환 후 안정성이 파괴됩니다. n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。

比较拗口，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。

3、插入排序

插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。

如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。

所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

4、快速排序

快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a[j]>a[center_index]。

如果i和j都走不动了，i<=j，交换a[i]和a[j]，重复上面的过程，直到i>j。交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为5 3 3 4 3 8 9 10 11，现在中枢元素5和3（第5个元素，下标从1开始计）交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j] 交换的时刻。

5、归并排序

归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素（认为直接有序）或者2个序列（1次比较和交换），然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2

발음하기가 좀 어렵습니다. 예를 들어 5 8 5 2 9 시퀀스에서 1번째 요소 5를 선택한다는 것을 알고 있습니다. > 첫 번째 패스에서 2가 교환되면 원래 시퀀스에서 2와 5의 상대적 순서가 파괴되므로 선택이 일치합니다. 정렬은 안정적인 정렬 알고리즘이 아닙니다.

3. 삽입 정렬

삽입 정렬은 이미 정렬된 작은 시퀀스를 기반으로 한 번에 하나의 요소를 삽입합니다. 물론 처음에는 이 작은 순서의 시퀀스에는 첫 번째 요소인 단 하나의 요소만 있었습니다. 비교는 정렬된 시퀀스의 끝부터 시작됩니다. 즉, 삽입하려는 요소가 이미 정렬된 가장 큰 요소와 비교됩니다. 이 요소가 그보다 크면 바로 뒤에 삽입하고, 그렇지 않으면 다음 항목이 나올 때까지 계속 찾습니다. 위치에 삽입되어야 하는 요소를 찾으세요.

삽입된 요소와 동일한 요소가 발견되면 삽입된 요소는 동일한 요소 뒤에 삽입하려는 요소를 배치합니다.

따라서 동일한 요소의 순서는 변경되지 않았습니다. 원래 순서가 지정되지 않은 순서가 정렬된 순서이므로 삽입 정렬이 안정적입니다.

🎜4. 빠른 정렬🎜🎜🎜왼쪽의 i 첨자는 a[i] <= a[center_index]일 때 두 가지 방향이 있습니다. 여기서 center_index는 중앙 요소의 배열 인덱스이며 일반적으로 배열의 0 요소로 사용됩니다. 오른쪽의 j 아래 첨자는 a[j]>a[center_index]일 때 왼쪽 끝까지 갑니다. 🎜🎜i와 j가 모두 걸을 수 없으면 i<=j, a[i]와 a[j]를 교환하고, 반복하세요. 위의 과정은 i>j까지 계속됩니다. a[j]와 a[center_index]를 바꿔서 빠른 정렬을 완료하세요. 피벗 요소가 a[j]로 교환되면 이전 요소의 안정성이 손상될 가능성이 매우 높습니다. 예를 들어 순서는 5 3 3 4 3 8 9입니다. 10 11, 이제 허브 요소 5 및 3(5 요소, 아래 첨자는 1에서 시작) code>)가 바뀌게 되면 요소 3의 안정성이 무너지므로 퀵 정렬은 중심 요소와 a[j]가 바뀌는 순간 불안정성이 발생하는 정렬 알고리즘이다. 🎜🎜🎜5. 병합 정렬🎜🎜🎜병합 정렬은 시퀀스를 짧은 시퀀스로 재귀적으로 나눕니다. 재귀 종료는 짧은 시퀀스에 <code>1 요소(직접 정렬된 것으로 간주)만 있다는 것입니다. 2 code> 시퀀스(1 비교 및 ​​교환)를 수행한 다음 정렬된 각 세그먼트 시퀀스를 정렬된 긴 시퀀스로 병합하고 원래 시퀀스가 ​​모두 정렬될 때까지 계속 병합합니다. 1 또는 2 요소가 있는 경우 1 요소는 교환되지 않고 2 요소가 있는 것을 알 수 있습니다. 요소의 크기가 동일하고 아무도 의도적으로 교체하지 않으면 안정성이 손상되지 않습니다. 🎜🎜그렇다면 Short Ordered Sequence를 병합하는 과정에서 안정성이 파괴되는 걸까요? 🎜🎜아니요, 병합 프로세스 중에 현재 두 요소가 동일하면 결과 시퀀스 앞에 이전 시퀀스의 요소를 저장하여 안정성을 보장할 수 있습니다. 따라서 병합 정렬도 안정적인 정렬 알고리즘입니다. 🎜🎜🎜6. 기수 정렬🎜🎜🎜Radix 정렬은 먼저 낮은 순서로 정렬한 다음 🎜🎜높은 순서로 정렬한 다음 🎜;

그리고 가장 높은 위치까지 계속됩니다. 일부 속성에는 우선순위가 낮은 순서로 정렬된 다음 높은 우선순위로 정렬되는 경우가 있습니다. 최종 순서는 높은 우선순위와 낮은 우선순위가 동일한 순서로 정렬되는 것입니다. 기수 정렬은 분리 정렬과 분리 수집을 기반으로 하므로 안정적인 정렬 알고리즘입니다.

7. 힐 정렬(쉘)

힐 정렬은 요소가 처음에 매우 무질서한 경우 요소를 삽입하고 정렬하는 것입니다. 삽입 정렬은 매우 적고 매우 빠릅니다.

요소가 기본적으로 정렬되어 있고 단계 크기가 작은 경우 삽입 정렬은 정렬된 시퀀스에 매우 효율적입니다. 따라서 Hill 정렬의 시간 복잡도는 O(n^2)보다 좋습니다. 다중 삽입 정렬로 인해 우리는 하나의 삽입 정렬이 안정적이며 동일한 요소의 상대적 순서를 변경하지 않는다는 것을 알고 있습니다. 그러나 다른 삽입 정렬 프로세스에서는 동일한 요소가 각각의 삽입 정렬에서 이동할 수 있으며 최종적으로 안정성이 향상됩니다. 변경 내용이 뒤섞여 있어 쉘 정렬이 불안정합니다. O(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。

8、堆排序

我们知道堆的结构是节点i的孩子为2 * i和2 * i + 1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列，堆排序的过程是从第n / 2开始和其子节点共3个值选择最大（大顶堆）或者最小（小顶堆），这3个元素之间的选择当然不会破坏稳定性。但当为n / 2-1， n/2-2，...1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1

8. 힙 정렬

우리는 힙의 구조가 i 노드의 하위 항목이 2 * i 및 2 * i라는 것을 알고 있습니다. + 1 노드, 큰 상위 힙은 상위 노드가 2 하위 노드보다 크거나 같아야 하고, 작은 상위 힙은 상위 노드가 이보다 작거나 같아야 합니다. 2 하위 노드에. 길이가 n인 순서에서 힙 정렬 과정은 n/2와 그 하위 노드에서 시작하여 총 3에서 가장 큰 값을 선택하는 것입니다. >(큰 상단 힙) 또는 가장 작은(작은 상단 힙) 3 요소 중에서 선택해도 안정성이 파괴되지는 않습니다. 그러나 상위 노드 n/2-1, n/2-2, ...1에 대한 요소를 선택하면 안정성이 손상됩니다. . n/2번째 상위 노드는 다음 요소를 교환하는 반면 n/2-1번째 상위 노드는 다음과 같은 요소를 교환하지 않을 수 있습니다. 이 두 개의 동일한 요소 사이의 안정성이 파괴됩니다. 따라서 힙 정렬은 안정적인 정렬 알고리즘이 아닙니다. 🎜🎜더 많은 관련 지식을 알고 싶다면 🎜FAQ🎜 칼럼을 방문해주세요! 🎜

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