C# 빠른 정렬

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)!