데이터 구조 6 - 정렬 알고리즘 (정렬, 힐 정렬, 빠 른 정렬, 병합 정렬 과 정렬 직접 삽입)

모든 정렬 에서 정렬 해 야 할 배열 array 의 0 위 는 올 바른 숫자 를 저장 하지 않 고 보초병 으로 존재 합 니 다.
1. 정렬 바로 삽입
        정렬 을 직접 삽입 하 는 기본 동작 은 정렬 된 표 에 기록 을 삽입 하여 새로운 기록 1 의 질서 표를 얻 는 것 이다.무질서 한 숫자 array (동시에 길이 가 1 인 질서 표 로 볼 수 있 습 니 다). 1 이후 의 모든 위치 에서 자신의 적당 한 위 치 를 찾 아 삽입 하고 싶 습 니 다. i 위 (i 는 2 부터) 숫자 를 자신의 위치 에 삽입 하려 면 예전 i - 1 위 부터 순서대로 비교 (앞 자리 보다 크 고 뒷 자리 보다 작 음) 하고 기록 을 뒤로 옮 겨 야 합 니 다.순서 표 의 길이 가 배열 array 의 길이 일 때 까지.

/// 

///     
/// 
public void InsertSort(int[] array)
{
    int i = 0, j = 0;

    for (i = 2; i < array.Length; i++)
    {
        if (array[i] < array[i - 1])
        {
            array[0] = array[i];
            array[i] = array[i - 1];
            for (j = i - 2; array[0] < array[j]; j--)
            {
                array[j + 1] = array[j];
            }
            array[j + 1] = array[0];
        }
    }
}

        정렬 을 직접 삽입 하면 원래 질서 있 는 배열 에 정렬 하 는 데 적합 합 니 다. 배열 이 질서 가 있 을 수록 삽입 하 는 횟수 가 적 기 때 문 입 니 다.시간 복잡 도 는 O (n ^ 2) 입 니 다.
2. 힐 정렬
        힐 정렬 은 정렬 을 직접 삽입 하 는 개량 판 이다.그의 사상 은 먼저 전체 대기 기록 서열 을 여러 개의 하위 서열 로 나 누 어 각각 순 서 를 직접 삽입 하고 전체 서열 이 '기본 적 인 질서' 가 있 을 때 전체 기록 에 대해 직접 순 서 를 삽입 하 는 것 이다.

/// 

///     
/// 
/// 
public void ShellSort(int[] array)
{
    int[] dlta = new[] {5, 3, 1};

    for (int i = 0; i < dlta.Length; i++)
    {
        ShellInsert(array, dlta[i]);
    }
}

private void ShellInsert(int[] array, int dk)
{
    int i = 0, j = 0;

    for (i = dk + 1; i < array.Length; i++)
    {
        if (array[i] < array[i - dk])
        {
            array[0] = array[i];
            for (j = i - dk; j > 0 && array[0] < array[j]; j -= dk)
            {
                array[j + dk] = array[j];
            }
            array[j + dk] = array[0];
        }
    }
}

3. 빠 른 정렬
        빠 른 정렬 은 거품 정렬 의 개선 판 이다.그의 기본 사상 은 한 번 의 정렬 을 통 해 정렬 기록 을 독립 된 두 부분 으로 나 누 는 것 이다. 그 중에서 일부 기록 의 키 워드 는 모두 다른 부분 에 기 록 된 키워드 보다 작 으 면 이 두 부분의 기록 을 계속 정렬 할 수 있 고 전체 서열 이 질서 가 있다 는 것 이다.

/// 

///     
/// 
/// 
public void QuickSort(int[] array)
{
    QSort(array, 1, array.Length - 1);
}

private void QSort(int[] array, int low, int high)
{
    if (low < high)
    {
        int pivokey = Partition(array, low, high);
        QSort(array, low, pivokey - 1);
        QSort(array, pivokey + 1, high);
    }
}

