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

5.1?排序的概念及其运用

5.1.1排序的概念

5.1.2排序运用

?

5.1.3 常见的排序算法

?

5.2?常见排序算法的概念

5.2.1 插入排序?

?

?

5.2.2 选择排序

5.2.2.3 堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。（若一个二叉树的左、右孩子都比父节点的数据大则称为大堆，反之则称为小堆）。下图演示的是小堆变大堆。

?

5.2.3 交换排序

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

5.2.3.1? 冒泡排序

根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。

5.2.3.2 快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

5.2.4 归并排序

基本思想：

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：

?

5.2.5 非比较排序

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：

1. 统计相同元素出现次数

2. 根据统计的结果将序列回收到原来的序列中

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

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

1.建立三个文件

?

2.代码

//1.Sort.h部分
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <errno.h>
#include <ctype.h>
#include <assert.h>
#include <stdbool.h>
 
 
//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 <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <errno.h>
#include <ctype.h>
#include <assert.h>
#include <stdbool.h>
#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]<a[start], 所以要从右边开始，end的找小，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 <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <errno.h>
#include <ctype.h>
#include <assert.h>
#include <stdbool.h>
#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;
}