【算法篇】排序——八大排序（c语言）

简介

冒泡排序

1）比较相邻的元素。如果第一个比第二个大，就交换他们两个；
2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数；
3）针对所有的元素重复以上的步骤，除了最后一个；
4）持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

选择排序

1）首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；
2）再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；
3）重复第二步，直到所有元素均排序完毕。

直接插入排序

插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法步骤：
1）将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列；
2）从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置(相同则插入相等元素后边)。

希尔排序(递减增量排序算法)

核心思想：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
1）选择一个增量序列d[1]，t[2]，…，d[k]，其中d[i]>d[j]，d[k]=1；
2）按增量序列个数k，对序列进行k 趟排序；
3）每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

堆排序

利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

堆排序的平均时间复杂度为Ο(nlogn) 。

算法步骤：

1）创建一个堆H[0…n-1]

2）把堆首（最大值）和堆尾互换

3）把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置

4） 重复步骤2，直到堆的尺寸为1

快速排序

分而治之。通过排序将序列分割为两部分，左边都是比基线条件小的数，右边都是比它大的数；然后再按照这个方法对分割后的两个序列排序。

归并排序

1）将需要排序的序列两两划分进行第一次组内排序；

2）将第一步排好的组再次两两组合进行组内排序；

3）重复以上步骤，直至最后一次排序完成；

基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。

算法分析

1.算法排序的时间复杂度

时间复杂度o(n^2)
冒泡排序，选择排序，插入排序
时间复杂度o(n*logn)
归并排序，快速排序，堆排序，希尔排序
时间复杂度o(n)
基数排序

2.算法排序的空间复杂度

o(1)
冒泡排序，选择排序，插入排序，堆排序，希尔排序
o(nlogn)
快速排序
o(N)
归并排序
o(M)
基数排序

3.稳定性：相同值的元素排序前和排序后值保持不变

稳定的排序算法：冒泡排序，插入排序，归并排序，基数排序；
不稳定的排序算法：选择排序，快速排序，堆排序，希尔排序；

4.不稳定原因

选择排序原因：在选择最小值和位置为0的数交换的时候产生；
快速排序原因：在随机选择相同值中间的数的，两边的相同值的不不是被划分到选择值得左边就是选择值的右边；
堆排序原因：在每次建立大根堆后，堆顶元素会换到最后的位置上去；
希尔排序：步长为2时，第二个1跳两部，造成了不稳定；

5.源码

详情见代码注释

/***********************************************************

Create date:2019.10.8
Designer by:MaL
Compiling environment:Microsoft Visual Studio2012

************************************************************/

#include "sort.h"
#include <assert.h>
#include <string.h>
#include <malloc.h>
#include <stdio.h>
#include <math.h>

void Swap(int *a, int *b)
{
	int c = *a;
	*a = *b;
	*b = c;
}

void Show(int *arr, int len)
{
	for (int i = 0; i < len; ++i)
	{
		printf("%d  ", arr[i]);
	}

	printf("\n");
}

// 冒泡
// O(n^2)   O(1)    稳定 
void BubbleSort(int *arr, int len)
{
	for (int i = 0; i < len - 1; ++i)
	{
		int flag = 0;
		for (int j = 0; j < len - 1 - i; ++j)
		{
			if (arr[j] > arr[j + 1])
			{
				Swap(&arr[j], &arr[j + 1]);
				flag = 1;
			}
		}

		if (flag == 0)
		{
			break;
		}
	}
}

// 选择
// O(n^2)   O(1)    不稳定
void SelectSort(int *arr, int len)
{
	for (int i = 0; i < len - 1; ++i)
	{
		int min = i;
		for (int j = i + 1; j < len; ++j)
		{
			if (arr[j] < arr[min])
			{
				min = j;
			}
		}

		Swap(&arr[i], &arr[min]);
	}
}

//直接插入排序   数据越趋于有序，其效率越高
// O(n^2)     O(1)    稳定
//  最坏 O(n^2)   最好 O(n)
void InsertSort(int *arr, int len)
{
	for (int i = 1; i < len; ++i)
	{
		int tmp = arr[i];
		int j = 0;
		for (j = i - 1; j >= 0; --j)
		{
			if (arr[j] > tmp)
			{
				arr[j + 1] = arr[j];
			}
			else
			{
				break;
			}
		}

		arr[j + 1] = tmp;
	}
}

