排序选择算法

前言

教材来自麻省理工版本的算法导论，B站亦有相应的高清视频可供观看

学习的目的一则是复现上课所讲的代码，二则是训练自己的编程水平（

排序算法

插入排序

void Insertion_Sort(int* a, int num)
{
	int t;
	for (int i = 1; i < num; i++)
	{
		t = a[i];
		int j = i - 1;
		while (j >= 0 && a[j] > t)
		{
			a[j + 1] = a[j];
			j--;
		}
		a[j + 1] = t;
	}
}

归并排序

void Merge(int* a, int p, int q, int r)
{
	int n1 = q - p + 1;
	int n2 = r - q;
	int* L, * R;
	L = (int*)malloc(sizeof(int) * n1);
	R = (int*)malloc(sizeof(int) * n2);
	for (int i = 0; i < n1; i++)
	{
		L[i] = a[p + i];
	}
	for (int i = 0; i < n2; i++)
	{
		R[i] = a[q + i + 1];
	}
	int i = 0;
	int j = 0;
	for (int k = p; k <= r; k++)
	{
		if ((L[i] <= R[j] && i < n1) || (j == n2))
		{
			a[k] = L[i];
			i++;
		}
		else
		{
			a[k] = R[j];
			j++;
		}
	}

	free(L);
	free(R);
}

void Merge_sort(int* a, int p, int r)
{
	if (p < r)
	{
		int q = (p + r) / 2;
		Merge_sort(a, p, q);
		Merge_sort(a, q + 1, r);
		Merge(a, p, q, r);
	}
}

堆排序

void Max_Heapify(int* a, int heap_size, int i)
{
	int l_child = 2 * i + 1;
	int r_child = 2 * i + 2;
	int largest_child;
	if (l_child <= heap_size - 1 && a[l_child] > a[i])
	{
		largest_child = l_child;
	}
	else
	{
		largest_child = i;
	}
	if (r_child <= heap_size - 1 && a[r_child] > a[largest_child])
	{
		largest_child = r_child;
	}

	if (largest_child != i)
	{
		//交换i与largest_child
		Swap_Array_ij(a, heap_size, i, largest_child);

		Max_Heapify(a, heap_size, largest_child);
	}
}

void Heap_Sort(int* a, int num)
{
	int heap_size = num;
	//建立堆
	for (int i = num / 2 - 1; i >= 0; i--)
	{
		Max_Heapify(a, num, i);
	}
	for (int i = num - 1; i > 0; i--)
	{
		//交换i与0
		Swap_Array_ij(a, num, i, 0);

		heap_size--;
		Max_Heapify(a, heap_size, 0);
	}
}

快速排序

int Random_Partition(int* a, int p, int r)
{
	//随机主元
	int random_num = rand() % (r - p + 1) + p;
	int x = a[random_num];
	Swap_Array_ij(a, r - p + 1, random_num, r);

	int i = p - 1;
	for (int j = p; j < r; j++)
	{
		if (a[j] <= x)
		{
			i++;
			//交换i与j
			Swap_Array_ij(a, r - p + 1, i, j);
		}
	}
	//交换i+1与r
	Swap_Array_ij(a, r - p + 1, i + 1, r);

	return i + 1;
}

void Random_Quick_Sort(int* a, int p, int r)
{
	if (p < r)
	{
		int q;
		q = Random_Partition(a, p, r);
		Random_Quick_Sort(a, p, q - 1);
		Random_Quick_Sort(a, q + 1, r);
	}
}

计数排序

void Counting_Sort(int* a, int num, int maxnum)
{
	int* b, * c;
	b = (int*)malloc(sizeof(int) * num);
	c = (int*)malloc(sizeof(int) * (maxnum + 1));
	for (int i = 0; i <= maxnum; i++)
	{
		c[i] = 0;
	}
	for (int i = 0; i < num; i++)
	{
		c[a[i]]++;
	}
	for (int i = 1; i <= maxnum; i++)
	{
		c[i] = c[i] + c[i - 1];
	}
	for (int i = 0; i < num; i++)
	{
		c[a[i]] --;
		b[c[a[i]]] = a[i];
	}

	for (int i = 0; i < num; i++)
	{
		a[i] = b[i];
	}
	free(b);
	free(c);
}

