09交换排序算法---冒泡排序和快速排序_交换排序 (1)请实现冒泡排序 (2)请实现快速排序

---

一、冒泡排序

冒泡排序应该是最简单也是最容易理解的一种排序算法，它的逻辑是每趟将最大的数移到数组的最右边：

我之前写过冒泡排序的详细说明，链接如下：冒泡排序

代码实现：

//交换函数
void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
void BubbleSort(int* a, int n)
{
	int i,j;
	for (i = 0; i < n - 1; i++)//趟数
	{
		int exchange = 0;//如果没有发生排序说明已经有序，exchange为0
		for (j = 0; j < n - i - 1; j++)//交换的次数
		{
			if (a[j] > a[j + 1])//交换两个元素
			{
				Swap(&a[j], &a[j + 1]);
				exchange = 1;//第一趟发生了排序
			}
		}
		if (exchange == 0)//如果没发生排序直接跳出循环
		{
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

1.1.时间空间复杂度分析

最好的情况：排序前的数组已经是有序的，则只需要进行n-1次比较即可，没有数据交换，时间复杂度为O（N）。
最坏的情况：排序前数组，则需要比较并交换n-1+n-2+…3+2+1次，也就是n(n-1)/2次 时间复杂度为O（N²）。
时间复杂度是最坏的情况，O（N²）
空间复杂度是O（1）.

---

二、快速排序

快排的性能在所有排序算法里面是最好的，数据规模越大快速排序的性能越优。快排在极端情况下会退化成 O（N²）的算法，因此假如在提前得知处理数据可能会出现极端情况的前提下，可以选择使用较为稳定的归并排序。

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

1. 首先设定一个分界值，通过该分界值将数组分成左右两部分。
2. 将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
3. 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
4. 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

快速排序的比较和交换方式可以通过递归和非递归的形式完成，每种形式又可以通过三种方式完成：

2.1.快排的递归实现

2.1.1.挖坑法

挖坑法的实现思路是：

1. 选一个数为关键字，同时这个数的下标为坑位pivot，同时定义begin和end，begin左向右走，end从右向左走。（若在最左边挖坑，则需要end先走；若在最右边挖坑，则需要begin先走），这里选择最左边为坑位。
2. 在走的过程中，若end遇到小于key的数，则将该数放入坑位，并在此处形成一个坑位，这时begin再向后走，若遇到大于key的数，则将其放入之前坑位，自己又形成一个坑位。
3. 如此循环下去，直到最终begin和right相遇，这时将key放入坑位，一趟排序就完成。
4. 最终key左边都比它小，右边都比它大：
   

这样一趟排序让6的左边都是比它小的数，右边都是比它大的数，如果再将6的左区间和右区间用相同的方法递归下去，则可以实现最终的排序。

代码实现：

//挖坑法
void QuickSort1(int* a, int left, int right)//left是数组a的左下标，right是右下标
{
	if (left >= right)//当只有一个数据或是序列不存在时，不需要进行操作
	{
		return;
	}
	int begin = left, end = right;//确定begin和end的位置
	int pivot = begin;//选最左边左边为坑
	int key = a[begin];//选最左边的元素为key
	while (begin < end)//begin和end相遇时停止
	{
		//右边找小，放到左边
		while (begin < end && a[end] >= key)//遇到大于等于key的元素就继续向右走
		{
			end--;
		}
		//小的放到坑位，自己形成新的坑位
		a[pivot] = a[end];
		pivot = end;

		//左边找大，自己形成新的坑
		while (begin < end && a[begin] <= key)//遇到比小于等于key的元素就继续往左走
		{
			begin++;
		}
		//大的放到坑位，自己形成新的坑位
		a[pivot] = a[begin];
		pivot = begin;
	}
	a[pivot] = key;//begin和right相遇后跳出循环，将key放入相遇的坑位
	QuickSort1(a, left,pivot-1);//递归左区间
	QuickSort1(a, pivot+1,right);//递归右区间
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

2.1.2.左右指针法

左右指针法和挖坑法差不多，唯一的区别在于左右指针法是交换两个数，挖坑法是将数放入坑里：

1. 选出一个key，一般是数组最左边或是最右边的数。
2. 定义一个begin和一个end，begin从左向右走，end从右向左走。（如果选择最左边的数据作为key，则需要end先走；若选择最右边的数据作为key，则需要left先走）。
3. 以最左边的数为key举例，在走的过程中，若end遇到小于key的数，则停下，begin开始走，直到L遇到一个大于key的数时，将end和begin的内容交换，end再次开始走，如此进行下去，直到end和begin最终相遇，此时交换key和相遇位置的值。
   

另外，这种方法和挖坑法排完一趟后数的顺序是不一样的。

再将6的左区间和右区间用相同的方法递归下去，则可以实现最终的排序。

//左右指针快排
void QuickSort2(int* a, int left, int right)
{
	if (left >= right)//当只有一个数据或是序列不存在时，不需要进行操作
	{
		return;
	}
	int begin = left, end = right;//确定begin和end的位置
	int key = begin;//key为最左边的元素
	while (begin < end)
	{
		//找小
		while (begin < end && a[end] >= a[key])
		{
			end--;
		}
		//找大
		while (begin < end && a[begin] <= a[key])
		{
			begin++;
		}
		Swap(&a[begin], &a[end]);//交换
	}

	Swap(&a[begin], &a[key]);//相遇时和key交换

	QuickSort1(a, left, begin - 1);//key的左序列进递归
	QuickSort1(a, begin + 1, right);//key的右序列进行递归
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

2.1.3.前后指针法

前后指针法的步骤：

1. 选出一个key，一般是最左边。
2. prev指针指向序列开头，cur指针指向prev+1的位置。
3. cur一直往右走，如果cur指向的内容小于key，则prev先向右移动一位，然后交换prev和cur指针指向的内容；若cur指向的内容大于key，则不交换。如此进行下去，直到cur指针越界，此时将key和prev指针指向的内容交换，即完成一次排序。

再将6的左区间和右区间用相同的方法递归下去，则可以实现最终的排序。

//前后指针快排
void QuickSort3(int* a, int left, int right)
{
	if (left >= right)//当只有一个数据或是序列不存在时，不需要进行操作
	{
		return;
	}
	int key = left;
	int prev = left, cur = left + 1;
	while (cur <= right)//当cur>right也就是越界时，跳出循环
	{
		if (a[cur] < a[key] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);//交换
		}
		cur++;
	}
	Swap(&a[key], &a[prev]);//交换key和prev指针指向的内容
	QuickSort3(a, left, prev - 1);//key的左序列进行递归
	QuickSort3(a, prev + 1, right);//key的右序列进行递归
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.2.快排的非递归实现

如果使用非递归实现，也就意味着我们需要使用额外的操作来起到递归的效果，一般来说可以用循环或者栈模拟递归的过程，这里只能使用栈来实现。

既然要用非递归，那么我们原来的递归函数就要修改成非递归只能排一趟了，但具体的思路没有变，只是多了一个返回值：

2.2.1.挖坑法

//挖坑法
int PartSort1(int* a, int left, int right)
{
	if (left >= right)//当只有一个数据或是序列不存在时，不需要进行操作
	{
		return;
	}
	int begin = left, end = right;
	int pivot = begin;
	int key = a[begin];
	while (begin < end)
	{
		//右边找小，放到左边
		while (begin < end && a[end] >= key)
		{
			end--;
		}
		//小的放到坑位，自己形成新的坑位
		a[pivot] = a[end];
		pivot = end;
		//左边找大，自己形成新的坑
		while (begin < end && a[begin] <= key)
		{
			begin++;
		}
		a[pivot] = a[begin];
		pivot = begin;
	}
	a[pivot] = key;
	return pivot;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

2.2.2.左右指针法

//左右指针法
int PartSort2(int* a, int left, int right)
{
	int begin = left, end = right;
	int key = begin;
	while (begin < end)
	{
		//找小
		while (begin < end && a[end] >= a[key])
		{
			end--;
		}
		//找大
		while (begin < end && a[begin]<= a[key])
		{
			begin++;
		}
	Swap(&a[begin], &a[end]);
	}

	Swap(&a[begin], &a[key]);
	return begin;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.2.3.前后指针法

//前后指针法
int PartSort3(int* a, int left, int right)
{
	int index = GetMidIndex(a, left, right);
	Swap(&a[left], &a[index]);

	int key = left;
	int prev = left, cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[key]&&++prev!=cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	Swap(&a[key], &a[prev]);
	return prev;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.2.4.用栈实现非递归

利用栈先进后出的特点，用栈实现非递归的思路：

1. 一开始将数组的最后一个元素的下标和第一个元素的下标入栈。
2. 当栈不为空时，读取栈中的元素，一次读取元素：一个记为left，另一个记为right，这两个元素是排序的左右下标，然后调用快排的单趟排序，排完后获得了key的下标，然后判断key的左序列和右序列是否还需要排序，若还需要排序，就将相应序列的L和R入栈；序列只有一个元素或是不存在则不需要排序，就不需要将该序列的信息入栈。
3. 反复执行步骤2.直到栈为空为止。

在这里需要用到栈的函数，在之前的文章中有线性表之栈和队列

void QuickSortNonR(int* a, int n)
{
	ST st;//创建一个栈
	StackInit(&st);//初始化栈
	//栈里的区间就是需要被单趟分割排序的
	StackPush(&st, n - 1);//将最后一个元素下标入栈
	StackPush(&st, 0);//将第一个元素下标入栈
	while (!StackEmpty(&st))//栈不为空则执行循环
	{
		int left = StackTop(&st);//获取左边第一个元素的下标
		StackPop(&st);//弹出左边第一个元素的下标
		int right = StackTop(&st);//获取右边第一个元素
		StackPop(&st);//弹出右边第一个元素的下标

		int keyIndex = PartSort1(a, left, right);//快排并获取返回的key的位置
		//这一次快排以后，数组的区间如下：
		//[left,keyIndex-1]keyIndex[keyIndex+1,right]
		//接下来只需要将左右区间的left，right压栈即可

		if (keyIndex + 1 < right)
		//如果keyIndex + 1 >= right说明右区间没有元素，不用入栈
		{
			StackPush(&st, right);//右区间的最后一个元素入栈
			StackPush(&st, keyIndex + 1);//右区间第一个元素入栈
		}
		if (left < keyIndex - 1)
		//如果left > keyIndex - 1说明左区间没有元素，不用入栈
		{

			StackPush(&st, keyIndex - 1);//左区间最后一个元素入栈
			StackPush(&st, left);//左区间第一个元素入栈
		}
	}
	StackDestory(&st);//销毁栈
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

注意入栈和出栈的顺序不要弄错。如果是先取left后取right，则应该先入right，后入left。

2.3.快排的优化

2.3.1三数取中

理想情况下，对于一个大小为N的数组，每次递归的左右区间中的元素个数如果都相同，那么只需要调用log₂N次即可。

但是当数组有序或者接近有序时，我们若是依然每次都选取最左边作为key，这就会导致左边区间根本就没有数，右边区间的数是除了key剩下的数，这样就必须调用N次递归了，那么快速排序的效率就会非常低。

三数取中的意思是取数组左边，中间，右边三个数中不是最大也不是最小的那个数，然后返回下标，接着交换这个数和最左边的数即可：

//三数取中
int GetMidIndex(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[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

取中以后只需要在快排函数的最前面交换这个数和最左边的数：

	int index = GetMidIndex(a, left, right);
	Swap(&a[left], &a[index]);
1
2

通过三数取中后，递归后的key就不会在靠近中间的位置，减少了调用次数，提高了效率。

2.3.2.小区间优化

通过这张图不难看出来，当划分的左右子区间的元素个数很小的时候（一般为十几个），需要调用的次数会非常多，这时候使用别的排序算法比如直接插入排序比快速排序更加的高效。

//小区间优化的快速排序
void QuickSort(int* a, int left,int right)
{
	if (left >= right)
	{
		return;
	}
	int keyIndex = PartSort1(a, left, right);
	//排序完成以后，从keyIndex分成三部分
	//[left,keyIndex-1] keyIndex [keyIndex+1,right]
	if (keyIndex - 1 - left > 10)//如果区间范围小于10，则不递归
	{
		QuickSort(a, left, keyIndex - 1);
	}
	else
	{
		InsertSort(a + left, keyIndex - 1 - left + 1);//使用直接插入排序
		//a + left是左区间的起始下标，keyIndex - 1 - left + 1是左区间元素个数
	}
	if (right - (keyIndex + 1)>10)//如果区间范围小于10，则不递归
	{
		QuickSort(a, keyIndex + 1, right);
	}
	else
	{
		InsertSort(a + keyIndex +1, right-(keyIndex +1)+1);//使用直接插入排序
		//a + keyIndex +1是右区间的起始下标，right-(keyIndex +1)+1是右区间元素个数
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

2.4.时间空间复杂度分析

如果没有优化：每次调用都会遍历一次传入的数组，所以调用一次的时间复杂度是O（N），而最好的情况就是key每次都是中间的位置，这样只需要调用log₂N次，而最坏的情况需要调用N次，所以最好的时间复杂度是 O（Nlog₂N），最坏的时间复杂度是O（N²）。
优化后，key一般都会在靠近中间的位置，所以优化后的时间复杂度一般为O（Nlog₂N）
每次递归调用都会开辟空间，所以空间复杂度最好的情况是O（Nlog₂N），最坏的是O（N²）。

平均来看：
时间复杂度为O（NlogN）
空间复杂度为O（NlogN）