private int Partition(int[] array, int low, int high)
{
    array[0] = array[low];
    int pivokey = array[low];
    while (low < high)
    {
        while (low < high && array[high] >= pivokey) high--;
        array[low] = array[high];
        while (low < high && array[low] <= pivokey) low++;
        array[high] = array[low];
    }
    array[low] = pivokey;
    return low;
}

        빠 른 정렬 은 '어 지 러 운' 서열 에 적합 합 니 다. 만약 에 서열 이 질서 가 있 으 면 빠 른 정렬 이 매우 느 릴 것 입 니 다.시간 복잡 도 O (nlogn).
4. 병합 정렬
        병합 정렬 의 사상 은 최초의 서열 표 의 모든 키 워드 를 하나의 서열 표 로 본 다음 에 인접 한 두 순서 목록 을 하나의 서열 표 로 합 쳐 정렬 하고 여러 번 합 친 후에 최종 적 으로 하나의 표 만 남 는 것 이다.

/// 

///     
/// 
/// 
public void MergeSort(int[] array)
{
    //    
    for (int i = 1; i < array.Length; i *= 2)
    {
        MergePass(array, i);
    }
}

private void Merge(int[] array, int low, int mid, int high)
{
    int i = low;
    int j = mid + 1;
    int k = 0;
    int[] array2 = new int[high - low + 1];

    while (i <= mid && j <= high)
    {
        if (array[i] <= array[j])
        {
            array2[k] = array[i];
            i++;
            k++;
        }
        else
        {
            array2[k] = array[j];
            j++;
            k++;
        }
    }

    while (i <= mid)
    {
        array2[k] = array[i];
        k++;
        i++;
    }

    while (j <= high)
    {
        array2[k] = array[j];
        k++;
        j++;
    }

    for (k = 0, i = low; i < high; k++, i++)
    {
        array[i] = array2[k];
    }
}

private void MergePass(int[] array, int gap)
{
    int i =0;
    for (i = 0; i + 2*gap - 1 < array.Length; i += 2*gap)
    {
        Merge(array, i, i + gap - 1, i + 2*gap - 1);
    }
    if (i + gap - 1 < array.Length)
    {
        Merge(array, i, i + gap - 1, array.Length - 1);
    }
}

        병합 정렬 은 매우 안정 적 인 정렬 로 대부분 상황 에서 정렬 시간 이 작은 범위 로 안 정 될 수 있다.시간 복잡 도 O (nlogn).
5. 쌓 기 정렬
        서열 이 Ki > = K (2i) & & Ki > = K (2i + 1) 를 만족 시 킬 때 이 서열 은 바로 큰 지붕 더미 이다. 쉽게 말 하면 이 진 트 리 를 만 들 고 그 뿌리 노드 는 두 개의 노드 보다 크다.쌓 아 올 리 는 순 서 는 이런 큰 지붕 더 미 를 만들어 야 한다. 쌓 아 올 리 는 것 이 가장 큰 숫자 이다. 우 리 는 쌓 아 올 리 는 지붕 을 서열 의 끝까지 옮 긴 다음 에 큰 지붕 더 미 를 다시 만 들 고 이전의 절 차 를 반복 한다.

/// 

///    
/// 
/// 
public void HeapSort(int[] array)
{
    for (int i = array.Length/2; i >= 1; i--)                //           Lenth/2
    {
        HeapAdjust(array, i, array.Length - 1);
    }
    for (int i = array.Length - 1; i > 1; i--)
    {
        int temp = array[1];
        array[1] = array[i];
        array[i] = temp;

        HeapAdjust(array, 1, i - 1);
    }
}

private void HeapAdjust(int[] array, int s, int m)
{
    int tmp = array[s];
    for (int j = 2*s; j <= m; j *= 2)
    {
        if (j < m && array[j] < array[j + 1]) j++;
        if (tmp < array[j])
        {
            array[s] = array[j];
            s = j;
        }
                    
        else
            break;
    }
    array[s] = tmp;
}

        쌓 기 정렬 은 기록 이 적은 파일 을 정렬 하 는 데 적합 하지 않 지만 큰 파일 을 정렬 하 는 데 적합 합 니 다.시간 복잡 도 O (nlogn)