#include <stdio.h>
#include <stdlib.h>

void bubble_sort(int* src, int size) {
    int i = size;
    while (i > 0) { // 可以加个flag，如果后面排好了就不用继续冒泡
        int j = 0;
        while (j < i - 1) {
            if (src[j] > src[j + 1]) { // 加了=号就不是稳定排序了
                int tmp = src[j];
                src[j] = src[j + 1];
                src[j + 1] = tmp;
            }
            j++;
        }
        i--;
    }
}

void select_sort(int* src, int size) {
    int i = 0;
    while (i < size) {
        int j = i;
        while(j < size) {
            if (src[j] < src[i]) { // 加了=号就不是稳定排序了
                int tmp = src[i];
                src[i] = src[j];
                src[j] = tmp;
            }
            j++;
        }
        i++;
    }
}

void insert_sort(int* src, int size) {
    int sep = 0;
    while(sep < size) {
        int cur = sep + 1;
        while(cur > 0 && src[cur] < src[cur - 1]) { // 加了=号就不是稳定排序了
            int tmp = src[cur];
            src[cur] = src[cur - 1];
            src[cur - 1] = tmp;
            cur--;
        }
        sep++;
    }
}

void merge_sort(int* src, int size) {
    if (size == 1) {
        return;
    }
    int sep = size >> 1;
    merge_sort(src, sep);
    merge_sort(src + sep, size - sep);

    int *tmp_array = (int*)malloc(size*sizeof(int));
    int i = 0, j = sep, cur = 0;
    while(i < sep && j < size) {
        if (src[i] <= src[j])  // 去掉=号就不是稳定排序了
            tmp_array[cur++] = src[i++];
        else
            tmp_array[cur++] = src[j++];
    }
    while(i < sep) {
        tmp_array[cur++] = src[i++];
    }
    while(j < size) {
        tmp_array[cur++] = src[j++];
    }
    int k = 0;
    while (k < size) {
        src[k] = tmp_array[k];
        k++;
    }
    free(tmp_array); //临时数组放在参数里可以提高效率
}

void quick_sort(int* src 
ohne-rezeptkaufen.com
 , int size) {
    if (size <= 1) {
        return;
    }
    int slot = src[0];
    int i = 0, j = size - 1;
    while (i < j) {
        while (i < j && src[j] > slot) j--;
        if (i < j) {
            src[i] = src[j];
            i++;
        }
        while (i < j && src[i] < slot) i++;
        if (i < j) {
            src[j] = src[i];
            j--;
        }
    }
    src[i] = slot;
    quick_sort(src, i);
    quick_sort(src + j + 1, size - j - 1);
}

void print_result(int* src, int size) {
    int i = 0;
    printf("{");
    do {
        printf("%d, ", src[i]);
    } while(++i < size);
    printf("}");
}

int main()
{
    int target[] = {2,3,5,1,6,4,8,4,9,0,0,2,3,-2,0,-3,-2};
    int target_size = sizeof(target)/sizeof(int);
    printf("target size:%d\n", target_size);

    merge_sort(target, target_size);
    printf("sort:");
    print_result(target, target_size);

    return 0;
}