八大排序之交换排序

目录

一 冒泡排序

二 快速排序

 快速排序的递归版本（hoare）

图解：

1 思想：

2 几个问题

代码：

快速排序之挖坑法

思想：

图解：

代码：

前后指针法

基本思想：

图解：

代码

对快速排序的优化

1 对有序或者接近有序的优化

2 对递归的优化

快速排序的非递归写法

---

一 冒泡排序

可以观看我之前写的博客：一键跳转

可爱的排序——冒泡排序_zhengyawen666的博客-CSDN博客

二 快速排序

 快速排序的递归版本（hoare）

图解：

1 思想：

以单趟排序为例子，

① 选定一个keyi值，一般选择最左边的或者最右边的值

② 如果选择最左边的值，那么就让右边的先走。以排升序为例，要保证一趟排序之后，keyi对应的值的左边的都比keyi该处值小，keyi所对应的值右边的数字都比keyi该处值大。那么右边需要找到不符合条件的小于keyi处值的和左边大于keyi处值的进行交换

③最后左右一定会相遇，相遇处的值和keyi处进行交换

单趟排序排好之后，只需要根据二叉树里的思想，去依次递归他的左区间和右区间就可以了

递归结束的条件：该区间只有一个值，begin==end;该区间不存在，无值：begin>end

2 几个问题

关于为什么先让右边的走：

最后一次是需要交换keyi和right所对应的位置的值的，为了保证keyi对应的值的左边的都比keyi该处值小，keyi所对应的值右边的数字都比keyi该处值大，也就是把小于keyi处的值换到最开始的位置，那么必须要保证该处的值是要小于keyi所对应的值的

让右边先走无非这几种结果：

① 右边的去遇左边的

1 最特殊的情况，右边一直找不到比keyi所对应的值更小的值，直接到达了最左边的位置 交换keyi处值和right，依旧符合上述规则

2 右边走了，左边走，找到对应的值进行交换，那么左边的就是较小的值了，右边去遇左边的，也可以保证最后的相遇处的值是小于keyi处值的

②左边去遇右边的

那么也就是说最后相遇处的值就是右边较小的（左边找大一直找不到）

这样子的话，可以保证最后换到keyi处的值一定是要小于keyi的

同理，如果让右边作为keyi值的话，那么就需要左边先走

关于为什么取keyi下标，而不是创建临时变量存储最左边的值：

如果是临时变量的话，最后交换的时候如果交换了临时变量的值，那么对数组没影响，还要经过其他的处理工作

关于为什么while内层的while依然需要比较left

代码：

int part(int* a, int left,int right)
{
	assert(a);
	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]);
                        
	return right;
}
 
void QuickSort(int* a, int begin, int end)
{
	assert(a);
 
	if (begin >= end)
	{
		return;
	}
 
	int keyi = part(a, begin, end);
	QuickSort(a, keyi + 1, end);
	QuickSort(a, begin, keyi - 1);
	
}

快速排序之挖坑法

通过Hoare法的快速排序，我们发现这个问题比较难理解：

为什么如果选择左边作为基准值，要让右边先走；或者反之

思想：

因此挖坑法直接将keyi下标对应的值存储在一个tmp中，形成一个坑位。

其他的步骤和Hoare法的思想是差不多的。

因为左边形成了坑位，所以右边要去找数，填到左边的这个坑位中去；

同时填到坑位中去之后，右边的值形成新的坑位。

最后迭代，两者相遇的位置形成的坑中填入最开始保存的keyi下标处的值即可

图解：

 

代码：

int Hole(int* a, int left, int right)
{
	assert(a);
	int tmp = a[left];
 
	int tmpi = left;
 
	while (left < right)
	{
		while (left<right && a[right]>tmp)
		{
			right--;
		}
		Swap(&a[tmpi], &a[right]);
		tmpi = right;
 
		while (left < right && a[left < tmp])
		{
			left++;
		}
		Swap(&a[tmpi], &a[left]);
		tmpi = left;
	}
	Swap(&a[right], &a[tmpi]);
 
	return tmpi;
}
void QuickSort2(int* a, int left, int right)
{
	assert(a);
 
	if (right <= left)
	{
		return;
	}
 
	int middle = Hole(a, left, right);
	QuickSort2(a, left, middle - 1);
	QuickSort2(a, middle + 1, right);
}

前后指针法

前后指针法相对于前两种方法更加的简便也更加的抽象

基本思想：

