/*
 * CreateTime: 2014-09-15 20:10:48
 *  因为冒泡是相邻交换, sign 标记着这次不用交换, 下次也不用交换.
 */
#include <cstdio>

#define N 10

int main(void) {
    int sign = 1;
    int a[10] = { 1, 454, 634,34, 3, 3, 2343, 23435, 34, 42 };

    /* 第一轮排序后, 最大的已经在 a[9] 上 */
    for(int i = 0; i < N-1 && sign; ++i) {
        sign = 0;
        for(int j = 0; j < N-1-i; ++j) {
            if(a[j] > a[j+1]) {
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
                sign = 1;
            }
        }
    }
    for(int i = 0; i < 10; ++i) {
        printf("%d ", a[i]);
    }
    printf("\n");

    return 0;
}

/*
 * CreateTime: 2014-09-15 20:15:44
 */
#include <cstdio>

int main(void) {
    int a[10] = {1, 454, 634,34, 3, 3, 2343, 23435, 34, 42};

    for(int i = 0; i < 10-1; ++i) {
        int k = i;
        for(int j = i+1; j < 10; ++j) {
            if(a[j] < a[k]) {   // 选择出最小的
                k = j;
            }
        }
        if(k != i) {
            int temp = a[k];
            a[k] = a[i];
            a[i] = temp;
        }
    }

    for(int i = 0; i < 10; ++i) {
        printf("%d ", a[i]);
    }
    printf("\n");

    return 0;
}

/*
 * CreateTime: 2014-09-15 20:11:59
 */
#include <cstdio>