static void Shell2(int *arr, int len, int d)
{
	for (int k = 0; k < d; ++k)
	{
		for (int i = d + k; i < len; i += d)
		{
			int tmp = arr[i];
			int j = i - d;
			for (; j >= 0; j -= d)
			{
				if (arr[j] > tmp)
				{
					arr[j + d] = arr[j];
				}
				else
				{
					break;
				}
			}

			arr[j + d] = tmp;
		}
	}
}
static void Shell(int *arr, int len, int d)
{
	for (int i = d; i < len; ++i)
	{
		int tmp = arr[i];
		int j = i - d;
		for (; j >= 0; j -= d)
		{
			if (arr[j] > tmp)
			{
				arr[j + d] = arr[j];
			}
			else
			{
				break;
			}
		}

		arr[j + d] = tmp;
	}
}

//希尔排序
//  O(n ^1.3~1.5)   O(1)    不稳定  
void ShellSort(int *arr, int len)
{
	// 目前并没有一个合适的固定分组
	//  分组的值需要两两互质，并且最后一个分组必须为1
	int d[] = { 5, 3, 1 };
	for (int i = 0; i < sizeof(d) / sizeof(d[0]); ++i)
	{
		Shell(arr, len, d[i]);
	}
}

//  O(logn)
static void OneAdjust(int *arr, int len, int root)
{
	int i = root;
	int tmp = arr[i];
	int j = 2 * i + 1; //   left
	while (j < len)
	{
		if (j + 1 < len && arr[j] < arr[j + 1])
		{
			j = j + 1; 
		}
		//  j 就是左右孩子中较大的哪一个
		if (arr[j] > tmp)
		{
			arr[i] = arr[j];
			i = j;  //  下一个子树的根
			j = 2 * i + 1; //  下一个子树的左孩子
		}
		else
		{
			break;
		}
	}

	arr[i] = tmp;
}

//  O(nlogn) 
static void CreateHeap(int *arr, int len)
{
	int root = len / 2 - 1;
	for (; root >= 0; --root)
	{
		OneAdjust(arr, len, root);  // O(logn)
	}
}

//堆排序
//  O(nlogn)     O(1)      不稳定
void HeapSort(int *arr, int len)
{
	CreateHeap(arr, len);  //  O(nlogn)

	for (int i = 0; i < len - 1; ++i)  // O(n)
	{
		Swap(&arr[0], &arr[len - 1 - i]);

		OneAdjust(arr, len - i - 1, 0);  //  O(logn)
	}
}

// O(n)
static  int  OneQuick(int *arr, int i,  int j)
{
	int tmp = arr[i];

	while (i < j)   //   保证找的整个过程  i  < j
	{
		while (i < j)   //  从后向前找比tmp小的元素  保证  i < j
		{
			if (arr[j] < tmp) break;
			j--;
		}

		arr[i] = arr[j];   //   当找到比tmp小的元素后，将j位置的值存储到i位置

		while (i < j)  //  从前向后找比tmp大的元素  保证  i < j
		{
			if (arr[i] > tmp) break;
			i++;
		}

		arr[j] = arr[i];  //   当找到比tmp大的元素后，将i位置的值存储到j位置
	}

	arr[i] = tmp;   //   i之前的数据都比tmp小， 之后的数据都比tmp大

	return i;
}

// O(nlogn)     O(logn)      不稳定
static void Quick(int *arr, int left, int right)
{
	// O(n)
	int mod = OneQuick(arr, left, right);

	if (mod - left > 1)   //  i左边剩余的数据是否超过1个
	{
		Quick(arr, left, mod - 1);
	}
	if (right - mod > 1)  // i右边剩余的数据是否超过1个
	{
		Quick(arr, mod + 1, right);
	}
}

