C 언어 - 데이터 구조 - 정렬 집합 (코드 직접 실행 가능)

거품 정렬
거품 정렬 (영어: Bubble Sort) 은 간단 한 정렬 알고리즘 이다.이 는 정렬 할 수열 을 반복 적 으로 방문 하여 한 번 에 두 요 소 를 비교 한 적 이 있다. 만약 그들의 순서 (예 를 들 어 크 고 작은 것, 이니셜 이 A 에서 Z 까지) 가 틀 리 면 그들 을 교환 할 것 이다.

#include 
void bubble_sort(int arr[], int len) {
    int i, j, temp;
    for (i = 0; i < len - 1; i++)
        for (j = 0; j < len - 1 - i; j++)
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
}
int main() {
    int arr[] = { 22, 34, 3, 32, 82};
    int len = (int) sizeof(arr) / sizeof(*arr);
    bubble_sort(arr, len);
    for (int i = 0; i < len; i++)
        printf("%d ", arr[i]);
    return 0;
}

2. 정렬 선택
정렬 선택 (Selection sort) 은 간단 하고 직관 적 인 정렬 알고리즘 입 니 다.그것 의 작업 원 리 는 다음 과 같다.먼저 정렬 되 지 않 은 시퀀스 에서 최소 (큰) 요 소 를 찾 아 정렬 시퀀스 의 시작 위치 에 저장 한 다음 에 나머지 정렬 되 지 않 은 요소 에서 최소 (큰) 요 소 를 계속 찾 은 다음 정렬 된 시퀀스 의 끝 에 놓 습 니 다.모든 요소 가 정렬 될 때 까지 유추 합 니 다.

#include 
void swap(int *a,int *b) //     
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
void selection_sort(int arr[], int len)
{
    int i,j;
    for (i = 0 ; i < len - 1 ; i++)
    {
        int min = i;
        for (j = i + 1; j < len; j++)     //        
            if (arr[j] < arr[min])    //       
                min = j;    //     
        swap(&arr[min], &arr[i]);    //   
    }
}
int main() {
    int arr[] = { 22, 34, 3, 32, 82};
    int len = (int) sizeof(arr) / sizeof(*arr);
    selection_sort(arr, len);
    for (int i = 0; i < len; i++)
        printf("%d ", arr[i]);
    return 0;
}

3. 정렬 삽입
정렬 삽입 (영어: Insertion Sort) 은 간단 하고 직관 적 인 정렬 알고리즘 이다.그것 의 작업 원 리 는 질서 있 는 서열 을 구축 하여 정렬 되 지 않 은 데이터 에 대해 정렬 된 서열 에서 뒤로 스 캔 하여 해당 하 는 위 치 를 찾 아 삽입 하 는 것 이다.

#include 
void insertion_sort(int arr[], int len){
    int i,j,temp;
    for (i=1;i<len;i++){
        temp = arr[i];
        for (j=i;j>0 && arr[j-1]>temp;j--)
            arr[j] = arr[j-1];
        arr[j] = temp;
    }
}
int main() {
    int arr[] = { 22, 34, 3, 32, 82};
    int len = (int) sizeof(arr) / sizeof(*arr);
    insertion_sort(arr, len);
    for (int i = 0; i < len; i++)
        printf("%d ", arr[i]);
    return 0;
}

사. 힐 정렬
힐 정렬 은 증분 정렬 알고리즘 이 라 고도 부 르 며 정렬 을 삽입 하 는 더욱 효율 적 인 개선 버 전 입 니 다.힐 정렬 은 불안정 정렬 알고리즘 입 니 다.힐 정렬 은 정렬 을 삽입 하 는 다음 과 같은 두 가지 성질 을 바탕 으로 개선 방법 을 제시한다.

정렬 을 삽입 하면 거의 정렬 된 데이터 작업 을 할 때 효율 이 높 고 선형 정렬 의 효율

에 도달 할 수 있다.

그러나 삽입 정렬 은 일반적으로 비효 율 적 입 니 다. 삽입 정렬 은 매번 한 자리 만 이동 할 수 있 기 때 문 입 니 다

#include 
void shell_sort(int arr[], int len) {
    int gap, i, j;
    int temp;
    for (gap = len >> 1; gap > 0; gap = gap >> 1)
        for (i = gap; i < len; i++) {
            temp = arr[i];
            for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                arr[j + gap] = arr[j];
            arr[j + gap] = temp;
        }
}
int main() {
    int arr[] = { 22, 34, 3, 32, 82};
    int len = (int) sizeof(arr) / sizeof(*arr);
    shell_sort(arr, len);
    for (int i = 0; i < len; i++)
        printf("%d ", arr[i]);
    return 0;
}

