정렬 알고리즘 면접 문제 (상)

> 1. 정렬 삽입:
정렬 기본 사상 삽입: 모든 단계 에서 정렬 할 요 소 를 정렬 코드 의 크기 에 따라 앞 에 정렬 된 요소 의 적당 한 위치 에 삽입 하고 요소 가 모두 꽂 힐 때 까지 합 니 다.i (i > = 1) 개 요 소 를 삽입 할 때 앞의 array [0], array [1],...................................................................정렬 알고리즘 을 직접 삽입 하 는 시간 효율 이 높 을 수록 가장 좋 은 경우: 시간 효율 이 O (n) 최 악의 경우: 시간 복잡 도 는 O (n ^ 2) 공간 복잡 도: O (1) 이 고 안정 적 인 정렬 알고리즘 입 니 다.

void InsertSort(DataType *a, size_t n)//    
{
    for (size_t i = 0; i1; i++)//         n-1;
    {
        DataType end=i;
        DataType tmp = a[end + 1];
        while (end >= 0 && a[end]>tmp)//            ，   
        {
            a[end + 1] = a[end];// end       
            end--;//         
        }
        a[end + 1] = tmp;//    
    }

}

2. 힐 정렬:
축소 증 량 정렬 이 라 고도 하 는데 직접 삽입 정렬 에 대한 최적화 1) 예비 정렬 이다.2) 정렬 을 직접 삽입 하면 데이터 양 이 너무 많은 상황 에서 효율 을 높 일 수 있다.

void XiErSort(DataType*a, size_t n)//    /       ，       
{
    int flag=3;
    while (flag > 1)
    {
        flag = flag / 3 + 1;//    ，flag=1    
        for (size_t i = 0; iend = i;
            int tmp = a[end + flag];
            while (end >= 0 && a[end] > tmp)//            ，   
            {
                a[end + flag] = a[end];
                end -= flag;
            }
            a[end + flag] = tmp;

        }
        /*printf("       ：");
        for (size_t i = 0; i < n; i++)
        {
            printf("%d ", a[i]);
        }
        printf("
");*///  
    }
}

> 3. 쌓 기 정렬
쌓 아 올 리 는 방법 으로 정렬 하 다.1) 작은 무 더 기 를 만 든 다음 에 위로 조정 하거나 아래로 조정 하 는 알고리즘 을 통 해 가장 작은 숫자 를 선택 한 다음 에 마지막 숫자 로 첫 번 째 숫자 를 덮어 쓰 고 아래로 조정 하 는 알고리즘 을 순서대로 작은 것 을 선택 하여 최종 적 으로 정렬 2) 큰 무 더 기 를 만 드 는 것 과 같다.시간 복잡 도 o (n * logn);공간 복잡 도 o (1);
더미 만 들 기: 오름차 순 - > 큰 더미, 내림차 순 - > 작은 더 미 는 다음 과 같은 절 차 를 수행 합 니 다. 배열 이 비어 있 을 때 까지 array [0] 요소 와 현재 가장 쌓 인 마지막 요소 교환 더미 요소 의 개 수 를 1 로 줄 입 니 다. 첫 번 째 단계 후 뿌리 노드 가 가장 쌓 인 정 의 를 만족 시 키 지 않 기 때문에 뿌리 노드 를 아래로 조정 하여 전체 이 진 트 리 를 더미 로 조정 합 니 다.그리고 매번 에 쌓 인 요 소 를 교환 한 후에 조정 하 는 시간 복잡 도 는 모두 O (logn) 이기 때문에 쌓 인 정렬 시간 복잡 도 는 O (n * logn) 쌓 인 정렬 이 불안정 한 정렬 알고리즘 입 니 다.

void Adjustdown(DataType*a, size_t n, int parent)//      
{
    assert(a);
    int  child = 2 * parent + 1;
    while (childif (a[child + 1] < a[child] && (child + 1) < n)//                  //        
        {
            ++child;//     
        }
        if (a[child]<a[parent])
        {
            Swap(&a[child], &a[parent]);

            parent = child;
            child = 2 * parent + 1;
        }
        else
        {
            break;
        }
    }
}
void HeapSort(DataType*a, size_t n)//  
{
    assert(a);
    for (int i = (n - 2) >> 1; i>=0 ;i--)
    {
        Adjustdown(a, n, i);
    }

    while (n>0)
    {
        printf("%d ", a[0]);
        a[0] = a[n-1];
        n--;
        Adjustdown(a, n, 0);

    }

}

