数据结构6.3--交换排序

目录

交换排序基本思想

1.冒泡排序

2.快速排序

2.1hoare版本

2.2挖坑法

2.3前后指针版本

交换排序基本思想

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

1.冒泡排序

void BubbleSort(int* a, int n)
{
	for(int j=0;j<n;j++)
	{
		for (int i = 1; i < n-j; i++)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
			}
		}
	}
	
}

冒泡排序的特性总结：

1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O（N^2）
3. 空间复杂度：O（1）
4. 稳定性：稳定

2.快速排序

快速排序的思想：

任取待排序元素序列中的某元素作为基准值，按照该排序列将待排序列集合分割成两个序列，左子序列所有元素均小于基准值，右子序列中的所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

2.1hoare版本

动图中的L=left，R=right，P就是基准值

void QuickSort(int* a, int left, int right)
{
	if (left>=right)
	{
		return;
	}

	
	int begin = left, end = right;

	//随机选keyi，是为了防止需要快排的数据本身就是顺序或者逆序，
	//顺序和逆序会导致栈溢出
	//int randi = left+ (rand() % (right - left));
	//Swap(&a[randi], &a[left]);

	//三数取中，也可以解决数据本身就是顺序或逆序的问题
	//int midi = GetMidNumi(a, left, right);
	//Swap(&a[midi], &a[left]);

    int keyi = left;
	while (left < right)
	{
		//右边找比key小
		while (left < right && a[keyi] <= a[right])
			right--;
		//左边找比key大
		while (left < right && a[keyi] >= a[left])
			left++;
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[keyi]);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

特别注意：

为什么右边先走，才能保证相遇的位置小于key

相遇：

1.R找到小，L找大没找到，L遇到R
2.R找不到小，R直接和L相遇了，因为经过上一轮的交换，此时L对应的数小于key

3.R直接到keyi的位置

类似道理，右边做key，左边先走

2.2挖坑法

int PartSort2(int* a, int left, int right)
{

	//三数取中，也可以解决数据本身就是顺序或逆序的问题
	int midi = GetMidNumi(a, left, right);
	Swap(&a[midi], &a[left]);
	
	int key = a[left];
	int hole = left;
	while (left < right)
	{
		//右边找比key小
		while (left < right && key <= a[right])
			right--;
		a[hole] = a[right];
		hole = right;
		//左边找比key大
		while (left < right && key >= a[left])
			left++;

		a[hole] = a[left];
		hole = left;
	}
	a[hole] = key;
	return hole;
}
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;
	int hole = PartSort2(a, left, right);
	QuickSort(a, left, hole-1);
	QuickSort(a, hole + 1, right);
}

2.3前后指针版本

int PartSort3(int* a, int left, int right)
{
    //三数取中
	int midi = GetMidNumi(a, left, right);
	if (midi != left)
		Swap(&a[left], &a[midi]);

	int keyi = left;
	
    int cur = left + 1;
	int prev = left;
	
    while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
			Swap(&a[cur], &a[prev]);
		
		cur++;
	}
	Swap(&a[keyi], &a[prev]);

	keyi = prev;
	return keyi;
}


void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;
	int keyi = PartSort2(a, left, right);
	QuickSort(a, left, keyi-1);
	QuickSort(a, keyi + 1, right);
}

快速排序的特性总结：

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序。
2. 时间复杂度：O(NlogN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定

2.4补充一个快排的非递归

void QuickSortNonR(int* a, int left, int right)
{
	ST st;
	STInit(&st);
	STPush(&st, right);
	STPush(&st, left);

	while (!STEmpty(&st))
	{
		int begin = STTop(&st);
		STPop(&st);
		int end = STTop(&st);
		STPop(&st);
		int keyi = PartSort3(a,begin,end);

		if (keyi + 1 < end)
		{
			STPush(&st, end);
			STPush(&st, keyi + 1);
		}
		
		if (begin < keyi - 1)
		{
			STPush(&st, keyi - 1);
			STPush(&st, begin);
		}
	}
	STDestroy(&st);
}