정렬
데 이 터 를 두 단락 으로 나 누 어 두 단락 에서 가장 작은 요 소 를 하나씩 선택 하여 새 데이터 세그먼트 의 끝 에 옮 깁 니 다.위 에서 아래로, 아래 에서 위로 진행 할 수 있 습 니 다.
반복 법:

#include 
#include 
int min(int x, int y) {
    return x < y ? x : y;
}
void merge_sort(int arr[], int len) {
    int* a = arr;
    int* b = (int*) malloc(len * sizeof(int));
    int seg, start;
    for (seg = 1; seg < len; seg += seg) {
        for (start = 0; start < len; start += seg + seg) {
            int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        int* temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        int i;
        for (i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    free(b);
}
int main() {
    int arr[] = { 22, 34, 3, 32, 82};
    int len = (int) sizeof(arr) / sizeof(*arr);
    merge_sort(arr, len);
    for (int i = 0; i < len; i++)
        printf("%d ", arr[i]);
    return 0;
}

귀속 법:

#include 
void merge_sort_recursive(int arr[], int reg[], int start, int end) {
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    merge_sort_recursive(arr, reg, start1, end1);
    merge_sort_recursive(arr, reg, start2, end2);
    int k = start;
    while (start1 <= end1 && start2 <= end2)
        reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        reg[k++] = arr[start1++];
    while (start2 <= end2)
        reg[k++] = arr[start2++];
    for (k = start; k <= end; k++)
        arr[k] = reg[k];
}
void merge_sort(int arr[], const int len) {
    int reg[len];
    merge_sort_recursive(arr, reg, 0, len - 1);
}
int main() {
    int arr[] = { 22, 34, 3, 32, 82};
    int len = (int) sizeof(arr) / sizeof(*arr);
    merge_sort(arr, len);
    for (int i = 0; i < len; i++)
        printf("%d ", arr[i]);
    return 0;
}

6. 빠 른 정렬
구간 에서 무 작위 로 원 소 를 선택 하여 기준 보다 작은 원 소 를 기준 에 두 고 기준 보다 큰 원 소 를 기준 에 둔 다음 에 각각 소수 구역 과 대수 구역 을 정렬 합 니 다.
반복 법:

#include 
typedef struct _Range {
    int start, end;
} Range;
Range new_Range(int s, int e) {
    Range r;
    r.start = s;
    r.end = e;
    return r;
}
void swap(int *x, int *y) {
    int t = *x;
    *x = *y;
    *y = t;
}
void quick_sort(int arr[], const int len) {
    if (len <= 0)
        return; //   len          （Segment Fault）
    // r[]    ,p   ,r[p++] push,r[--p] pop     
    Range r[len];
    int p = 0;
    r[p++] = new_Range(0, len - 1);
    while (p) {
        Range range = r[--p];
        if (range.start >= range.end)
            continue;
        int mid = arr[(range.start + range.end) / 2]; //          
        int left = range.start, right = range.end;
        do
        {
            while (arr[left] < mid) ++left;   //              
            while (arr[right] > mid) --right; //             

            if (left <= right)
            {
                swap(&arr[left],&arr[right]);
                left++;right--;               //        
            }
        } while (left <= right);

        if (range.start < right) r[p++] = new_Range(range.start, right);
        if (range.end > left) r[p++] = new_Range(left, range.end);
    }
}
int main() {
    int arr[] = { 22, 34, 3, 32, 82};
    int len = (int) sizeof(arr) / sizeof(*arr);
    quick_sort(arr, len);
    for (int i = 0; i < len; i++)
        printf("%d ", arr[i]);
    return 0;
}

귀속 법:

#include 
void swap(int *x, int *y) {
    int t = *x;
    *x = *y;
    *y = t;
}
void quick_sort_recursive(int arr[], int start, int end) {
    if (start >= end)
        return;
    int mid = arr[end];
    int left = start, right = end - 1;
    while (left < right) {
        while (arr[left] < mid && left < right)
            left++;
        while (arr[right] >= mid && left < right)
            right--;
        swap(&arr[left], &arr[right]);
    }
    if (arr[left] >= arr[end])
        swap(&arr[left], &arr[end]);
    else
        left++;
    if (left)
        quick_sort_recursive(arr, start, left - 1);
    quick_sort_recursive(arr, left + 1, end);
}
void quick_sort(int arr[], int len) {
    quick_sort_recursive(arr, 0, len - 1);
}
int main() {
    int arr[] = { 22, 34, 3, 32, 82};
    int len = (int) sizeof(arr) / sizeof(*arr);
    quick_sort(arr, len);
    for (int i = 0; i < len; i++)
        printf("%d ", arr[i]);
    return 0;
}