4. 정렬 선택:
매번 (i 번, i = 0, 1,..., n - 2) 뒤에 n - i 정렬 할 데이터 요소 집합 에서 키 코드 가 가장 작은 데이터 요 소 를 선택 하여 질서 있 는 요소 서열 의 i 번 째 요소 로 합 니 다.n - 2 번 이 끝 날 때 까지 정렬 요소 집합 에 1 개의 요소 만 남 았 습 니 다. 정렬 이 끝 날 때 까지 요소 집합 array [i] – array [n - 1] 에서 키 코드 가 가장 큰 (작은) 데이터 요 소 를 선택 하 십시오. 이 요소 의 마지막 (첫 번 째) 요소 가 아니라면 이 요소 의 마지막 (첫 번 째) 요소 와 나머지 array [i] – array [n - 2] (array [+ 1]– array [n - 1] 집합 에서 상기 절 차 를 반복 하고 나머지 1 개 요 소 를 집합 하여 정렬 하 는 시간 복잡 도 를 O (n ^ 2) 로 직접 선택 할 때 까지 합 니 다.그것 은 불안정한 정렬 알고리즘 이다

void SelectSort(DataType*a, size_t n)
{
    int i = 0;
    int min = 0;
    int j = 0;
    for (i = 0; i < n - 1; i++)
    {
        min = i;//   min         
        for (j = i; j < n; j++)
        {
            if (a[min]>a[j])//      
                min = j;
        }
        if (min != i)
        {
            Swap(&a[min], &a[i]);
        }

    }

5. 거품 정렬:
거품 정렬 법 이란 한 그룹의 숫자 를 큰 것 에서 작은 것 으로 정렬 하거나 작은 것 에서 큰 것 으로 정렬 하 는 알고리즘 이다.구체 적 인 방법 은 인접 수치 두 개 를 교환 하 는 것 이다.첫 번 째 수치 부터 인접 한 두 수의 배열 순서 가 우리 의 기대 와 다 르 면 두 수의 위 치 를 교환 합 니 다 (대조).만약 그것 이 우리 의 기대 와 일치한다 면 교환 할 필요 가 없다.이러한 과정 을 반복 하면 마지막 에 수치 가 교환 되 지 않 을 때 까지 정렬 이 완 료 됩 니 다.일반적으로 N 개 수 를 정렬 해 야 할 경우 (N - 1) 번 거품 을 일 으 켜 야 한다.

void BubberSort(DataType*a, size_t n)
{
    int i = 0;
    int j = 0;
    for (i = 0; i < n-1; i++)
    {
        for ( j = 0; j< n-1-i; j++)
        {
            if (a[j+1]1], &a[j]);
}
}
}
}

테스트 코드:

#include"sort.h"
void InsertTest()
{
    int a[10] = { 2, 4, 5, 9, 3, 6, 8, 7, 1, 0 };
    InsertSort(a, sizeof(a) / sizeof(a[0]));
    SortPrint(a, sizeof(a) / sizeof(a[0]));
}
void XiErTest()
{
    int a[10] = { 9,8,7,6,5,4,3,2,1,0};
    XiErSort(a, sizeof(a) / sizeof(a[0]));
    SortPrint(a, sizeof(a) / sizeof(a[0]));

}
void HeapSorttest()
{
    int a[10] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
    HeapSort(a, sizeof(a) / sizeof(a[0]));

}
void SelectSortTest()
{
    int a[10] = { 1, 8, 7, 6,0,5, 4, 3, 2, 9};
    SelectSort(a, sizeof(a) / sizeof(a[0]));
    SortPrint(a, sizeof(a) / sizeof(a[0]));
}
void BubberSortTest()
{
    int a[10] = { 1, 8, 7, 6, 0, 5, 4, 3, 2, 9 };
    BubberSort(a, sizeof(a) / sizeof(a[0]));
    SortPrint(a, sizeof(a) / sizeof(a[0]));
}
int main()
{
    /*InsertTest();*/
    //XiErTest();
    //HeapSorttest();
    SelectSortTest();

    /*BubberSortTest();*/
    system("pause");
    return 0;
}