C# 병합 정렬
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Sort { class MergeSorter { /// <summary> /// 归并排序之归:归并排序入口 /// </summary> /// <param name="data">无序数组</param> /// <returns>有序数组</returns> public static int[] Sort(int[] data) { //若data为null,或只剩下1 or 0个元素,返回,不排序 if (null == data || data.Length <= 1) { return data; } //取数组中间下标 int middle = data.Length >> 1; //初始化临时数组let,right,并定义result作为最终有序数组,若数组元素奇数个,将把多余的那元素空间预留在right临时数组 int[] left = new int[middle]; int[] right = new int[data.Length - middle]; int[] result = new int[data.Length]; for (int i = 0; i < data.Length; i++) { if (i < middle) { left[i] = data[i]; } else { right[i-middle] = data[i]; //此处i-middle,让我省掉定义一个j,性能有所提高 } } left = Sort(left);//递归左数组 right = Sort(right);//递归右数组 result = Merge(left, right);//开始排序 return result; } /// <summary> /// 归并排序之并:排序在这一步 /// </summary> /// <param name="a">左数组</param> /// <param name="b">右数组</param> /// <returns>合并左右数组排序后返回</returns> private static int[] Merge(int[] a, int[] b) { //定义结果数组,用来存储最终结果 int[] result = new int[a.Length + b.Length]; int i = 0, j = 0, k = 0; while (i < a.Length && j < b.Length) { if (a[i] < b[j])//左数组中元素小于右数组中元素 { result[k++] = a[i++];//将小的那个放到结果数组 } else//左数组中元素大于右数组中元素 { result[k++] = b[j++];//将小的那个放到结果数组 } } while (i < a.Length)//这里其实是还有左元素,但没有右元素 { result[k++] = a[i++]; } while (j < b.Length)//有右元素,无左元素 { result[k++] = b[j++]; } return result;//返回结果数组 } } }
병합 정렬:
병합 정렬 방법은 두 개 이상의 순서 목록을 새로운 순서 목록으로 병합하는 것입니다. 즉, 정렬된 시퀀스는 여러 하위 시퀀스로 나뉩니다. , 각 하위 시퀀스는 순서가 지정됩니다. 그런 다음 정렬된 하위 시퀀스를 전체 정렬된 시퀀스에 병합합니다. 이 알고리즘은 분할 정복(Divide and Conquer) 방식을 사용하는 매우 일반적인 응용 프로그램입니다.
순서가 지정된 하위 시퀀스를 병합하여 완전히 정렬된 시퀀스를 얻습니다. 즉, 먼저 각 하위 시퀀스를 정렬한 다음 하위 시퀀스 세그먼트를 정렬합니다. 두 개의 순서 목록이 하나의 순서 목록으로 병합되는 경우 이를 양방향 병합이라고 합니다.
정렬되지 않은 시퀀스가 있다고 가정하면 먼저 분할 방법을 사용하여 시퀀스를 정렬된 하위 시퀀스로 나눈 다음 병합 방법을 사용하여 하위 시퀀스를 하나씩 분리합니다. 분할 및 병합 과정은 아래 범례에서 볼 수 있습니다.
위 그림에서 알 수 있듯이 먼저 정렬되지 않은 시퀀스를 가운데부터 2부분으로 나눈 다음, 2개 부분으로 4개 부분으로 나누고, 하나씩 데이터로 분할될 때까지 순서대로 나누고, 이 데이터들을 합쳐서 순서대로 만들고, 계속 병합하여 최종적으로 순서가 있는 순서가 됩니다.
두 개의 정렬된 하위 시퀀스를 하나의 정렬된 시퀀스로 병합하는 방법은 무엇입니까? 아래 방법을 참고하시면 됩니다.
두 개의 정렬된 하위 시퀀스가 있다고 가정합니다.
시퀀스 A: 1 23 34 65
시퀀스 B: 2 13 14 87
그런 다음 아래 단계에 따라 하나의 시퀀스로 병합할 수 있습니다.
(1) 먼저 새로운 시퀀스 C[8]을 설정합니다.
(2) A[0]과 B[0]을 비교하고, A[0] = 1, B[0] = 2, A[0] < B[0], 그러면 C[0] = 1
(3) A[1]과 B[0]을 비교하면 A[1] = 23, B[0] = 2, A[1] > B[0], 그러면 C[1] = 2
(4) A[1]과 B[1]을 비교하면 A[1] = 23, B[1] = 13, A[1] > B[1]이면 C[2] = 13
(5) A[1]과 B[2]를 비교하면 A[1] = 23, B[2] = 14, A[1] > B[2]이면 C[3] = 14
6) A[1]과 B[3]을 비교하면 A[1] = 23, B[3] = 87, A[1] (7 ) A[2]와 B[3]을 비교하면 A[2] = 34, B[3] = 87, A[2] (8) A[3]과 B[3]을 비교하면 A[3] = 65, B[3] = 87, A[3] (9) 마지막으로; B[3]을 C에 복사한 다음 C[7] = 87을 복사합니다. 병합이 완료되었습니다.
C# 시프트 연산(왼쪽 시프트 및 오른쪽 시프트)
병합 정렬, 시간 복잡도는 O(nlogn)입니다.
병합 정렬의 효율성은 상대적으로 높습니다. 시퀀스의 길이가 N이라고 가정합니다. 각 단계는 순서가 지정된 시퀀스를 병합하는 프로세스입니다. O(N)으로 기록되므로 합계는 O(N*logN)입니다. 병합 정렬은 매번 인접한 데이터에 대해 작동하기 때문에 O(N*logN)의 여러 병합 정렬(빠른 정렬, 병합 정렬, 힐 정렬, 힙 정렬)도 상대적으로 효율적입니다.
위 내용은 C# 병합정렬 내용입니다. 더 많은 관련 내용은 PHP 중국어 홈페이지(www.php.cn)를 참고해주세요!