【数据结构】交换排序

插入排序链接。
这篇文章讲解交换排序的两种排序：冒泡排序与快速排序。

冒泡排序：

冒泡排序简单不实用，被誉为数据结构的“HelloWord”。

思想：相邻元素两两比较，根据升序或者降序每趟选出一个最值放在数组尾部

我们实现冒泡排序时，先进行一趟冒泡排序，这样容易控制整个程序

注意：n为数组元素个数

for (int j = 0; j < n - 1; j++)
为什么j<n-1而不是j<n，因为我们会访问a[j+1]，故最大的J为n-2
{
	if (a[j] > a[j + 1])
	{
		Swap(&a[j], &a[j + 1]);
	}
}

在进行完一趟后，就可以嵌套一个for循环，因为一趟可以确定一个元素位置，故for (int i = 0; i < n; i++)，
最后我们想，当确定一个元素的位置后，下一次就可以不用管他，故内层for循环再for (int j = 0; j < n - i - 1; j++)

完整代码：

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

快速排序：

先来数一下快排的整体思想（升序）：

先选出一个关键值，进行一次单趟排序，
这趟排序是怎样的排序呢？
只要确保关键值左边的比关键值小，右边的比关键值大就算一趟排序

单趟排序完成后，我们可以利用遍历二叉树的思想

最终完成排序，也就是快排

单趟排序：

既然主要部分是单趟排序，那么就有多种单趟排序的办法，这里我们只说最常用的三种

hoare：

hoare是快排的发明者，故hoare自己搞了一个单趟排序，

思想：
选出一个key值（最左边），
right先走，当 right 找到比 key 小的时候或遇到 left 时停止，
left再走，当 left 找到比 key 大的时候或遇到 right 时停止，
当没有相遇时，他们交换值，
相遇后，将key的值与left（或right，因为相遇时left == right）交换

此时完成单趟排序。

int PartSort1(int* a, int begin, int end)
{
	int left = begin;
	int right = end;
	int keyi = left;
	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		//相遇前，left与right的值交换
		Swap(&a[left], &a[right]);
	}
	//相遇后
	Swap(&a[keyi], &a[right]);

	keyi = left;
	//为什么return呢，马上会讲解
	return keyi;
}

挖坑：

挖坑法的思想整体与hoare一致，不过有点差异。

思想：

将最左边作为关键值，同时作为坑的下标，
同理，right先走，遇到比关键值小的或相遇时停下，将right此时的值给坑，right变成新的坑
left再走，遇到比关键值大的或相遇时停下，将left此时的值给坑，left变成新的坑
当相遇时，将key值给坑

这就是一趟排序

//挖坑
int PartSort2(int* a, int begin, int end)
{
	int left = begin;
	int right = end;
	int key = a[left];
	int holei = left;
	
	while (left < right)
	{
	    // 右边找小，填到左边的坑
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[holei] = a[right];
		holei = right;
		// 左边找大，填到右边的坑
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[holei] = a[left];
		holei = left;
	}
	
	a[holei] = key;
	return holei;
}

前后指针：

前后指针的方法与前两者的思想不同。

---

分解成一步一步，看到最后发现prev与cur之间的就是比key大的，
最后将prev与key的值交换，完成单趟排序

---

这是我们最提倡的一种，根本思想就是：

cur的值大于key时，cur++；
当cur的值小于key时，prev++，将prev与cur的值交换，cur++

int PartSort3(int* a, int begin, int end)
{
	int prev = begin;
	int cur = begin + 1;
	int keyi = begin;
	while (cur <= end)
	{
		if (a[cur] < a[keyi])
		{
			prev++;
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	Swap(&a[prev], &a[keyi]);
	return prev;
}

---

这里解释一下为什么会返回一个key的下标，因为我们是单趟排序，有多种方案
用下图代码实现快排更为方便

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}

	int keyi = PartSort3(a, begin, end);
	//begin keyi end
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

完整代码（3种方式）：

#include "Sort.h"
#include "stack.h"

void Swap(int* e1, int* e2)
{
	int tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}
//hoare
int PartSort1(int* a, int begin, int end)
{
	int left = begin;
	int right = end;
	int mid = (left + right) / 2;
	int midi = getmid(a, mid, left, right);
	Swap(&a[left], &a[midi]);

	int keyi = left;
	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[keyi], &a[right]);

	keyi = left;
	return keyi;
}

//挖坑
int PartSort2(int* a, int begin, int end)
{
	int left = begin;
	int right = end;
	int mid = (begin - end) / 2;
	int midi = getmid(a, mid, left, right);
	Swap(&a[midi], &a[left]);

	int key = a[left];
	int holei = left;
	while (left < right)
	{
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[holei] = a[right];
		holei = right;
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[holei] = a[left];
		holei = left;
	}
	a[holei] = key;
	return holei;
}

//前后指针
int PartSort3(int* a, int begin, int end)
{
	int prev = begin;
	int cur = begin + 1;
	int keyi = begin;
	while (cur <= end)
	{
		if (a[cur] < a[keyi])
		{
			prev++;
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	Swap(&a[prev], &a[keyi]);
	return prev;
}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}

	int keyi = PartSort3(a, begin, end);
	//begin keyi end
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

欢迎讨论哦