八大排序（二）堆排序，快速排序，归并排序，计数排序

小灵蛇

发布于 2024-06-06 21:16:04

780

发布于 2024-06-06 21:16:04

文章被收录于专栏：文章部文章部

一.堆排序

（1）原理：

在了解原理之前，我们先来了解什么是堆？

堆是一个数组。它满足两个特点：

1.完全二叉树

2.任一结点的值都是其子树所有结点的最大值①或最小值②

情况①：为最大堆

②为最小堆

原理：

堆排序其实就是利用堆的第二个特点：任一结点的值都是其子树所有结点的最大值或最小值。

只要将需要排序的数组建立成堆，然后每次取出根结点，就把剩下的结点调整成堆；再取出根结点，如此下去，最后便能得到排好序的数据。

（2）代码实现

堆排序主体代码如下：

void AdjustDown(int* hph, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && hph[child + 1] > hph[child])
		{
			++child;
		}
		if (hph[child] > hph[parent])
		{
			swap(&hph[child], &hph[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void Heapsort(int* a, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}

（3）时间空间复杂度与算法稳定性

时间复杂度

时间复杂度：堆排序包括建堆和排序两个操作，建堆过程的时间复杂度是O(n) ，排序过程的时间复杂度是O(nlogn)，所以，堆排序整体的时间复杂度是 O(nlogn)。

空间复杂度

空间复杂度：因为堆排序是就地排序，空间复杂度为常数：O(1)

算法稳定性

稳定性：不稳定。因为在堆的调整过程中，元素进行比较和交换所走的是该结点到叶子结点的一条路径，因此对于相同的元素就可能出现排在后面的元素被交换到前面来的情况。

二.快速排序

（1）原理

快速排序采用的是分治思想，即在一个无序的序列中选取一个任意的基准元素pivot，利用pivot将待排序的序列分成两部分，前面部分元素均小于或等于基准元素，后面部分均大于或等于基准元素，然后采用递归的方法分别对前后两部分重复上述操作，直到将无序序列排列成有序序列。

（2）不同版本快速排序

快速排序的主框架为：

// 假设按照升序对array数组中[left, right)区间中的元素进行排序

void QuickSort(int array[], int left, int right)
{
 if(right - left <= 1)
 return;
 
 // 按照基准值对array数组的 [left, right)区间中的元素进行划分

 int div = partion(array, left, right);
 
 // 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)

 // 递归排[left, div)

 QuickSort(array, left, div);
 
 // 递归排[div+1, right)

 QuickSort(array, div+1, right);
}

我们下面来介绍不同版本的快速排序：

将区间按照基准值划分为左右两半部分的常见方式有：

1.hoare版本

hoare版本主体代码为：

int GetMidi(int* a, int left, int right)//避免大量重复数据带来的负面影响
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[mid] > a[right])
		{
			if (a[left] < a[right])
			{
				return left;
			}
			else
				return right;
		}
	}
	if (a[left] > a[mid])
	{
		if (a[left] < a[right])
		{
			return left;
		}
		else if (a[left] > a[right])
		{
			if (a[right] > a[mid])
			{
				return right;
			}
			else
				return mid;
		}
	}
}
int partsort1(int* a, int left, int right)
{
	int midi = GetMidi(a, left, right);
	swap(&a[left], &a[midi]);
	int key = left;
	while (left < right)
	{
		//找小
		while (left < right && a[right] >= a[key])
		{
			right--;
		}
		while (left < right && a[left] <= a[key])
		{
			left++;
		}
		swap(&a[left], &a[right]);
	}
	swap(&a[key], &a[left]);
	return left;
}
void Quicksort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	if ((end - begin + 1) > 10)
	{
		int keyi = partsort3(a, begin, end);
		Quicksort(a, begin, keyi - 1);
		Quicksort(a, keyi + 1, end);
	}
	else
	{
		Insertsort(a + begin, end - begin + 1);
	}
}

2.挖坑法

挖坑法版本主体代码为：

int GetMidi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[mid] > a[right])
		{
			if (a[left] < a[right])
			{
				return left;
			}
			else
				return right;
		}
	}
	if (a[left] > a[mid])
	{
		if (a[left] < a[right])
		{
			return left;
		}
		else if (a[left] > a[right])
		{
			if (a[right] > a[mid])
			{
				return right;
			}
			else
				return mid;
		}
	}
}
//挖坑法
int partsort2(int* a, int left, int right)
{
	int midi = GetMidi(a, left, right);
	swap(&a[left], &a[midi]);
	int key = a[left];
	int hole = left;
	while (left < right)
	{
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[hole] = a[right];
		hole = right;
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[hole] = a[left];
		hole = left;
	}
	a[hole] = key;
	return hole;
}
void Quicksort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	if ((end - begin + 1) > 10)
	{
		int keyi = partsort3(a, begin, end);
		Quicksort(a, begin, keyi - 1);
		Quicksort(a, keyi + 1, end);
	}
	else
	{
		Insertsort(a + begin, end - begin + 1);
	}
}

