第三部分—数据结构与算法基础_5. 排序算法

5.1 排序的概念及其运用

5.1.1排序的概念

5.1.2排序运用

 

5.1.3 常见的排序算法

 

5.2 常见排序算法的概念

5.2.1 插入排序 

 

 

5.2.2 选择排序

 动画演示https://visualgo.net/zh/sorting

5.3 常见排序算法的代码实现

1.建立三个文件

 

2.代码

//1.Sort.h部分
#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
 
 
//0.辅助函数
//0.1交换数值函数声明
void Swap(int* a, int* b);
//0.2打印数组函数声明
void DataPrint(int* data, int n);
 
 
//1.冒泡排序函数声明
void BubbleSort(int* data,int n);
 
 
 
//2.插入排序函数声明
void InsertSort(int* data, int n);
 
 
 
//3.希尔排序函数声明
void ShellSort(int* data, int n);
 
 
 
//4.堆排序函数声明
void HeapSort(int* data, int n);
 
 
 
//5.选择排序函数声明
void SelectSort(int* data, int n);
 
 
 
//6.递归快排序函数声明
void RecursionQuickSort(int* data, int left, int right, int method);
 
 
 
//7.非递归快排序函数声明
void NonRecursionQuickSort(int* data, int begin, int end);
 
 
//8.递归归并排序函数声明
void RecursionMergeSort(int* a, int n);
 
 
//9.非递归归并排序函数声明
void NonRecursionMergeSort(int* a, int n);
 
 
//10.计数排序函数声明
void CountSort(int* data, int n);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
//2.SortFunction.c 部分
#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include"Sort.h"
 
 
 
//0.辅助函数
//0.1交换数值函数实现
void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
 
//0.2打印数组函数实现
void DataPrint(int* data, int n)
{
	int i = 0;
	for (i = 0; i < n; i++)
	{
		printf("%d ", data[i]);
	}
	printf("\n");
}
 
 
 
 
 
//1.冒泡排序函数实现
void BubbleSort(int* data,int n)
{
	int i = 0;
	int j = 0;
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n - 1 - i; j++)
		{
			if (data[j] > data[j + 1])
			{
				Swap(&data[j], &data[j + 1]);
			}
		}
	}
}
 
 
 
 
 
//2.插入排序函数实现
void InsertSort(int* data, int n)
{
	assert(data);
	int i = 0;
	int end = 0;
	int tmp = 0;
	for (i = 0; i < n - 1; ++i)
	{
		end = i;
		tmp = data[end + 1];                           //储存临时值
		while (end >= 0 && data[end] > tmp)            //将data[end]到data[0]的数依次与data[end+1]比较，当小于时跳出循环
		{
			data[end + 1] = data[end];                 //data[end]大于data[end+1]就将值后移
			end--;
		}
		data[end + 1] = tmp;                           //插入该位置
	}
}
 
 
 
 
 
//3.希尔排序函数实现
void ShellSort(int* data, int n)
{
	assert(data);
	int i = 0;
	int end = 0;
	int tmp = 0;
	int gap = n;                               
	while (gap > 1)
	{
		gap = gap / 3 + 1;                                 //依次将gap=4、2、1，进行排序，其中gap=4、2为预排序
		for (i = 0; i < n - gap; i++)                      //i每次加1表示第一组第一个数排完再到第二组第一个数排，每次都切换不同的组排
		{
			end = i;
			tmp = data[end + gap];
			while (end >= 0 && data[end] > tmp)
			{
				data[end + gap] = data[end];
				end = end - gap;
			}
			data[end + gap] = tmp;
		}
	}
}
 
 
 
 
 
