三、 交换排序 （冒泡排序，快速排序---《hoare版本快排》、挖坑法、前后指针法）

交换排序

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

void BubbleSort(int* a,int n)
{
	for(int i=0;i<n-1;i++)
	{
		for(int j=0;j<n-1-i;j++)	//注意边界为 n-1-i 
		{
			if(a[j]>a[j+1])
			{
				swap(&a[j],&a[j+1]);
			}
		}
	}
 } 
1
2
3
4
5
6
7
8
9
10
11
12
13

冒泡排序的特性总结：

• 冒泡排序是一种非常容易理解的排序
• 时间复杂度：O(N^2)
• 空间复杂度：O(1)
• 稳定性：稳

2.快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右 子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
将区间按照基准值划分为左右两半部分的常见方式有：

1. hoare版本
2. 挖坑法
3. 前后指针版本

上面三种方法我们都会讲解实现一下：
2.1 hoare版本


代码如下：

//三数取中法
int getmid(int* a,int begin,int end)
{
	int mid=(begin+end) >> 1;
	if(a[begin]>a[end])
	{
		if(a[begin]>a[mid])
		{
			if(a[mid]>=a[end])
				return mid;
			else
				return end;
		}
		else
			return begin;
	}
	else if(a[begin]<a[end])
	{
		if(a[end]>a[mid])
		{
			if(a[mid]>=a[begin])
				return mid;
			else
				return begin;
		}
		else
			return end;
	}
	else
		return begin;
}
//快速排序 
//hoare
int PartSort(int* a,int begin,int end)
{
	int tmp=begin;
	int key= a[begin];
	while(begin<end)
	{
		while(begin<end&&a[end]>=key)
		{
			end--;
		}
		while(begin<end&&a[begin]<=key)
		{
			begin++;
		}
	
		swap(&a[begin], &a[end]);
	}
		swap(&a[tmp], &a[begin]);
		return begin;
	
 }
 void Qsort(int* a,int begin,int end)
 {
 	int mid;
 	if(begin<end)
 	{
 		mid=getmid(a,begin,end);
	 	swap(&a[begin],&a[mid]);
	 	mid = PartSort2(a,begin,end);
		Qsort(a,begin,mid-1);
 		Qsort(a,mid+1,end);	
 	}
	
 }
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

2.2 挖坑法
下面这张图示是被人画的，虽然不是很清晰，但是讲的很好，大家可以看图理解。

实现代码如下：

int PartSort2(int* a,int begin,int end)
 {
 	int tmp=a[begin];
 
 	while(begin<end)
 	{
 		while(begin<end&&a[end]>=tmp)
 			end--;
 		if (begin < end)
 		{
 			a[begin]=a[end];
		 }
 		
 		while(begin<end&&a[begin]<=tmp)
 			begin++;
 		if(begin<end)
 		{
 			a[end]=a[begin];
		 }	
	 }
	 a[begin]=tmp;
	 return begin;
  } 
 void Qsort(int* a,int begin,int end)
 {
 	int mid;
 	if(begin<end)
 	{
 		mid=getmid(a,begin,end);
	 	swap(&a[begin],&a[mid]);
	 	mid = PartSort2(a,begin,end);
		Qsort(a,begin,mid-1);
 		Qsort(a,mid+1,end);	
 	}
	
 }
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
36

2.3前后指针版本
看下面的图，理解前后指针法。

分析：
用两个指针prev，cur，cur指向begin，prev=cur-1;
然后判断 若cur的值小于等于基准值，prev++，此时判断：prev==cur？若等于，则cur++，若不等于则先交换两个位置的值，然后cur继续+1。
结束标志：cur>end .此时一prev为界线，序列划分为2部分，对两部分分别递归执行以上操作。
代码实现如下：

int PartSort3(int* a,int begin,int end)
{
	int prev=begin-1;
	int cur=begin;
	int tmp=a[end];
	while(cur<=end)
	{
		if(a[cur]<=tmp)
		{
			prev++;
			if(prev!=cur)
			{
				swap(&a[prev],&a[cur]);
			}
		}
		cur++;
	}
	return prev;
}
 void Qsort(int* a,int begin,int end)
 {
 	int mid;
 	if(begin<end)
 	{
 		mid=getmid(a,begin,end);
	 	swap(&a[begin],&a[mid]);
	 	mid = PartSort3(a,begin,end);
		Qsort(a,begin,mid-1);
 		Qsort(a,mid+1,end);	
 	}
	
 }
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

快速排序的特性总结：

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序 。
2. 时间复杂度：O(N*logN）
3. 空间复杂度：O(logN)
4. 稳定性：不稳定
   关于其他类型的排序算法大家可以看我的博客：
   一、排序 ----- 插入排序（直接插入排序、希尔排序）
   二、选择排序（直接选择排序、堆排序）
   四、归并排序、非比较排序　(归并排序、计数排序)