Acm入门7:排序算法(未完 春节后更新)

排序算法种类:

冒泡 选择 插入(希尔)

快速排序 分组排序 基数排序 桶排序 堆排序 归并排序 

#include 

void print(int* a, int len, bool isBefore = true);

int main() {
	int arr[10] = { 1,9,66,0,33,5,2,88,666,233 };

	print(arr, 10);
	print(arr, 10, false);
	while (1);
	return 0;
}

void print(int* a, int len, bool isBefore) {

	if (isBefore)
		printf("before sort:");
	else
		printf("after  sort:");

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

中间填充排序算法

思想(升序):

比较相邻的两个元素哪个比较大,若大的在后面,不管,若小的在后面交换

一轮过后,第len个数据就是最大的,

#include 


void print(int* a, int len, bool isBefore = true);
void bubble_sort(int* a, int len);

int main() {
	int arr[10] = { 1,9,66,0,33,5,2,88,666,233 };

	print(arr, 10);
	printf("bubble_sortn");
	bubble_sort(arr, 10);
	print(arr, 10, false);
	while (1);
	return 0;
}

//冒泡排序

void bubble_sort(int* a, int len)
{
	int temp;
	for (int i = 0; i < len; i++) {//外层循环
		for (int j = 0; j < len - i - 1; j++) {
			printf("i:%d,j:%d", i, j);
			if (a[j] > a[j + 1]) {
				temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
			}
		}
	}
}
void print(int* a, int len, bool isBefore) {

	if (isBefore)
		printf("before sort:");
	else
		printf("after  sort:");

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

一轮选一个最小的,下一轮继续选个最小的,9轮之后即可

#include 

void select_sort(int* a, int len);
void print(int* a, int len, bool isBefore = true);

int main() {
	int arr[10] = { 1,9,66,0,33,5,2,88,666,233 };

    void select_sort(arr, 10);
	print(arr, 10, false);
	while (1);
	return 0;
}

void select_sort(int* a, int len) {
	int temp;
	int minidx;
	for (int i = 0; i < len - 1; i++) {
		temp = a[i];
		minidx = i;
		for (int j = i; j < len; j++) {
			minidx = (a[j] < a[minidx]) ? j : minidx;
		}
		a[i] = a[minidx];
		a[minidx] = temp;
	}
}

void print(int* a, int len, bool isBefore) {

	if (isBefore)
		printf("before sort:");
	else
		printf("after  sort:");

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

先假设数组有序,每次往有序数组中插入一个

#include 
#include 

void print(int* a, int len, bool isBefore = true);
void insert_sort(int* a, int len);
int main() {
	int arr[10] = { 1,9,66,0,33,5,2,88,666,233 };
	printf("insert_sortn");
	insert_sort(arr, 10);
	print(arr, 10, false);
	while (1);
	return 0;
}
void insert_sort(int* a, int len) {
	int temp;
	int j;
	for (int i = 1; i < len; i++) {
		temp = a[i];
		j = i - 1;
		while (j >= 0 && a[j] > temp) {
			a[j + 1] = a[j];
			j--;
		}
		a[j + 1] = temp;
		print(a, 10);
	}

}

void print(int* a, int len, bool isBefore) {

	if (isBefore)
		printf("before sort:");
	else
		printf("after  sort:");

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

引入步长概念,每次按照步长分组,组内做插入排序

步长每次变化,通常折半

#include 

void print(int* a, int len, bool isBefore = true);
void shell_sort(int* a, int len);
int main() {
	int arr[10] = { 1,9,66,0,33,5,2,88,666,233 };

	shell_sort(arr, 10);
	print(arr, 10, false);
	while (1);
	return 0;
}
void shell_sort(int* a, int len) {
	int step = len / 2;
	int temp = 0;
	int j;
	while (step) {

		for (int i = temp; i < len; i++) {
			temp = a[i];
			j = i - step;
			while (j >= 0 && a[j] > temp) {
				a[j + 1] = a[j];
				j--;
			}
			a[j + step] = temp;
			print(a, 10);
		}
		step = step / 2;
	}

}
void print(int* a, int len, bool isBefore) {

	if (isBefore)
		printf("before sort:");
	else
		printf("after  sort:");

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