C# Quick Sort
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Sort { class QuickSorter { private static int[] myArray; private static int arraySize; public static int[] Sort(int[] a) { arraySize = a.Length; QuickSort(a, 0,arraySize- 1); return a; } private static void QuickSort(int[] myArray, int left, int right) { int i, j, s; if (left < right) { i = left - 1; j = right + 1; s = myArray[(i + j) / 2]; while (true) { while (myArray[++i] < s) ; while (myArray[--j] > s) ; if (i >= j) break; Swap(ref myArray[i], ref myArray[j]); } QuickSort(myArray, left, i - 1); QuickSort(myArray, j + 1, right); } } private static void Swap(ref int left, ref int right) { int temp; temp = left; left = right; right = temp; } } }
빠른 정렬의 개념:
정렬할 배열이 A[0]...A[N-1]이라고 가정하고 먼저 선택합니다. 임의의 데이터(보통 배열의 첫 번째 숫자 선택)를 키 데이터로 삼고, 그보다 작은 숫자는 모두 앞에 넣고, 그보다 큰 숫자는 모두 뒤에 넣습니다. 이 과정을 빠른 정렬이라고 합니다. 퀵 정렬은 안정적인 정렬 알고리즘이 아니라는 점, 즉 여러 개의 동일한 값의 상대적 위치가 알고리즘 종료 시 변경될 수 있다는 점은 주목할 가치가 있습니다.
원 패스 퀵 정렬의 알고리즘은 다음과 같습니다.
1) 정렬 시작 시 두 개의 변수 i와 j를 설정합니다. i=0, j=N-1; >2) 첫 번째 배열 요소를 키 데이터로 사용하여 키에 할당합니다. 즉, key=A[0]
3) j부터 앞으로 검색, 즉 뒤에서 앞으로 검색합니다. (j- -), key보다 작은 첫 번째 값 A[j]를 찾아 A[j]로 값 key와 항목을 교환합니다.
4) i부터 역방향으로 검색합니다. , 앞에서 시작하여 뒤로 검색(i++)하여 키보다 큰 첫 번째 A[i]를 찾고 A[i]와 값 키가 있는 항목을 교환합니다.
5) 3단계를 반복합니다. 🎜>
6) i=j가 될 때까지 3, 4, 5단계를 반복합니다. (3, 4단계에서는 조건을 충족하는 값이 발견되지 않습니다. 즉, 3의 A[j]가 다음보다 작지 않을 때입니다. key, 4의 A[j]는 key보다 크지 않다. 조건에 맞는 값을 찾을 때까지 j=j-1, i=i+1이 되도록 j와 i의 값을 변경하면 된다. i 및 j 포인터 위치는 변경되지 않습니다. 프로세스는 정확히 i+ 또는 j-가 완료되고 루프가 종료되는 시점에 이루어져야 합니다. 예: 배열을 예로 들어 범위의 첫 번째 숫자를 기본 숫자로 사용합니다.i = 3;
j부터 시작하여 앞으로 검색합니다. j=5일 때 조건이 충족되면 a[5]를 파내어 이전 구멍에 채웁니다. a[3] = a[5];i부터 시작하여 역방향으로 검색합니다. i=5이면 i==j이므로 종료됩니다. 이때, i = j = 5이고 a[5]는 지난번에 파놓은 구멍이니까 X를 a[5]에 채워주세요. 배열은 다음과 같습니다.
위는 C# 퀵 정렬의 내용입니다. 자세한 내용은 PHP 중국어 웹사이트(www. .php.cn)!