基数排序

void Sort_Digit(int* a, int num, int* c, int system, int digit, int sort_digit)
{
	//调用基数排序
	int* counting_sort_c;
	counting_sort_c = (int*)malloc(sizeof(int) * system);
	int* counting_sort_b1, * counting_sort_b2;
	counting_sort_b1 = (int*)malloc(sizeof(int) * num);
	counting_sort_b2 = (int*)malloc(sizeof(int) * num * digit);

	for (int i = 0; i < system; i++)
	{
		counting_sort_c[i] = 0;
	}

	for (int i = 0; i < num; i++)
	{
		counting_sort_c[c[i * digit + sort_digit]] ++;
	}

	for (int i = 1; i < system; i++)
	{
		counting_sort_c[i] = counting_sort_c[i] + counting_sort_c[i - 1];
	}

	for (int i = num - 1; i >= 0; i--)
	{
		counting_sort_c[c[i * digit + sort_digit]] --;
		counting_sort_b1[counting_sort_c[c[i * digit + sort_digit]]] = a[i];
		for (int j = 0; j < digit; j++)
		{
			counting_sort_b2[counting_sort_c[c[i * digit + sort_digit]] * digit + j] = c[i * digit + j];
		}
	}

	for (int i = 0; i < num; i++)
	{
		a[i] = counting_sort_b1[i];
		for (int j = 0; j < digit; j++)
		{
			c[i * digit + j] = counting_sort_b2[i * digit + j];
		}
	}

	free(counting_sort_c);
	free(counting_sort_b1);
	free(counting_sort_b2);

}

void Radix_Sort(int* a, int num, int maxnum, int system)
{
	//确定位数
	int digit = 1;
	while (pow(system, digit) < maxnum)
	{
		digit++;
	}

	//储存整数的各个位数值
	//第一列表示排序序号，第二位表示个位数字，...，第digit + 1位表示digit位数字
	int* c;
	c = (int*)malloc(sizeof(int) * num * digit);

	int place;
	for (int i = 0; i < num; i++)
	{
		c[i * digit] = i;
		for (int j = 0; j < digit; j++)
		{
			place = a[i] / pow(system, j);
			c[i * digit + j] = place % system;
		}
	}

	for (int j = 0; j < digit; j++)
	{
		Sort_Digit(a, num, c, system, digit, j);
	}

	free(c);
}

选择算法

int Randomized_Select(int* a, int p, int r, int i)
{
	if (p == r)
	{
		return a[p];
	}
	else
	{
		int q;
		q = Random_Partition(a, p, r);
		int k = q - p + 1;

		if (i == k)
		{
			return a[q];
		}
		else if (i < k)
		{
			return Randomized_Select(a, p, q - 1, i);
		}
		else
		{
			return Randomized_Select(a, q + 1, r, i - k);
		}
	}
}

总代码

#include <stdio.h>
#include <stdlib.h>
#include "time.h"
#include <math.h>

//随机生成数组
int* Random_Array(int num, int maxnum)
{
	int* a;
	a = (int*)malloc(sizeof(int) * num);
	for (int i = 0; i < num; i++)
	{
		a[i] = rand() % maxnum;
	}
	return a;
}

//复制数组
int* Copy_Array(int* a, int num)
{
	int* b;
	b = (int*)malloc(sizeof(int) * num);
	for (int i = 0; i < num; i++)
	{
		b[i] = a[i];
	}
	return b;
}

//交换数组i与j
void Swap_Array_ij(int* a, int num, int i, int j)
{
	int t;
	t = a[i];
	a[i] = a[j];
	a[j] = t;
}

//判断是否从小到大排序好
int Order_Array(int* a, int num)
{
	int flag = 1;
	for (int i = 0; i < num - 1; i++)
	{
		if (a[i] > a[i + 1])
		{
			flag = 0;
			break;
		}
	}
	return flag;
}

