c 语言排序算法

1. 插入排序
   每个循环都使当前子数组有序

#include
int main() {
	int num[10] = { 1,32,25,17,39,24,42,61,38,10 };
	for (int i = 1; i < sizeof num / sizeof num[0]; i++) {
		for (int j = i; j > 0;j--) {
			if (num[j] < num[j - 1]) {
				int temp = num[j];
				num[j] = num[j - 1];
				num[j - 1] = temp;
			}
			else {
				break;
			}
		}
		for (int i = 0; i < 10; i++) {
			printf("%d ", num[i]);
		}
		printf("n");
	}
	return 0;
}

2. 选择排序
   选择最小值使当前子数组有序

#include
int main() {
	int num[10] = { 51,32,25,17,39,24,42,61,38,10 };
	for (int i = 1; i < sizeof num / sizeof num[0]; i++) {
		int min = 1000000000 , pos;
		for (int j = i-1; j < sizeof num / sizeof num[0]; j++) {
			if (num[j] < min) {
				min = num[j];
				pos = j;
			}
		}
		int temp = num[i - 1];
		num[i - 1] = min;
		num[pos] = temp;
		for (int i = 0; i < 10; i++) {
			printf("%d ", num[i]);
		}
		printf("nn");
	}
	return 0;
}

3. 归并排序
不断分裂数组到最小单位，最后合并的同时排序

#include 
#include
void merge_sort(int* arr, int p, int q);
void merge(int* arr, int p, int mid, int q);

int main() {
    int arr[10] = { 7,5,2,4,1,6,3,0,9,6 };
    int p = 1, q = sizeof arr / sizeof arr[0];
    merge_sort(arr, p, q);
    for (int i = 0; i < 10; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

void merge_sort(int* arr, int p, int q) {
    if (p < q) {
        int mid = (p + q) / 2;
        printf("p mid q %d %d %dn", p, mid, q);
        merge_sort(arr, p, mid);
        merge_sort(arr, mid + 1, q);
        merge(arr, p, mid, q);
    }
}

void merge(int* arr, int p, int mid, int q) {
    for (int i = p; i <= mid; i++) {
        printf("%d ", arr[i - 1]);
    }
    printf("n");
    for (int i = mid+1; i <= q; i++) {
        printf("%d ", arr[i - 1]);
    }
    printf("n");
    int len_L = mid - p + 1, len_R = q - mid;
    int L[100], R[100];
    int m = 0, n = 0;
    for (int i = 0; i < len_L; i++) {
        L[i] = arr[p - 1 + i];
    }
    for (int i = 0; i < len_R; i++) {
        R[i] = arr[mid + i];
    }
    L[len_L] = INT_MAX;
    R[len_R] = INT_MAX;
    for (int i = p; i <= q; i++) {
        if (L[m] <= R[n]) {
            arr[i - 1] = L[m];
            m++;
        }
        else {
            arr[i - 1] = R[n];
            n++;
        }
    }
}