数据结构之八大排序算法

前言：各位铁子们好啊，博客已经好久没有更新了。今天就来看看新的文章吧。

在日常生活中，我们能够发现在许多地方会存在排序的问题。比如学校排名，成绩排名，手机销量排名等等。而常见的排序有八种，我们一起来看看都有哪八种排序算法。

1. 直接插入排序

直接插入排序的基本思想是：将待排序的关键码值按照大小插入到一个已经有序的序列中，直到将所有的关键码值插入完为止，得到一个新的有序序列。

//时间复杂度O(N^2)
void InsertSort(int* arr, int n)
{
	for (int i = 0; i < n; ++i)
	{
		int tmp = arr[i];
		int end = i - 1;
		while (end >= 0)
		{
			if (arr[end] > tmp)
			{
				arr[end + 1] = arr[end];
				--end;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = tmp;
	}
}

若end>=0，说明应该继续比较当前end所处位置的关键码值与待排序
关键码值的大小关系。若end位置的关键码值大，就将end位置的关键
码值往后移一步，继续--end，重复上述步骤，直到end位置的关键码
值小于等于待排序的关键码值，跳出循环。此时end+1的位置就是待
排序关键码值应该插入的位置。

2. 希尔排序

希尔排序是对于直接插入排序的一种优化，又叫做缩小增量法。希尔排序的基本思想是：先选定一个整数（通常是gap=gap/3+1）,把待排序文件所有记录分成各组，所有距离相等的记录分在同一组内，并对每一组内的记录进行排序，然后gap=gap/3+1得到下一个整数，再将数组分成各组，进行插入排序。当gap=1时，就相当于直接插入排序。

void ShellSort(int* arr, int n)
{
	int gap = n;
	//gap > 1都是预排序，目的是为了让数组更接近有序
	while(gap > 1)
	{
	//组数越多，循环次数多
	//组数越少，每组内比较的次数增多
	//3是一个折中的取法
	//+1（只有一组，相当于直接插入排序）是为了保证最后一组数据是有序的
		gap = gap / 3 + 1;
		for (int j = 0; j < n; ++j)
		{
			int tmp = arr[j];
			int end = j - gap;
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}
}

对待排序文件记录进行分组，对每一组的记录先进行排序，若
arr[end]>tmp，将当前end位置的记录往后移，更新end，继续判断
end位置的关键码值与tmp的大小关系，若arr[end]<tmp，就跳出循
环，此时end+gap就是待排序关键码值要插入的位置，再重新分
组，重复上述步骤。

希尔排序特性总结：

1.希尔排序是对直接插入排序的优化。

2.gap>1都是预排序，目的是为了让数组更加接近有序，gap=1，就相当于直接插入排序。

3. 直接选择排序

1.在元素集合arr[i]...arr[n-1]选择最小（或最大）的元素
2.若它不是这组元素中的第一个（或最后一个）元素时，就将它与这
组元素中的第一个（或最后一个）元素进行交换。
3.在剩余的元素集合中arr[i+1]...arr[n-2]，重复上述步骤，直到集合剩
余一个元素

//时间复杂度O(N^2)
//直接选择排序
void SelectSort(int* arr, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		//最小值和最大值都要从begin位置开始找起，因为begin位置的元素有可能就是最大值或最小值
		int mini = begin, maxi = begin;
		//找最大，小值
		for (int i = begin + 1; i <= end; ++i)
		{
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
		}
		if (maxi == begin)
		{
			maxi = mini;
		}
		swap(&arr[begin], &arr[mini]);
		swap(&arr[maxi], &arr[end]);
		++begin;
		--end;
	}
}

从begin~end区间内mini找最小值，maxi找最大值，找到后mini位置
的元素与begin位置的元素进行交换，maxi与end元素进行交换。

4. 堆排序

堆排序是一种利用堆这种数据结构的排序算法。升序建大堆，降序建小堆。

void AdjustDown(int* arr, int parent, int n)
{
	//左孩子
	int child = 2 * parent + 1;
	while (child < n)
	{
		//右孩子大，++child
		if (child + 1 < n && arr[child + 1] > arr[child])
		{
			++child;
		}
		//孩子节点大于父节点
		if (arr[child] > arr[parent])
		{
			swap(&arr[child], &arr[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}
//堆排序
void HeapSort(int* arr, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(arr, i, n);
	}
	int end = n - 1;
	while (end > 0)
	{
		swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end);
		--end;
	}

从最后一棵子树开始进行向下调整算法，直到根节点调整完毕，此时
为一个有效的堆。再将根节点与最后一个节点进行交换，调整堆，删
除最后一个节点。重复上述步骤，直至元素有序。

5. 归并排序

归并排序采用的是分治法，是将已有序的子序列进行合并，得到一个完全有序的序列。

void _MergeSort(int* arr, int left, int right, int* tmp)
{
	if (left >= right)
	{
		return;
	}
	int mid = ((right - left) >> 1) + left;
	//划分左右区间
	//左区间  [left,mid]
	//右区间  [mid + 1,right]
	_MergeSort(arr, left, mid, tmp);
	_MergeSort(arr, mid + 1, right, tmp);
	//进行合并
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = begin1;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] > arr[begin2])
		{
			tmp[index++] = arr[begin2++];
		}
		else
		{
			tmp[index++] = arr[begin1++];
		}
	}
	//若某子数组有剩余元素，则将该数组剩余元素依次填充
	while (begin1 <= end1)
	{
		tmp[index++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[index++] = arr[begin2++];
	}
	for (int i = left; i <= right; ++i)
	{
		arr[i] = tmp[i];
	}
}
//归并排序
void MergeSort(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	_MergeSort(arr, 0, n - 1, tmp);
	free(tmp);
}

对一个序列不断地进行划分左右区间，直到不能划分为止，再对子区
间依次进行排序，合并即可。

6. 计数排序（非比较排序）

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

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

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

//计数排序
void CountSort(int* arr, int n)
{
	//求数组内最大，最小值
	int max = arr[0], min = arr[0];
	for (int i = 0; i < n; ++i)
	{
		if (arr[i] > max)
		{
			max = arr[i];
		}
		if (arr[i] < min)
		{
			min = arr[i];
		}
	}
	//开空间
	int gap = max - min + 1;
	int* count = (int*)calloc(sizeof(int), gap);
	//统计每一个元素出现的次数
	for (int i = 0; i < n; ++i)
	{
		count[arr[i] - min]++;
	}
	//排序
	int index = 0;
	for (int i = 0; i < gap; ++i)
	{
		while (count[i]--)
		{
			arr[index++] = i + min;
		}
	}
	free(count);
}

之所以开空间没有按照元素的个数去开空间，是因为如果元素个数非
常庞大的情况下，可能会申请失败，浪费空间。因此对原数组进行遍
历，求数组内的最大值和最小值，再开辟空间。统计原数组内每一个
元素出现的次数，根据统计的结果对序列进行排序

7. 快速排序

快速排序的基本思想：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后对左右子序列重复该过程。

7.1 hoare版本的快速排序

思路：

1.创建左右指针，确定基准值。

2.从右往左找比基准值小的，从左往右找比基准值大的，左右指针数据交换，进行下次循环。

//hoare版本
int _QuickSort(int* arr, int left, int right)
{
	int key = left;
	//如果不++left，那么当right指向的数据都大于key(基准
	//值)时，会存在越界问题
	++left;
	while (left <= right)
	{
		//从右往左找比基准值小的
		while (left <= right && arr[right] > arr[key])//arr[right] == arr[key]要不要交换
		{
			--right;
		}
		//从左往右找比基准值大的
		while (left <= right && arr[left] < arr[key])
		{
			++left;
		}
		if (left <= right)
		{
			swap(&arr[left++], &arr[right--]);
		}
	}
	swap(&arr[right], &arr[key]);
	return right;
}

right指针从右往左找比基准值小的数据，left指针从左往右找比基准值
大的数据，左右指针数据进行交换，继续重复上述步骤。跳出循环之
后，right指向的位置就是基准值的位置。

7.2 挖坑法

思路：

创建左右指针。首先从右往左找比基准值小的数据，找到后放入左边坑中，当前位置变为新的“坑”；然后从左往右找比基准值大的数据，找到后放入右边坑中，当前位置变为新的“坑”，结束循环后，将基准值放入当前“坑”中，返回当前“坑”下标。

//挖坑法
int _QuickSort1(int* arr, int left, int right)
{
	int key = arr[left];
	int hole = left;
	while (left < right)
	{
		//从右往左找比基准值小的
		while (left < right && arr[right]  >= key)
		{
			--right;
		}
		arr[hole] = arr[right];
		hole = right;
		//从左往右找比基准值大的
		while (left < right && arr[left] <= key)
		{
			++left;
		}
		arr[hole] = arr[left];
		hole = left;
	}
	arr[hole] = key;
	return hole;
}

7.3 lomuto前后指针法

思路：
创建前后指针，从左往右找比基准值小的数据进行交换，使小的数据都排在基准值左边。

int _QuickSort2(int* arr, int left, int right)
{
	int key = left;
	int prev = left, cur = prev + 1;
	while (cur <= right)
	{
		//从左往右找比基准值小的数据
		if (arr[cur] < arr[key] && ++prev != cur)
		{
			swap(&arr[prev], &arr[cur]);
		}
		++cur;
	}
	swap(&arr[prev], &arr[key]);
	return prev;
}
//快速排序
void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int key = _QuickSort(arr, left, right);
	
	//划分左右序列
	QuickSort(arr, left, key - 1);
	QuickSort(arr, key + 1, right);
}

基准值确定之后，在对原数组进行左右区间划分，重复上述步骤。

7.4 非递归版本的快速排序

//非递归版本（栈实现）
void QuickSortNonR(int* arr, int left, int right)
{
	Stack s;
	//栈初始化
	StackInit(&s);
	//栈顶插入数据
	StackPush(&s, right);
	StackPush(&s, left);
	//判断栈是否为空
	while (!StackEmpty(&s))
	{
		//取栈顶数据
		int begin1 = StackTop(&s);
		StackPop(&s);
		int end1 = StackTop(&s);
		StackPop(&s);

		int key = begin1;
		int prev = begin1;
		int cur = prev + 1;
		while (cur <= end1)
		{
			if (arr[cur] < arr[key] && ++prev != cur)
			{
				swap(&arr[cur], &arr[prev]);
			}
			++cur;
		}
		swap(&arr[prev], &arr[key]);
		if (prev + 1 < end1)
		{
			StackPush(&s,end1);
			StackPush(&s, prev + 1);
		}
		if (begin1 < prev - 1)
		{
			StackPush(&s, prev - 1);
			StackPush(&s, begin1);
		}
	}
	StackDestroy(&s);
}

先入右区间的左右端点，再入左区间的左右端点，因为栈遵从先入后出的原则。