3.前后指针

前后指针版本主体代码为：

int GetMidi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[mid] > a[right])
		{
			if (a[left] < a[right])
			{
				return left;
			}
			else
				return right;
		}
	}
	if (a[left] > a[mid])
	{
		if (a[left] < a[right])
		{
			return left;
		}
		else if (a[left] > a[right])
		{
			if (a[right] > a[mid])
			{
				return right;
			}
			else
				return mid;
		}
	}
}
//前后指针
int partsort3(int* a, int left, int right)
{
	int prev = left;
	int cur = prev+1;
	int key = left;
	while (cur<=right)
	{
		while (a[prev + 1] < a[key])
		{
			cur++;
			prev++;
		}
		while (cur<=right&&a[cur] > a[key])
		{
			cur++;
		}
		if(cur<=right)
		{
			swap(&a[++prev], &a[cur]);
		}
	}
	swap(&a[key], &a[prev]);
	return prev;
}
void Quicksort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	if ((end - begin + 1) > 10)
	{
		int keyi = partsort3(a, begin, end);
		Quicksort(a, begin, keyi - 1);
		Quicksort(a, keyi + 1, end);
	}
	else
	{
		Insertsort(a + begin, end - begin + 1);
	}
}

4.非递归

非递归版本的主体代码为：

void STInit(ST* ps)
{
	assert(ps);
	ps->a= NULL;
	ps->top = 0;
	ps->capacity = 0;
}
void STPush(ST* ps, STdatatype x)
{
	assert(ps);
	if(ps->top==ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STdatatype* st = (STdatatype*)realloc(ps->a,sizeof(STdatatype)*newcapacity);
		if (st == NULL)
		{
			perror("relloc failed");
			exit(-1);
		}
		ps->a = st;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}
void STPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}
STdatatype STTop(ST* ps)
{
	assert(ps);
	return ps->a[ps->top-1];
}
int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
void QuicksortNonr(int* a, int begin, int end)
{
	ST st;
	STInit(&st);
	STPush(&st, end);
	STPush(&st, begin);
	while (!STEmpty(&st))
	{
		int left=STTop(&st);
		STPop(&st);
		int right = STTop(&st);
		STPop(&st);
		int key = partsort1(a, left,right);
		if (key + 1 < right)
		{
			STPush(&st, right);
			STPush(&st, key + 1);
		}
		if (key - 1 > left)
		{
			STPush(&st, key - 1);
			STPush(&st, left);
		}
	}
	STDestory(&st);
}

（3）时间空间复杂度与算法稳定性

三.归并排序

（1）原理：

归并排序的原理是：

归并排序算法有两个基本的操作，一个是分，也就是把原数组划分成两个子数组的过程。另一个是治，它将两个有序数组合并成一个更大的有序数组。

（1）将待排序的线性表不断地切分成若干个子表，直到每个子表只包含一个元素，这时，可以认为只包含一个元素的子表是有序表。（2）将子表两两合并，每合并一次，就会产生一个新的且更长的有序表，重复这一步骤，直到最后只剩下一个子表，这个子表就是排好序的线性表。

（2）代码实现

归并排序的主体代码为：

void _Mergesort(int* a, int* tmp, int begin, int end)
{
	if(end<=begin)
	{
		return;
	}
	int mid = (begin + end) / 2;
	_Mergesort(a, tmp, begin, mid);
	_Mergesort(a, tmp, mid + 1, end);
	//归并再拷贝回去
	//[begin,mid]  [mid+1,end]
	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));
}
void Mergesort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc failed");
		exit(-1);
	}
	_Mergesort(a, tmp, 0, n - 1);
	free(tmp);
}

（3）非递归下的归并排序

非递归归并排序的主体代码为：

void MergesortNonr(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc failed");
		exit(-1);
	}
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap-1;
			int index =i;
			if (begin2 >= n)
			{
				break;
			}
			if (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 + i, tmp + i, (end2-i+1) * sizeof(int));
		}
		gap *= 2;
	}
	free(tmp);
}

（4）时间空间复杂度及算法稳定性

时间复杂度

空间复杂度

算法稳定性

四.计数排序

（1）原理

（2）代码实现

计数排序的主体代码如下：

void Countsort(int* a, int n)
{
	int min = a[0], max = a[0];
	for (int i = 0; i < n; i++)
	{
		if (a[i] > max)
		{
			max = a[i];
		}
		if (a[i] < min)
		{
			min = a[i];
		}
	}
	int range = max - min + 1;
	int* tmp = (int*)malloc(sizeof(int) * range);
	if (tmp == NULL)
	{
		perror("malloc failed");
		exit(-1);
	}
	memset(tmp, 0, range * sizeof(int));
	for (int i = 0; i < n; i++)
	{
		tmp[a[i] - min]++;
	}
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (tmp[i]--)
		{
			a[j++] = i + min;
		}
	}
	free(tmp);
}