데이터 구조 정렬 에 대한 자신의 정리 와 학습

4232 단어
 //               Coding
//                             
#include <cstdio>
#include <cstdlib>
//#define _OJ_

void
Bubble_sort(int a[], int n)
{
    int i, j, t, change;
    for (i = 0, change = 1; i < n && change; i++) {
        change = 0;
        for (j = 0; j < n - 1 - i; j++) {
            if(a[j] > a[j + 1])
            {t = a[j];  a[j] = a[j + 1];  a[j + 1] = t;   change = 1;}
        }
    }
    printf("i == %d
", i); } void Select_sort(int a[], int n) { int i, j, t, min; for (i = 0; i < n; i++) { min = i; for (j = i + 1; j < n; j++) if(a[j] < a[min]) min = j; if(min != i) {t = a[i]; a[i] = a[min]; a[min] = t;} } printf("i1 == %d
", i); } void Insert_sort(int a[], int n) // { int i, j, t; for (i = 1; i < n; i++) { for (j = i; j > 0 && a[j] < a[j - 1]; j--) { t = a[j - 1]; a[j - 1] = a[j]; a[j] = t; } } } void Shell_sort(int a[], int n) // { int i, j, t, gap; for (gap = n / 2; gap > 0; gap /= 2) { for (i = gap; i < n; i += gap) { for (j = i; j - gap >= 0 && a[j] < a[j - gap]; j -= gap) { t = a[j - gap]; a[j - gap] = a[j]; a[j] = t; } } } } void Quick_sort(int a[], int left, int right) // { int i, j, x; i = left; j = right; x = a[left]; if(i < j) { while (i < j) { while (i < j && x < a[j]) j--; if(i < j) a[i++] = a[j]; while (i < j && x > a[i]) i++; if(i < j) a[j--] = a[i]; } a[i] = x; Quick_sort(a, left, i - 1); Quick_sort(a, i + 1, right); } } void merge_array(int a[], int low, int mid, int high, int tmp[]) {// divid and conquer int i, j, n, m, k; i = low; j = mid + 1; n = mid; m = high; k = 0; while (i <= n && j <= high) { if(a[i] <= a[j]) tmp[k++] = a[i++]; else tmp[k++] = a[j++]; } while (i <= n) tmp[k++] = a[i++]; while (j <= m) tmp[k++] = a[j++]; for (i = 0; i < k; i++) a[low + i] = tmp[i]; } void merge_sort(int a[], int low, int high, int tmp[]) { if(low < high) { int mid = (low + high) / 2; merge_sort(a, low, mid, tmp); merge_sort(a, mid + 1, high, tmp); merge_array(a, low, mid, high, tmp); } } void Merge_sort(int a[], int n) { int *tmp; tmp = (int*) malloc (100 * sizeof(int)); merge_sort(a, 0, n - 1, tmp); free(tmp); } int main(int argc, char const *argv[]) { #ifndef _OJ_ //ONLINE JUDGE freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); #endif int i, n; int a[100]; scanf("%d", &n); for (i = 0; i < n; i++) a[i] = n - i - 1; // scanf("%d", &a[i]); // Bubble_sort(a, n); // Select_sort(a, n); // Insert_sort(a, n); // Shell_sort(a, n); // Quick_sort(a, 0, n - 1); // Merge_sort(a, n); for (i = 0; i < n; i++) printf("%d ", a[i]); return 0; }

좋은 웹페이지 즐겨찾기