【十大经典排序算法】C语言实现

插入类排序

直接插入排序

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

折半(二分)插入排序

void binary_insert_sort(int arr[], int len) {
	int record;
	
	for(int i = 1; i < len; i++) {
		record = arr[i];
		int low = 0, high = i - 1, mid;
		while(low <= high) {
			mid = (low + high) / 2;
			if(record < arr[mid])
				high = mid - 1;
			else
				low = mid + 1;
		}
		for(int j = i - 1; j >= low; j--)
			arr[j + 1] = arr[j];
		arr[low] = record;
	}
}

希尔排序

void shell_sort(int arr[], int len) {
	
	for(int delta = len / 2; delta > 0; delta /= 2)
		for(int i = delta; i < len; i++) {
			int record = arr[i], j;
			for(j = i - delta; j >= 0 && arr[j] > record; j -= delta)
				arr[j + delta] = arr[j];
			arr[j + delta] = record;
		}
}

交换类排序

冒泡排序

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

快速排序

void quick_sort(int arr[], int begin, int end) {
	if(begin == end)
		return;
	
	int key = arr[begin], i = begin, j = end;
	while(i < j) {
		while(i < j && arr[i] <= key)
			i++;
		while(i < j && arr[j] >= key)
			j--;
		if(i != j) {
			int temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
	}
	i = (i == j) ? (i - 1) : i;
	int temp = arr[begin];
	arr[begin] = arr[i];
	arr[i] = temp;
	
	quick_sort(arr, begin, i);
	quick_sort(arr, i + 1, end);
}

选择类排序

选择排序

void selection_sort(int arr[], int len) {
	int i, j, t;
	
	for(i = 0; i < len - 1; i++) {
		int k = i;
		for(j = i + 1; j < len; j++)
			if(arr[k] > arr[j])
				k = j;
		if(k != i) {
			t = arr[i];
			arr[i] = arr[k];
			arr[k] = t;
		}
	}
}

树形选择排序

void tree_selection_sort(int arr[], int len) {
	int treeLen = len * 2 - 1, difference = treeLen - len;
	int tree[treeLen], key[treeLen];
	
	for(int i = 0; i < len; i++) {
		tree[i + difference] = arr[i];
		key[i + difference] = i;
	}
	
	for(int i = 0; i < len; i++) {
		for(int j = difference - 1; j >= 0; j--) {
			tree[j] = (tree[j * 2 + 1] < tree[j * 2 + 2]) ? tree[j * 2 + 1] : tree[j * 2 + 2];
			key[j] = (tree[j * 2 + 1] < tree[j * 2 + 2]) ? key[j * 2 + 1] : key[j * 2 + 2];
		}
		tree[key[0] + difference] = INT_MAX;
		if(key[0] != i) {
			int temp = arr[i];
			arr[i] = arr[key[0]];
			arr[key[0]] = temp;
			temp = tree[key[0] + difference];
			tree[key[0] + difference] = tree[i + difference];
			tree[i + difference] = temp;
		}
	}
}

堆排序

void heap_sort(int arr[], int len) {
	
	for(int remain = len - 1; remain > 0; remain--) {
		for(int i = (remain - 1) / 2; i >= 0; i--) {
			int maxKey;
			if(i * 2 + 2 >= len)
				maxKey = i * 2 + 1;
			else
				maxKey = (arr[i * 2 + 1] > arr[i * 2 + 2]) ? (i * 2 + 1) : (i * 2 + 2); 
			if(arr[i] < arr[maxKey]) {
				int temp = arr[i];
				arr[i] = arr[maxKey];
				arr[maxKey] = temp;
			}
		}
		int temp = arr[0];
		arr[0] = arr[remain];
		arr[remain] = temp;
	}
}

归并排序

void merge_sort(int arr[], int low, int high) {
	
	if(low < high) {
		int mid = (low + high) / 2;
		
		merge_sort(arr, low, mid);
		merge_sort(arr, mid + 1, high);
		merge(arr, low, high, mid);
	}
}

void merge(int arr[], int low, int high, int mid) {
	int p = low, q = mid + 1;
	int t[high - low + 1];
	
	int i;
	for(i = 0; i < high - low + 1 && p <= mid && q <= high; i++)
		if(arr[p] < arr[q])
			t[i] = arr[p++];
		else
			t[i] = arr[q++];
	
	if(p > mid)
		while(q <= high) t[i++] = arr[q++];
	if(q > high)
		while(p <= mid) t[i++] = arr[p++];
	
	for(i = low; i <= high; i++)
		arr[i] = t[i - low];
}

计数排序

分配类排序

捅排序

基数排序