int main(void) {
    int a[10] = { 1, 454, 634, 34, 4, 3, 2343, 23435, 84, 42 };
    for(int i = 1; i < 10; i++) {
        int key = a[i];
        int j = i - 1;
        while(j >= 0 && a[j] > key) {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = key;
    }
    //  | | | | | | | | | |  相当于有十张牌, 一直往前面插
    for(int i = 0; i < 10; ++i) {
        printf("%d ", a[i]);
    }
    printf("\n");

    return 0;
}

/*
 * Created Time: 2014-05-24 18:53:01
 */
#include <cstdio>

void shellsort(void);
int a[10] = { 1, 454, 634,34, 3, 3, 2343, 23435, 34, 42 };

int main(void) {
    shellsort();
    for(int i = 0; i < 10; ++i) {
        printf("%d ", a[i]);
    }
    printf("\n");

    return 0;
}

void shellsort(void) {
    for(int k = N / 2; k > 0; k = k / 2) {
        for(int i = k; i < N; i++) {
            for(int j = i; j > k && a[i] < a[j-k]; j = j - k) {
                int tmp = a[j];
                a[j] = a[j-k];
                a[j-k] = tmp;
            }
        }
    }
}

/*
 * CreateTime: 2014-09-14 09:49:11
 */

#include <cstdio>

void msort(int start, int end);
void merge(int start1, int end1, int end2);
int a[10] = {1, 34, 45, 3, 54, 384, 454, 4387, 4546, 10};
int temp[10];

int main(void) {
    msort(0, 9);
    for(int i = 0; i < 10; ++i) {
        printf("%d ", a[i]);
    }
    printf("\n");

    return 0;
}

void msort(int start, int end) {
    if(start < end) {
        int centre = (start + end) / 2;
        msort(start, centre);
        msort(centre+1, end);
        merge(start, centre, end);
    }
}

void merge(int start1, int end1, int end2) {
    int start2 = end1 + 1;
    int length = start1;
    int num = end2 - start1 + 1;

    while(end1 >= start1 && end2 >= start2) {
        if(a[start1] <= a[start2]) {
            temp[length++] = a[start1++];
        } else {
            temp[length++] = a[start2++];
        }
    }

    /* 剩下的一组 */
    while(start1 <= end1) {
        temp[length++] = a[start1++];
    }
    while(start2 <= end2) {
        temp[length++] = a[start2++];
    }
    /* 剩下的一组 */

    for(int i = 0; i < num; i++, end2--) {
        a[end2] = temp[end2];
    }
}

/*
 * CreateTime: 2014-09-14 09:49:11
 */

#include <cstdio>

void msort(int l, int r);
void merge(int l, int mid, int r);
int a[10] = {1, 34, 45, 3, 54, 384, 454, 4387, 4546, 10};
int temp[10];

int main(void) {
    msort(0, 9);
    for(int i = 0; i < 10; ++i) {
        printf("%d ", a[i]);
    }
    printf("\n");

    return 0;
}

void msort(int l, int r) {
    if(l < r) {
        int mid = (l + r) / 2;
        msort(r, mid);
        msort(mid+1, r);
        merge(l, mid, r);
    }
}

void merge(int l, int mid, int r) {
    int i = l;
    int j = mid + 1;
    for(int t = l; t <= r; t++) {
        temp[t] = a[t];
    }
    for(int t = l; t <= r; t++) {
        if(i > mid) {       // l is full
            a[t] = temp[j++];
        } else if(j > r) {  // r is full
            a[t] = temp[i++];
        } else if(temp[i] < temp[j]) {
            a[t] = temp[i++];
        } else if(temp[i] >= temp[j]){
            a[t] = temp[j++];
        }
    }
}

/*
 * CreateTime: 2014-10-27 19:02:02
 */
#include <cstdio>
#include <cassert>

int arr[100] = { 10, 16, 4, 10, 14, 7, 9, 3, 2, 8, 1 };
// a[0] 表示堆大小

int left(int i);
int right(int i);
void max_heapify(int i);
void build_max_heap(void);
void insert_element(int value);
void heap_sort(void);
void print() {
    for(int i = 1; i <= arr[0]; i++) {
        printf("%4d", arr[i]);
    }
    printf("\n");

}

int main(void) {
    build_max_heap();
    print();
    insert_element(100);
    print();

    heap_sort();

    return 0;
}

int left(int i) {
    return (i*2);
}

int right(int i) {
    return (i*2 + 1);
}

void max_heapify(int i) {
    int largest;
    int l = left(i);
    int r = right(i);

    if(l <= arr[0] && arr[l] > arr[i]) {
        largest = l;
    } else {
        largest = i;
    }
    if(r <= arr[0] && arr[r] > arr[largest]) {
        largest = r;
    }
    if(largest != i) {
        int tmp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = tmp;
        max_heapify(largest);
    }
}

void build_max_heap(void) {
    for(int i = arr[0]/2; i > 1; i--) {
        max_heapify(i);
    }
}

void insert_element(int value) {
    arr[0]++;
    int t = arr[0];
    arr[t] = value;
    while(t > 1 && arr[t] > arr[t/2]) {
        // 重置, 因为最后一个可能大于父节点
        int tmp = arr[t];
        arr[t] = arr[t/2];
        arr[t/2] = tmp;
        t = t/2;
    }
}

void heap_sort(void) {
    build_max_heap();                     // 建堆
    for(int i = arr[0]; i >= 1; i--) {
        int last_element = arr[0];
        // 通过交换第一个(最大值) 和最后一个然后重建堆來完成
        int tmp = arr[last_element];
        arr[last_element] = arr[1];
        arr[1] = tmp;
        arr[0]--;                         // 删除最后一个
        printf("%4d", arr[last_element]);
        // 依次输出被删除的(也就是每次的最大來达到排序)
        max_heapify(1);                   // 重建
    }
    printf("\n");
}

/*
 * CreateTime: 2014-11-01 22:57:54
 */

#include <cstdio>
#include <cstdlib>
#include <cstring>

int a[10];

void print(void);
void swap(int &x, int &y);
void qsort(int l, int r);
int partition(int l, int r);

int main(void) {
    qsort(0, 9);
    print();

    return 0;
}

void print(void) {
    for(int i = 0; i < 10; i++) {
        printf("%3d", a[i]);
    }
    printf("\n");
}

void qsort(int l, int r) {
    if(l < r) {
        int q = partition(l, r);
        qsort(l, q-1);
        qsort(q+1, r);
    }
}

int partition(int l, int r) {
    int q = l - 1;
    int x = a[r];
    for(int i = l; i < r; i++) {
        if(a[i] < x) {
            q++;
            swap(a[i], a[q]);
        }
    }
    swap(a[q+1], a[r]);

    return q+1;
}