//  
static void  ForQuick(int *arr, int left, int right)
{
	Stack st;
	int size = (int)(log10((double)(right - left + 1)) / log10((double)2));
	size = (size + 1) * sizeof(int) * 2;
	st.data = (int *)malloc(size);
	assert(st.data != NULL);
	st.top = 0;

	st.data[st.top++] = left;
	st.data[st.top++] = right;

	while (st.top != 0)
	{
		right = st.data[--st.top];
		left = st.data[--st.top];

		int mod = OneQuick(arr, left, right);

		if (mod - left > 1)
		{
			st.data[st.top++] = left;
			st.data[st.top++] = mod - 1;
		}
		if (right - mod > 1)
		{
			st.data[st.top++] = mod + 1;
			st.data[st.top++] = right;
		}
	}

	free(st.data);
}

//快速排序
void QuickSort(int *arr, int len)
{
	ForQuick(arr, 0, len - 1);
}

// O(n)
static void Meger(int *arr, int len,  int width, int *brr)
{
	int L1 = 0;
	int H1 = L1 + width - 1;
	int L2 = H1 + 1;
	int H2 = L2 + width - 1 < len - 1 ? L2 + width - 1 : len - 1;
	int num = 0;

	while (L1 < len && L2 < len)
	{
		while (L1 <= H1 && L2 <= H2)
		{
			if (arr[L1] < arr[L2])
			{
				brr[num++] = arr[L1++];
			}
			else
			{
				brr[num++] = arr[L2++];
			}
		}

		while (L1 <= H1)
		{
			brr[num++] = arr[L1++];
		}

		while (L2 <= H2)
		{
			brr[num++] = arr[L2++];
		}

		L1 = H2 + 1;
		H1 = L1 + width - 1 < len - 1 ? L1 + width - 1 : len - 1;
		L2 = H1 + 1;
		H2 = L2 + width - 1 < len - 1 ? L2 + width - 1 : len - 1;
	}

	while (L1 <= H1)
	{
		brr[num++] = arr[L1++];
	}

	for (int i = 0; i < len; ++i)
	{
		arr[i] = brr[i];
	}
}

//归并排序
// O(nlogn)    O(n)     稳定
void MegerSort(int *arr, int len)
{
	int *brr = (int *)malloc(sizeof(int)* len);

	for (int i = 1; i < len; i *= 2)
	{
		Meger(arr, len, i, brr);   // O(n)
	}

	free(brr);
}

//  求数组中最大数字的宽度
static int  GetMaxWidth(int *arr, int len)
{
	int max = arr[0];
	for (int i = 0; i < len; ++i)
	{
		if (arr[i] > max)  max = arr[i];
	}

	int width = 0;
	while (max)  //  12
	{
		width++;
		max /= 10;
	}

	return width;
}

//  求data的倒数第i+1位上的值
static int GetNumOfWidth(int data, int i)
{
	while (i)
	{
		data /= 10;
		i--;
	}

	return data % 10;
}

// O(d * n)      O(k + n)     稳定
// 基数排序      不需要比较的排序
void RadixSort(int *arr, int len)
{
	/* 
	    1、创建队列
		2、先求最大数字的位数
		3、求出相应位数的值， 并根据位数值将其存储相应的队列中
		4、按顺序输出所有队列中的值，  循环处理3,4步，循环次数由第一步算出
	*/

	Que que[10];
	for (int i = 0; i < 10; ++i)
	{
		que[i].data = (int*)malloc(sizeof(int)* len);
		assert(que[i].data != NULL);
		que[i].head = que[i].tail = 0;
	}

	int width = GetMaxWidth(arr, len); // O(n)

	for (int i = 0; i < width; ++i)  // O(d * n)
	{
		//  将数组中所有的数字取其相应位数的值，并将其存储到相应的队列中
		for (int j = 0; j < len; ++j)
		{
			int  num = GetNumOfWidth(arr[j], i);
			que[num].data[que[num].tail++] = arr[j];
		}

		int k = 0;
		for (int m = 0; m < 10; ++m)
		{
			while (que[m].head != que[m].tail)
			{
				arr[k++] = que[m].data[que[m].head++];
			}
		}

		for (int n = 0; n < 10; ++n)
		{
			que[n].head = que[n].tail = 0;
		}
	}

	for (int i = 0; i < 10; ++i)
	{
		free(que[i].data);
	}
}