[数据结构与算法] 【数据结构与算法】【C】

🐱作者：傻响
🐱专栏：《数据结构与算法》
🔥格言：你只管努力，剩下的交给时间！

1、排序的概念及其运用

1.1排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。 稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。 内部排序：数据元素全部放在内存中的排序。 外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

1.2 常见的排序算法

1.3 排序算法接口

// 打印数组
void SortPrint(int* _array, int size);
// 插入排序
void InsertSort(int* _array, int size);
// 希尔排序
void ShellSort(int* _array, int size);
// 直接选择排序
void SelectSort(int* _array, int size);
// 堆排序
void HeapSort(int* _array, int size);
// 冒泡排序
void BubbleSort(int* _array, int size);
// 递归快速排序
void QuickSort(int* _array, int begin, int end);
int GetMidInster(int* _array, int left, int right); // 三数取中

// 非递归快速排序
void QuickSortNonR(int* _array, int begin, int end);



void TestInsertSort()
{
	int _array[] = { 44,66,76,2,10 };
	InsertSort(_array, sizeof(_array) / sizeof(_array[0]));
	SortPrint(_array, sizeof(_array) / sizeof(_array[0]));
}
void TestShellSort()
{
	int _array[] = { 9,8,7,6,5,4,3,2,1,0 };
	ShellSort(_array, sizeof(_array) / sizeof(_array[0]));
	SortPrint(_array, sizeof(_array) / sizeof(_array[0]));
}
void TestSelectSort()
{
	int _array[] = { 22,33,55,77,33,8,1,76,32,93,12 };
	SelectSort(_array, sizeof(_array) / sizeof(_array[0]));
	SortPrint(_array, sizeof(_array) / sizeof(_array[0]));
}
void TestHeapSort()
{
	int _array[] = { 22,33,55,77,33,8,1,76,32,93,12 };
	HeapSort(_array, sizeof(_array) / sizeof(_array[0]));
	SortPrint(_array, sizeof(_array) / sizeof(_array[0]));
}
void TestBubbleSort()
{
	int _array[] = { 22,33,55,77,33,8,1,76,32,93,12 };
	BubbleSort(_array, sizeof(_array) / sizeof(_array[0]));
	SortPrint(_array, sizeof(_array) / sizeof(_array[0]));
}
void TestQuickSort()
{
	int _array[] = { 6,1,2,7,9,3,4,5,10,8 };
	QuickSort(_array, 0, sizeof(_array) / sizeof(_array[0])-1);
	SortPrint(_array, sizeof(_array) / sizeof(_array[0]));
}
void TestQuickSortNonR()
{
	int _array[] = { 6,1,2,7,9,3,4,5,10,8 };
	QuickSortNonR(_array, 0, sizeof(_array) / sizeof(_array[0]) - 1);
	SortPrint(_array, sizeof(_array) / sizeof(_array[0]));
}
void TestTop()
{
	// 基准时间
	srand((unsigned int)time(NULL));
	int N = 1000000;

	// 开辟空间
	int* _array1 = (int*)malloc(sizeof(int) * N);
	assert(_array1);
	int* _array2 = (int*)malloc(sizeof(int) * N);
	assert(_array2);
	int* _array3 = (int*)malloc(sizeof(int) * N);
	assert(_array3);
	int* _array4 = (int*)malloc(sizeof(int) * N);
	assert(_array4);
	int* _array5 = (int*)malloc(sizeof(int) * N);
	assert(_array5);
	int* _array6 = (int*)malloc(sizeof(int) * N);
	assert(_array6);

	for (int i = 0; i < N; i++)
	{
		_array1[i] = rand();
		_array2[i] = _array1[i];
		_array3[i] = _array2[i];
		_array4[i] = _array3[i];
		_array5[i] = _array4[i];
		_array6[i] = _array5[i];
	}

	// 时间记录
	int begin1 = clock();
	//InsertSort(_array1, N);
	int end1 = clock();

	int begin2 = clock();
	ShellSort(_array2, N);
	int end2 = clock();

	int begin3 = clock();
	//SelectSort(_array3, N);
	int end3 = clock();

	int begin4 = clock();
	HeapSort(_array4, N);
	int end4 = clock();

	int begin5 = clock();
	//BubbleSort(_array5, N);
	int end5 = clock();

	int begin6 = clock();
	QuickSort(_array6, 0, N-1);
	int end6 = clock();

	// 打印时间
	printf("InsertSort Time : %d\n", end1 - begin1);
	printf("ShellSort Time : %d\n", end2 - begin2);
	printf("SelectSort Time : %d\n", end3 - begin3);
	printf("HeapSort Time : %d\n", end4 - begin4);
	printf("Bubble Time : %d\n", end5 - begin5);
	printf("QuickSort Time : %d\n", end6 - begin6);

	free(_array1);
	free(_array2);
	free(_array3);
	free(_array4);
	free(_array5);
}

2、常见排序算法的实现

2.1 插入排序

基本思想：直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

2.1.1直接插入排序

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移

第一轮：从第二位置的 6 开始比较，比前面 7 小，交换位置。

第二轮：第三位置的 9 比前一位置的 7 大，无需交换位置。

第三轮：第四位置的 3 比前一位置的 9 小交换位置，依次往前比较。

第四轮：第五位置的 1 比前一位置的 9 小，交换位置，再依次往前比较。

2.1.2 希尔排序( 缩小增量排序 )

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

2.2.1 直接选择排序

2.2.2 堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

2.3 交换排序

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

2.3.1冒泡排序

2.3.2快速排序

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