定义两个指针，一个是prev指向数组第一个位置，一个cur指向prev的下一个位置。

cur往后找小，如果找到对应的小的值，那么prev自增之后，再将cur处的值赋值给prev。

如果没找到小，cur还是往后走。

因此cur在循环中是一直往后的。

所以cur和prev交换的条件是当cur找到小并且在循环内部。

当cur达到最后的时候，交换prev和key的值。最后返回的prev作为下一次排序的中间值

图解：

 

一趟排序就走好了

代码

有可能存在自己和自己交换的情景：当cur没有找到小的时候，这时候如果还要交换的话就是自己=和自己换，这样是没有必要的，可以加一句判断避免交换。

int Point(int* a, int left, int right)
{
	assert(a);
	
	int keyi = left;
	int prev = left;
	int cur = prev + 1;
 
	while (cur <= right)
	{
		if(a[cur] < a[keyi])//while(a[cur] > a[keyi] && ++prev!= cur) 既可以避免自己和自己交换又可以改变prev的值
		{
			++prev;
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	Swap(&a[prev], &a[keyi]);
 
	return prev;
}

对快速排序的优化

1 对有序或者接近有序的优化

我们可以知道，基准值的选择对快速排序造成了很大的影响。如果数组已经是有序或者是倒序的情况下，是最不利于发挥快速排序的优势的。因为如果是上述的情况，每次排序都只减少一个值，最坏时是O（n^2）,和冒泡排序差不多了（key为第一个值或者最后一个值）

但是如果数组是随机的或者选择数的时候不选择第一个或者最后一个，而是尽可能随机的选择，那么效率上就会优化很多。

这里提出一个三数取中，也就是说将第一个和最后一个和中间的那三个数进行比较，选出三者中间的那一个作为key值

int key(int* a, int left, int right)
{
	int middle = left + (left - right) / 2;//防止越界
 
	if (a[left] > a[right])
	{
		if (a[right] > a[middle])
		{
			return  right;
		}
		else
		{
			if (a[left] > a[middle])
			{
				return middle;
			}
			else
			{
				return left;
			}
 
		}
	}
	else
	{
		if (a[left] > a[middle])
		{
			return left;
		}
		else
		{
			if (a[right] > a[middle])
			{
				return middle;
			}
			else
			{
				return right;
			}
		}
	}
 
}

int mid = key(a, left, right);
	Swap(&a[left], &a[mid]);
	//找到中间的那个值的下标并且把值放到left的位置上，让keyi定位的时候能取到 优化1
	int keyi = left;
	int prev = left;
	int cur = prev + 1;

2 对递归的优化

上述的快速排序是在递归的思想下实现的，但是递归的次数一多，就非常容易爆栈，所以我们可以在一个较小的区间用插入排序进行排序，大区间继续用快速排序，虽然也有递归，但是次数减少很多了，至少减少了三层递归，减少了80%以上的递归

void QuickSort3(int* a, int left, int right)
{
	assert(a);
 
	if (right <= left)
	{
		return;
	}
	if (right - left + 1 < 10)
	{
		InsertSort(a, right - left + 1);
	}//优化递归次数
	else
	{
		int middle = Point(a, left, right);
		QuickSort3(a, left, middle - 1);
		QuickSort3(a, middle + 1, right);
	}
}

 

快速排序的非递归写法

虽然快速排序经过了区间上的优化，减少了递归次数，但还是总归有递归的

那么我们可以利用栈这种数据结构的特性，来模拟递归的过程，实现栈的非递归写法

void QuickSortNorecurrence(int* a, int left, int right)
{
	assert(a);
	std::stack<int>stack;
 
	stack.push(right);
	stack.push(left);//先将整段区间入栈
 
	while (!stack.empty())//不为空的时候就进行出栈和入栈
	{
		left = stack.top();
		stack.pop();
 
		right = stack.top();
		stack.pop();//取出了left right这段区间
 
		int mid = Point(a, left, right);//用前后指针法对这样的一段区间进行排序获得中间值以便后续排序
 
		if (left < mid - 1)
		{
			stack.push(mid - 1);
			stack.push(left);
		}//当左区间内有值，就入栈
 
		if (mid + 1 < right)
		{
			stack.push(right);
			stack.push(mid + 1);
		}//当右区间内有值，就入栈
 
		//相当于带出一段区间的时候重新入两段区间
		//如果一段区间已经没值了，就不需要再入这一段区间了，相当于这一层递归走到尽头之后就去进行其他的递归
	}
}