[C]常用排序算法

void bubble_sort(int arr[], int len) {
	for (int i = 0; i < len - 1; i++)
	{
		for (int j = 0; j < len - 1 - i; j++) {
			if (arr[j] > arr[j + 1]) {
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
}

void selection_sort(int arr[], int len) {
	for (int i = 0; i < len - 1; i++)
	{
		int min = i; // 记录最小变量的标志为i
		for (int j = i+1; j < len; j++)
		{
			if (arr[j] < arr[i]) {
				min = j;
			}
		}
		if (min != i) {
			// 如果确实有更小的值
			// 完成一次交换使当前位置顺序正确
			int temp = arr[i];
			arr[i] = arr[min];
			arr[min] = temp;
		}
	}
}

//void insertion_sort(int arr[], int len) {
//	for (int i = 1; i < len; i++)
//	{
//		int temp = arr[i];
//		int j;
//		for ( j = i; j > 0 && arr[j-1] > temp ; j--)
//		{
//			arr[j] = arr[j-1];
//		}
//		arr[j] = temp;
//	}
//}

void insertion_sort(int arr[], int len) {
	for (int i = 1; i < len; i++)
	{
		for (int j = i; j > 0 && arr[j - 1] > arr[j]; j--) {
			int temp = arr[j];
			arr[j] = arr[j - 1];
			arr[j - 1] = temp;
		}
	}
}

// 希尔排序---在插入排序的基础上
void shell_sort(int arr[], int len) {
	for (int gap = len >> 1; gap > 0; gap = gap >> 1)
	{
		for (int i = gap; i < len; i++) {
			int temp = arr[i];
			int j;
			for ( j = i - gap; j >= 0 && arr[j] > temp ; j = j -gap)
			{
				arr[j + gap] = arr[j];
			}
			if (j != i - gap) {
				arr[j + gap] = temp;
			}
		}
	}
}

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*2) {  // 每次的片段大小， 从1开始;
        for (start = 0; start < len; start = start + seg * 2) {  // 每次将两个相同大小的片段排好, 
            int low = start, mid = min(start + seg, len), high = min(start + seg * 2, 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;           // 实现将部分排列好的数组重新给a, b是用来摆放的容器
    }
    if (a != arr) {          // 如果a指向的是临时创建的容器, 说明只完成了奇数次装填, 这里要将正确结果返回给装载到arr也就是b中
                                // b = a可以没有,也就是让他指会原来空间, 直接让编译器释放掉a b就行
        int i;
        for (i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    free(b);
}

void merge_sort_recursive(int arr[], int reg[], int start, int end) {
	if (start >= end) return;
	int len = end - start; 
	int mid = (len >> 1) + start;
	int start1 = start;
	int end1 = mid;
	int start2 = mid + 1;
	int end2 = end;
	int k = start;
	merge_sort_recursive(arr, reg, start1, end1);
	merge_sort_recursive(arr, reg, start2, end2);
	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[],  int len) {
	int* reg = (int*)malloc(len * sizeof(int));  // malloc 申请的内存大小可以是变量, 可以用来代替创建数组, 因为C中数组长度必须是常量
	merge_sort_recursive(arr, reg, 0, len - 1);
}