//输出数组
void Print_Array(int* a, int num)
{
	for (int i = 0; i < num; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

//插入排序
void Insertion_Sort(int* a, int num)
{
	int t;
	for (int i = 1; i < num; i++)
	{
		t = a[i];
		int j = i - 1;
		while (j >= 0 && a[j] > t)
		{
			a[j + 1] = a[j];
			j--;
		}
		a[j + 1] = t;
	}
}

//归并排序
void Merge(int* a, int p, int q, int r)
{
	int n1 = q - p + 1;
	int n2 = r - q;
	int* L, * R;
	L = (int*)malloc(sizeof(int) * n1);
	R = (int*)malloc(sizeof(int) * n2);
	for (int i = 0; i < n1; i++)
	{
		L[i] = a[p + i];
	}
	for (int i = 0; i < n2; i++)
	{
		R[i] = a[q + i + 1];
	}
	int i = 0;
	int j = 0;
	for (int k = p; k <= r; k++)
	{
		if ((L[i] <= R[j] && i < n1) || (j == n2))
		{
			a[k] = L[i];
			i++;
		}
		else
		{
			a[k] = R[j];
			j++;
		}
	}

	free(L);
	free(R);
}

void Merge_sort(int* a, int p, int r)
{
	if (p < r)
	{
		int q = (p + r) / 2;
		Merge_sort(a, p, q);
		Merge_sort(a, q + 1, r);
		Merge(a, p, q, r);
	}
}

//堆排序
void Max_Heapify(int* a, int heap_size, int i)
{
	int l_child = 2 * i + 1;
	int r_child = 2 * i + 2;
	int largest_child;
	if (l_child <= heap_size - 1 && a[l_child] > a[i])
	{
		largest_child = l_child;
	}
	else
	{
		largest_child = i;
	}
	if (r_child <= heap_size - 1 && a[r_child] > a[largest_child])
	{
		largest_child = r_child;
	}

	if (largest_child != i)
	{
		//交换i与largest_child
		Swap_Array_ij(a, heap_size, i, largest_child);

		Max_Heapify(a, heap_size, largest_child);
	}
}

void Heap_Sort(int* a, int num)
{
	int heap_size = num;
	//建立堆
	for (int i = num / 2 - 1; i >= 0; i--)
	{
		Max_Heapify(a, num, i);
	}
	for (int i = num - 1; i > 0; i--)
	{
		//交换i与0
		Swap_Array_ij(a, num, i, 0);

		heap_size--;
		Max_Heapify(a, heap_size, 0);
	}
}

//(随机)快速排序
int Random_Partition(int* a, int p, int r)
{
	//随机主元
	int random_num = rand() % (r - p + 1) + p;
	int x = a[random_num];
	Swap_Array_ij(a, r - p + 1, random_num, r);

	int i = p - 1;
	for (int j = p; j < r; j++)
	{
		if (a[j] <= x)
		{
			i++;
			//交换i与j
			Swap_Array_ij(a, r - p + 1, i, j);
		}
	}
	//交换i+1与r
	Swap_Array_ij(a, r - p + 1, i + 1, r);

	return i + 1;
}

void Random_Quick_Sort(int* a, int p, int r)
{
	if (p < r)
	{
		int q;
		q = Random_Partition(a, p, r);
		Random_Quick_Sort(a, p, q - 1);
		Random_Quick_Sort(a, q + 1, r);
	}
}

//计数排序
void Counting_Sort(int* a, int num, int maxnum)
{
	int* b, * c;
	b = (int*)malloc(sizeof(int) * num);
	c = (int*)malloc(sizeof(int) * (maxnum + 1));
	for (int i = 0; i <= maxnum; i++)
	{
		c[i] = 0;
	}
	for (int i = 0; i < num; i++)
	{
		c[a[i]]++;
	}
	for (int i = 1; i <= maxnum; i++)
	{
		c[i] = c[i] + c[i - 1];
	}
	for (int i = 0; i < num; i++)
	{
		c[a[i]] --;
		b[c[a[i]]] = a[i];
	}

	for (int i = 0; i < num; i++)
	{
		a[i] = b[i];
	}
	free(b);
	free(c);
}

//基数排序
void Sort_Digit(int* a, int num, int* c, int system, int digit, int sort_digit)
{
	//调用基数排序
	int* counting_sort_c;
	counting_sort_c = (int*)malloc(sizeof(int) * system);
	int* counting_sort_b1, * counting_sort_b2;
	counting_sort_b1 = (int*)malloc(sizeof(int) * num);
	counting_sort_b2 = (int*)malloc(sizeof(int) * num * digit);

	for (int i = 0; i < system; i++)
	{
		counting_sort_c[i] = 0;
	}

	for (int i = 0; i < num; i++)
	{
		counting_sort_c[c[i * digit + sort_digit]] ++;
	}

	for (int i = 1; i < system; i++)
	{
		counting_sort_c[i] = counting_sort_c[i] + counting_sort_c[i - 1];
	}

	for (int i = num - 1; i >= 0; i--)
	{
		counting_sort_c[c[i * digit + sort_digit]] --;
		counting_sort_b1[counting_sort_c[c[i * digit + sort_digit]]] = a[i];
		for (int j = 0; j < digit; j++)
		{
			counting_sort_b2[counting_sort_c[c[i * digit + sort_digit]] * digit + j] = c[i * digit + j];
		}
	}

	for (int i = 0; i < num; i++)
	{
		a[i] = counting_sort_b1[i];
		for (int j = 0; j < digit; j++)
		{
			c[i * digit + j] = counting_sort_b2[i * digit + j];
		}
	}

	free(counting_sort_c);
	free(counting_sort_b1);
	free(counting_sort_b2);

}

void Radix_Sort(int* a, int num, int maxnum, int system)
{
	//确定位数
	int digit = 1;
	while (pow(system, digit) < maxnum)
	{
		digit++;
	}

	//储存整数的各个位数值
	//第一列表示排序序号，第二位表示个位数字，...，第digit + 1位表示digit位数字
	int* c;
	c = (int*)malloc(sizeof(int) * num * digit);

	int place;
	for (int i = 0; i < num; i++)
	{
		c[i * digit] = i;
		for (int j = 0; j < digit; j++)
		{
			place = a[i] / pow(system, j);
			c[i * digit + j] = place % system;
		}
	}

	for (int j = 0; j < digit; j++)
	{
		Sort_Digit(a, num, c, system, digit, j);
	}

	free(c);
}

//随机选择算法
int Randomized_Select(int* a, int p, int r, int i)
{
	if (p == r)
	{
		return a[p];
	}
	else
	{
		int q;
		q = Random_Partition(a, p, r);
		int k = q - p + 1;

		if (i == k)
		{
			return a[q];
		}
		else if (i < k)
		{
			return Randomized_Select(a, p, q - 1, i);
		}
		else
		{
			return Randomized_Select(a, q + 1, r, i - k);
		}
	}
}

int main()
{
	int num = 100000;		//数组大小
	int maxnum = 100000000;	//范围0-maxnum
	printf("数组大小为%d\n数组值的范围为 0 -- %d\n", num, maxnum);
	int oeder_statistic = num / 2;

	clock_t start, finish;
	double  duration;

	//生成随机数组
	int* a;
	a = Random_Array(num, maxnum);
	int* b;
	b = Copy_Array(a, num);
	int* c;
	c = Copy_Array(a, num);
	int* d;
	d = Copy_Array(a, num);
	int* e;
	e = Copy_Array(a, num);
	int* f;
	f = Copy_Array(a, num);
	int* g;
	g = Copy_Array(a, num);

	//插入排序
	printf("---------------------\n");
	printf("插入排序：\n");
	start = clock();
	Insertion_Sort(a, num);
	finish = clock();
	if (Order_Array(a, num))
	{
		printf("数组已从小到大排序\n");
	}
	duration = (double)(finish - start) / CLOCKS_PER_SEC;
	printf("插入排序消耗的时间:  %f s\n", duration);

	//归并排序
	printf("\n---------------------\n");
	printf("归并排序：\n");
	start = clock();
	Merge_sort(b, 0, num - 1);
	finish = clock();
	if (Order_Array(b, num))
	{
		printf("数组已从小到大排序\n");
	}
	duration = (double)(finish - start) / CLOCKS_PER_SEC;
	printf("归并排序消耗的时间:  %f s\n", duration);

	//堆排序
	printf("\n---------------------\n");
	printf("堆排序：\n");
	start = clock();
	Heap_Sort(c, num);
	finish = clock();
	if (Order_Array(c, num))
	{
		printf("数组已从小到大排序\n");
	}
	duration = (double)(finish - start) / CLOCKS_PER_SEC;
	printf("堆排序消耗的时间:  %f s\n", duration);

	//快速排序
	printf("\n---------------------\n");
	printf("快速排序：\n");
	start = clock();
	Random_Quick_Sort(d, 0, num - 1);
	finish = clock();
	if (Order_Array(d, num))
	{
		printf("数组已从小到大排序\n");
	}
	duration = (double)(finish - start) / CLOCKS_PER_SEC;
	printf("快速排序消耗的时间:  %f s\n", duration);

	//计数排序
	printf("\n---------------------\n");
	printf("计数排序：\n");
	start = clock();
	Counting_Sort(e, num, maxnum);
	finish = clock();
	if (Order_Array(e, num))
	{
		printf("数组已从小到大排序\n");
	}
	duration = (double)(finish - start) / CLOCKS_PER_SEC;
	printf("计数排序消耗的时间:  %f s\n", duration);

	//基数排序
	printf("\n---------------------\n");
	printf("基数排序：\n");
	start = clock();
	Radix_Sort(f, num, maxnum, 10);
	finish = clock();
	if (Order_Array(f, num))
	{
		printf("数组已从小到大排序\n");
	}
	duration = (double)(finish - start) / CLOCKS_PER_SEC;
	printf("基数排序消耗的时间:  %f s\n", duration);


	//随机选择
	printf("\n---------------------\n");
	printf("随机选择：\n");
	start = clock();
	printf("数组第 %d 个顺序统计量为 %d\n", oeder_statistic, Randomized_Select(g, 0, num - 1, oeder_statistic));
	finish = clock();
	duration = (double)(finish - start) / CLOCKS_PER_SEC;
	printf("随机选择消耗的时间:  %f s\n", duration);


	free(a);
	free(b);
	free(c);
	free(d);
	free(e);
	free(f);
	free(g);

	return 0;
}

时长比较

数组大小为100000
数组值的范围为 0 -- 100000000
---------------------
插入排序：
数组已从小到大排序
插入排序消耗的时间:  5.605000 s

---------------------
归并排序：
数组已从小到大排序
归并排序消耗的时间:  0.110000 s

---------------------
堆排序：
数组已从小到大排序
堆排序消耗的时间:  0.085000 s

---------------------
快速排序：
数组已从小到大排序
快速排序消耗的时间:  0.039000 s

---------------------
计数排序：
数组已从小到大排序
计数排序消耗的时间:  0.606000 s

---------------------
基数排序：
数组已从小到大排序
基数排序消耗的时间:  0.081000 s

---------------------
随机选择：
数组第 50000 个顺序统计量为 16458
随机选择消耗的时间:  0.004000 s

数组大小为100000
数组值的范围为 0 -- 10000
---------------------
插入排序：
数组已从小到大排序
插入排序消耗的时间:  5.578000 s

---------------------
归并排序：
数组已从小到大排序
归并排序消耗的时间:  0.119000 s

---------------------
堆排序：
数组已从小到大排序
堆排序消耗的时间:  0.086000 s

---------------------
快速排序：
数组已从小到大排序
快速排序消耗的时间:  0.061000 s

---------------------
计数排序：
数组已从小到大排序
计数排序消耗的时间:  0.001000 s

---------------------
基数排序：
数组已从小到大排序
基数排序消耗的时间:  0.038000 s

---------------------
随机选择：
数组第 50000 个顺序统计量为 4519
随机选择消耗的时间:  0.008000 s