//4.1.向上调整函数实现
void HeapAdjustUp(int* data, int childpos)
{
	if (childpos == 0)
	{
		return;
	}
	int parentpos = (childpos - 1) / 2;
 
	while (childpos > 0)
	{
		//建大堆
		if (data[childpos] > data[parentpos])
		{
			Swap(&data[childpos], &data[parentpos]);
			childpos = parentpos;
			parentpos = (childpos - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
 
//4.2.向下调整函数实现
void HeapAdjustDown(int* data, int size, int rootpos)
{
	int parentpos = rootpos;
	int childpos = parentpos * 2 + 1;
	while (childpos < size)                                                    //while循环用于恢复大堆
	{
		if (childpos + 1 < size && data[childpos + 1] > data[childpos])
		{
			childpos++;
		}
 
		if (data[childpos] > data[parentpos])
		{
			Swap(&data[childpos], &data[parentpos]);
			parentpos = childpos;
			childpos = parentpos * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
 
 
//4.堆排序函数实现
void HeapSort(int* data, int n)
{
	int i = 0;
	//建堆
	for (i = 1; i < n; i++)
	{
		HeapAdjustUp(data, i);                                   //依次将每个元素进堆
	}
 
	//升序
	int end = n - 1;
	while (end > 0)
	{
		Swap(&data[0], &data[end]);                              //依次将最大元素放置末尾
		HeapAdjustDown(data, end, 0);
		end--;
	}
}
 
 
 
 
 
//5.选择排序函数实现
void SelectSort(int* data, int n)
{
	assert(data);
	int begin = 0;
	int end = n - 1;
	int i = 0;
	while (begin < end)
	{
		int min = begin, max = begin;
		for (i = begin; i <= end; i++)                 //找出最大和最小的数
		{
			if (data[i] >= data[max])
				max = i;
 
 
			if (data[i] < data[min])
				min = i;
		}
		Swap(&data[begin], &data[min]);                          //将最小值放在首位置
 
		if (begin == max)                                  //如果最大值恰好在begin位置上，那么就要更新max的值     
		{
			max = min;
		}
 
		Swap(&data[end], &data[max]);                            //将最大值放在末位置
		++begin;
		--end;
	}
}
 
 
 
 
 
//6.1.1递归快排序优化1—增加三数取中法选key
int GetMidIndex(int* data, int begin, int end)
{
	int mid = begin + ((end - begin) / 2);
	if (data[begin] < data[mid])
	{
		if (data[mid] < data[end])
		{
			return mid;
		}
		else if (data[begin] > data[end])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
	else if (data[begin] >= data[mid])
	{
		if (data[mid] > data[end])
		{
			return mid;
		}
		else if (data[begin] < data[end])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
}
 
 
//6.1.2递归快排序优化2—递归到小的子区间时使用插入排序
//此处程序见—2.插入排序函数实现
 
 
//6.2递归快排序—hoare法
int PartSort1(int* data, int begin, int end)
{
	int midindex = GetMidIndex(data, begin, end);             //快速排序优化1
	Swap(&data[begin], &data[midindex]);
 
	int key = data[begin];
	int start = begin;
 
	while (begin < end)                                    //最后的交换一定要保证a[begin]
	{
		while (begin < end && data[end] >= key)
		{
			--end;
		}
		while (begin < end && data[begin] <= key)
		{
			++begin;
		}
		Swap(&data[begin], &data[end]);
	}
	Swap(&data[begin], &data[start]);
	return begin;
}
 
 
//6.3递归快排序—挖坑法
int PartSort2(int* data, int begin, int end)
{
	//begin是坑
	int key = data[begin];
	while (begin < end)
	{
		while (begin < end && data[end] >= key)
		{
			end--;
		}
 
		data[begin] = data[end];
 
		while (begin < end && data[begin] <= key)
		{
			begin++;
		}
		data[end] = data[begin];
	}
 
	data[begin] = key;
	return begin;
}
 
 
//6.4递归快排序—前后指针法
int PartSort3(int* data, int begin, int end)
{
	int midindex = GetMidIndex(data, begin, end);                       //快速排序优化1
	Swap(&data[begin], &data[midindex]);
 
	int key = data[begin];
	int prev = begin;
	int cur = begin + 1;
 
	while (cur <= end)
	{
		// cur找小，把小的往前翻，大的往后翻
		if (data[cur] < key && prev++ != cur)
		{
			Swap(&data[cur], &data[prev]);
		}	
		cur++;
	}
	Swap(&data[begin], &data[prev]);
	return prev;
}
 
 
 
 
//6.递归快排序函数实现
void RecursionQuickSort(int* data, int left, int right, int method)
{
	if (left >= right)
	{
		return;
	}
 
	if (right - left  < 5)
	{
		InsertSort(data + left, right - left + 1);                  //快速排序优化2
	}
	else
	{
		if (method == 1)
		{
			int div = PartSort1(data, left, right);
			RecursionQuickSort(data, left, div - 1, method);
			RecursionQuickSort(data, div + 1, right, method);
		}
		else if (method == 2)
		{
			int div = PartSort2(data, left, right);
			RecursionQuickSort(data, left, div - 1, method);
			RecursionQuickSort(data, div + 1, right, method);
		}
		else if (method == 3)
		{
			int div = PartSort3(data, left, right);
			RecursionQuickSort(data, left, div - 1, method);
			RecursionQuickSort(data, div + 1, right, method);
		}
	}
}
 
 
 
 
 
//7.1定义结构体
typedef struct Stack
{
	int* a;
	int top;
	int capacity;
}ST;
 
 
//7.2栈初始化函数实现
void StackInit(ST* pStack)
{
	assert(pStack);
	pStack->a = NULL;
	pStack->top = 0;
	pStack->capacity = 0;
}
 
 
//7.3入栈函数实现
void StackPush(ST* pStack, int x)
{
	assert(pStack);
	if (pStack->capacity == pStack->top)
	{
		int newcapacity = pStack->capacity == 0 ? 4 : (pStack->capacity + 4);
		int* newpStack = (int*)realloc(pStack->a, newcapacity * sizeof(int));
		if (newpStack == NULL)
		{
			printf("StackPush::()%s\n", strerror(errno));
			exit(-1);
		}
		pStack->a = newpStack;
		pStack->capacity = newcapacity;
	}
	pStack->a[pStack->top] = x;
	pStack->top++;
}
 
 
//7.4判断栈是否为空函数实现
bool StackEmpty(ST* ps)
{
	return ps->top == 0;
}
 
 
//7.5获取栈顶元素函数实现
int StackTop(ST* pStack)
{
	if (pStack->top == 0)
	{
		return 0;
	}
	return pStack->a[pStack->top - 1];
}
 
 
//7.6出栈函数实现
void StackPop(ST* pStack)
{
	assert(pStack);
	if (pStack->top > 0)
	{
		pStack->top--;
	}
	else
	{
		return;
	}
}
 
 
//7.7栈销毁函数实现
void StackDestroy(ST* pStack)
{
	assert(pStack);
	free(pStack->a);
	pStack->a = NULL;
	pStack->capacity = 0;
	pStack->top = 0;
}
 
//7.非递归快排序函数实现
void NonRecursionQuickSort(int* data, int begin, int end)
{
	ST st;
	StackInit(&st);
	StackPush(&st, begin);
	StackPush(&st, end);
	//栈不为空，说明还有没处理的区间
	while (!StackEmpty(&st))
	{
		int right = StackTop(&st);
		StackPop(&st);
		int left = StackTop(&st);
		StackPop(&st);
		
		int div = PartSort1(data, left, right);
		
		// 把大于1个数的区间继续入栈
		// [left div-1]
		if (left < div - 1)
		{
			StackPush(&st, left);
			StackPush(&st, div - 1);
		}
 
		// [div+1, right]
		if (div + 1 < right)
		{
			StackPush(&st, div + 1);
			StackPush(&st, right);
		}
	}
	StackDestroy(&st);
}
 
 
 
 
 
//8.1拆分归并函数实现
void _MergeSort(int* a, int begin, int end, int* tmp)
{
	//拆分
	if (begin >= end)
	{
		return;
	}
	int mid = (begin + end) / 2;
 
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid + 1, end, tmp);
 
	//归并
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int index = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[index++] = a[begin1++];
		}
		else
		{
			tmp[index++] = a[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		tmp[index++] = a[begin1++];
	}
 
	while (begin2 <= end2)
	{
		tmp[index++] = a[begin2++];
	}
 
	memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
 
 
//8.递归归并排序函数实现
void RecursionMergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	assert(tmp);
 
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
}
 
 
 
 
 
//9.非递归归并排序函数实现
void NonRecursionMergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		return;
	}
	int gap = 1;
	int i = 0;
	
	while (gap < n)
	{
		for (i = 0; i < n; i = i + 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			int index = i;
 
			//修正end1越界
			if (end1 >= n)
			{
				end1 = n - 1;
			}
 
			//修正begin2越界，即第二个区间不存在
			if (begin2 >= n)
			{
				begin2 = n;
				end2 = n - 1;      //直接舍弃第二个区间
			}
 
			//修正end2越界
			if (begin2 < n && end2 >= n)
			{
				end2 = n - 1;
			}
 
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[index++] = a[begin1++];
				}
				else
				{
					tmp[index++] = a[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				tmp[index++] = a[begin1++];
			}
 
			while (begin2 <= end2)
			{
				tmp[index++] = a[begin2++];
			}
		}
		memcpy(a, tmp, n * sizeof(int));
 
		gap = gap * 2;
	}
 
	free(tmp);
}
 
 
 
 
 
//10.计数排序函数实现
void CountSort(int* data, int n)
{
	int min=data[0];
	int max = data[0];
	int i = 0;
	for (i = 1; i < n; i++)
	{
		if (data[i] < min)
		{
			min = data[i];
		}
		if (data[i] > max)
		{
			max = data[i];
		}
	}
 
	int range = max - min + 1;
	int* countdata = (int*)malloc(sizeof(int*) * range);
	assert(countdata);
 
	memset(countdata, 0, sizeof(int) * range);
 
	//计数
	for (i = 0; i < n; i++)
	{
		countdata[data[i] - min]++;
	}
 
	//排序
	int j = 0;
	for (i = 0; i < range; i++)
	{
		while (countdata[i]--)
		{
			data[j++] = i + min;
		}
	}
}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
//3. Sort.c 部分
#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include"Sort.h"
 
 
 
 
 
//1.冒泡排序测试
void TestBubbleSort()
{
	int data[10] = { 6,9,2,7,4,5,0,3,8,1 };
	int n = sizeof(data) / sizeof(int);
	BubbleSort(data, n);
	printf("冒泡排序 ：");
	DataPrint(data, n);
}
 
 
//2.插入排序测试
void TestInsertSort()
{
	
	int data[10] = { 6,9,2,7,4,5,0,3,8,1 };
	int n = sizeof(data) / sizeof(int);
	InsertSort(data, n);
	printf("插入排序 ：");
	DataPrint(data, n);
}
 
 
 
//3.希尔排序测试
void TestShellSort()
{
	int data[10] = { 6,9,2,7,4,5,0,3,8,1 };
	int n = sizeof(data) / sizeof(int);
	ShellSort(data, n);
	printf("希尔排序 ：");
	DataPrint(data, n);
}
 
 
 
//4.堆排序测试
void TestHeapSort()
{
	int data[10] = { 6,9,2,7,4,5,0,3,8,1 };
	int n = sizeof(data) / sizeof(int);
	HeapSort(data, n);
	printf("堆排序   ：");
	DataPrint(data, n);
}
 
 
 
//5.选择排序测试
void TestSelectSort()
{
	int data[10] = { 6,9,2,7,4,5,0,3,8,1 };
	int n = sizeof(data) / sizeof(int);
	SelectSort(data, n);
	printf("选择排序 ：");
	DataPrint(data, n);
}
 
 
 
//6.递归快排序测试
void TestRecursionQuickSort()
{
	int data1[10] = { 6,9,2,7,4,5,0,3,8,1 };
	int data2[10] = { 6,9,2,7,4,5,0,3,8,1 };
	int data3[10] = { 6,9,2,7,4,5,0,3,8,1 };
	int n = sizeof(data1) / sizeof(int);
 
	RecursionQuickSort(data1, 0, n - 1, 1);
	printf("递归快排序_hoare法(优化1+优化2)    ：");
	DataPrint(data1, n);
 
	RecursionQuickSort(data2, 0, n - 1, 2);
	printf("递归快排序_挖坑法(优化1)           ：");
	DataPrint(data2, n);
 
	RecursionQuickSort(data3, 0, n - 1, 3);
	printf("递归快排序_前后指针法(优化1+优化2) ：");
	DataPrint(data3, n);
}
 
 
 
//7.非递归快排序测试
void TestNonRecursionQuickSort()
{
	int data[10] = { 6,9,2,7,4,5,0,3,8,1 };
	int n = sizeof(data) / sizeof(int);
	NonRecursionQuickSort(data, 0, n - 1);
	printf("非递归快排序                       ：");
	DataPrint(data, n);
}
 
 
 
//8.递归归并排序测试
void TestRecursionMergeSort()
{
	int data[10] = { 6,9,2,7,4,5,0,3,8,1 };
	int n = sizeof(data) / sizeof(int);
	RecursionMergeSort(data, n);
	printf("递归归并排序                       ：");
	DataPrint(data, n);
}
 
 
 
//9.非递归归并排序测试
void TestNonRecursionMergeSort()
{
	int data[10] = { 6,9,2,7,4,5,0,3,8,1 };
	int n = sizeof(data) / sizeof(int);
	NonRecursionMergeSort(data, n);
	printf("非递归归并排序                     ：");
	DataPrint(data, n);
}
 
 
 
//10.计数排序测试
void TestCountSort()
{
	int data[] = { 6,9,2,7,4,5,0,3,8,1 };
	int n = sizeof(data) / sizeof(int);
	CountSort(data, n);
	printf("计数排序                           ：");
	DataPrint(data, n);
}
 
 
 
int main()
{
 
	//1.冒泡排序测试
	TestBubbleSort();
 
 
	//2.插入排序测试
	TestInsertSort();
 
 
	//3.希尔排序测试
	TestShellSort();
 
 
	//4.堆排序测试
	TestHeapSort();
 
 
	//5.选择排序测试
	TestSelectSort();
 
 
	//6.递归快排序测试
	TestRecursionQuickSort();
 
 
	//7.非递归快排序测试
	TestNonRecursionQuickSort();
 
 
	//8.递归归并排序测试
	TestRecursionMergeSort();
 
 
	//9.非递归归并排序测试
	TestNonRecursionMergeSort();
 
 
	//10.计数排序测试
	TestCountSort();
	
	return 0;
}