交换排序

发表于

标题：交换排序

冒泡排序（Bubble Sort）：是一种计算机科学领域的较简单的排序算法。

算法描述：它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。

  • 这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

冒泡排序算法步骤如下：

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

冒泡排序复杂度问题：

  • 冒泡排序最好情况时间复杂度O(n)，冒泡排序最坏情况下时间复杂度O(n^2) 冒泡排序空间复杂度O(1) 冒泡排序是一种稳定的排序算法

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//冒泡排序
//使用flag作为标记,当flag为1时,证明数组已将为有序数组,直接可以跳出循环
void BubbleSort(int *a, int len)
{
	assert(a);
	int flag = 0;
	for (int i = 0; i < len - 1; i++){
		flag = 1;
		for (int j = 0; j < len - i - 1; j++){
                        //比较是否需要交换
			if (a[j] > a[j+1]){
				Swap(&a[j], &a[j + 1]);
				flag = 0;
			}
		}
		//如果数组已经有序则直接跳出循环
		if (flag)
			break;
	}
}

快速排序

算法描述：快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据以一个枢纽div 分割成独立的两部分，其中左半部分的所有数据都比div要小,右半部分的所有数据都比div要大，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

递归实现：

1
2
3
4
5
6
7
8
9
10
11
12
//快速排序
void QuickSort(int *a, int left, int right){
	if (left >= right)
		return;
	assert(a);
	//按照基准经left和right标记区间划分成两个部分
	int div = PartionOne(a, left, right);
	//排列左半部分
	QuickSort(a, left, div - 1);
	//排列右半部分
	QuickSort(a, div + 1, right);
}
Partion()为进行一次库快速排序的算法, 常见的方法有 左右指针法 , 挖坑法 , 前后指针法

左右指针法:

  1. 这里选取数组中最后一个数( 第一个数 )作为关键字key
  2. 设置两个变量begin和end分别数组的起始和结束下标
  3. begin从前往后, 当找到一个比key大的值时, right从后往前走, 当找到一个比key小的值时, 将其交换
  4. 继续重复上述步骤, 直到begin和end相遇, 再将key记录的数放到begin的位置, 并且返回begin

  • 如上图所示 , 当begin>=end时, 一趟快速排序就完成了, 并在最后将key和begin的值进行交换,结 果就为 16 25 25 34 58 49
代码实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//(左右指针法)寻找一个枢轴作为记录
int PartionOne(int *a, int begin, int end)
{
	//选取序列的末尾作为关键字
	int key = a[end];
        //index用来记录关键字所在的下标
	int index = end;
	//保证key的左边都小于key,右边都大于key
	while (begin < end){
		//从左向右寻找比key大的数
		while (begin < end && a[begin] <= key)
			begin++;
		//从右向左寻找比key小的数
		while (begin < end && a[end] >= key)
			end--;
		//交换
		Swap(&a[begin], &a[end]);
	}
	Swap(&a[begin], &a[index]);
	return begin;
}

挖坑法：

  1. 这里选取数组中最后一个数( 第一个数 )作为关键字key, 也为初始坑位
  2. 设置两个变量begin和end分别数组的起始和结束下标
  3. begin从前往后, 当找到一个比key大的值时, 将该数放到坑中, 这时的坑位就变作begin
  4. right从后往前走, 当找到一个比key小的值时, 将该数放到坑中, 这时的坑位就变作end
  5. 重复上述步骤直到begin和end相遇, 在将key放入到最后一个坑位

  • 当begin>=end时, 将key放到最后一个坑中, 就完成了一次排序
代码实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//挖坑法
int PartionTwo(int *a, int begin, int end)
{
	//key为关键字,记录第一个坑里边的数据
	int key = a[end];
	while (begin < end){
		while (begin < end && a[begin] <= key)
			begin++;
		a[end] = a[begin];
		while (begin < end && a[end] >= key)
			end--;
		a[begin] = a[end];
	}
	a[begin] = key;
	return begin;
}

前后指针法:

  1. 定义一个变量next指向序列的起始位置, 定义一个变量prev指向next的前一个位置
  2. 当a[next]>key时, next不断向前走, 当a[next]<key时且prev和next相邻时, next和prev同时向前走
  3. 当a[next]<key且prev和next不相邻时, 将交换a[next]和a[prev]进行交换

代码实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//前后指针法
int PrationThree(int *a, int begin, int end)
{
	assert(a);
	if (begin >= end)
		return -1;
	int key = a[end];
	int prev = begin - 1;
	int next = begin;
	while (next < end){
		//如果找到小于key的值，并且nxet和prev不相邻时进行交换。注意两个条件的先后位置不能更换
		if (a[next] < key && ++prev != next)
			Swap(&a[prev], &a[next]);
		next++;
	}
	//注意:prev记得+1
	Swap(&a[end], &a[++prev]);
	return prev;
}

快速排序的优化：

  1. 三数取中法 : 当所要排序的数组本身就是正序或者逆序时, 这样我们每次挑选的枢纽并没有起到划分的作用, 这是快速排序的效率会减低很多, 所以这里可以可以每次从起始位置, 中间位置和结束位置当中挑选出中间值, 将这个中间值和key交换, 这样就会使得每次划分接近于均等, 效率会提高不少
  2. 小区间法优化 (直接插入) : 当要排序的序列比较少时,为了避免开辟过多栈帧,使用插入排序来提高快速排序的效率

叮，传送门–>插入排序实现

代码如下：
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
68
69
70
71
//三数取中法
int GetMid(int *a, int left, int right)
{
	assert(a);
	int mid = left + ((right - left) >> 2);
	if (a[left] <= a[right]){
		if (a[mid] < a[left])
			return left;
		else if (a[mid]>a[right])
			return right;
		else
			return mid;
	}
	else{
		if (a[mid] > a[left])
			return left;
		else if (a[mid] < a[right])
			return right;
		else
			return mid;
	}
}
//(左右指针法)寻找一个枢轴作为记录
int PartionOne(int *a, int begin, int end)
{
    //mid用获取起始,中间和结束位置中的中间值
	//选取序列的末尾作为关键字
	int mid = GetMid(a, begin, end);
	Swap(&a[mid], &a[end]);
	int key = a[end];
	int index = end;
	//保证key的左边都小于key,右边都大于key
	while (begin < end){
		//从左向右寻找比key大的数
		while (begin < end && a[begin] <= key)
			begin++;
		//从右向左寻找比key小的数
		while (begin < end && a[end] >= key)
			end--;
		//交换
		Swap(&a[begin], &a[end]);
	}
	Swap(&a[begin], &a[index]);
	return begin;
}
//快速排序(小区间优化)
void QuickSortTwo(int *a, int left, int right){
	if (left >= right)
		return;
	assert(a);
	//当要排序的序列比较少时,为了避免开辟过多栈帧,使用插入排序
	if (right - left <= 3){
		for (int i = 0; i < right-1; i++){
			int index = i + 1;
			int cur = a[index];
			if (a[i]>a[index]){
				while (index > 0 && cur > a[index + 1]){
					a[index + 1] = a[index];
					++index;
				}
			}
			a[index] = cur;
		}
	}
	//按照基准经left和right标记区间划分成两个部分
	int div = PrationOne(a, left, right);
	//排列左半部分
	QuickSort(a, left, div - 1);
	//排列右半部分
	QuickSort(a, div + 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
//快速排序(非递归)使用栈来存放下标区间
void QuickSortRecNone(int *a, int left, int right){
	if (left >= right)
		return;
	assert(a);
	Stack s;
	StackInit(&s);
	StackPush(&s, left);
	StackPush(&s, right);
	while (StackEmpty(&s) != 0){
		int end = StackTop(&s);
		StackPop(&s);
		int begin = StackTop(&s);
		StackPop(&s);
		int div = PartionOne(a, begin, end);
		//将左右区间分别压栈
		if (begin < div - 1){
			StackPush(&s, begin);
			StackPush(&s, div - 1);
		}
		if (end > div + 1){
			StackPush(&s, div + 1);
			StackPush(&s, 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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
 #include <stdio.h>
 #include <stdlib.h>
 #include <assert.h>
 #include <time.h>
 #include <string.h>
 //栈的头文件
 #include "Stack.h"
//交换数据
void Swap(int *m, int *n)
{
	int tmp = *m;
	*m = *n;
	*n = tmp;
}
//三数取中法
int GetMid(int *a, int left, int right)
{
	assert(a);
	int mid = left + ((right - left) >> 2);
	if (a[left] <= a[right]){
		if (a[mid] < a[left])
			return left;
		else if (a[mid]>a[right])
			return right;
		else
			return mid;
	}
	else{
		if (a[mid] > a[left])
			return left;
		else if (a[mid] < a[right])
			return right;
		else
			return mid;
	}
}
//(左右指针法)寻找一个枢轴作为记录
int PartionOne(int *a, int begin, int end)
{
	//选取序列的末尾作为关键字
	int mid = GetMid(a, begin, end);
	Swap(&a[mid], &a[end]);
	int key = a[end];
	int index = end;
	//保证key的左边都小于key,右边都大于key
	while (begin < end){
		//从左向右寻找比key大的数
		while (begin < end && a[begin] <= key)
			begin++;
		//从右向左寻找比key小的数
		while (begin < end && a[end] >= key)
			end--;
		//交换
		Swap(&a[begin], &a[end]);
	}
	Swap(&a[begin], &a[index]);
	return begin;
}
//挖坑法
int PartionTwo(int *a, int begin, int end)
{
	//key为关键字,记录第一个坑里边的数据
	int key = a[end];
	while (begin < end){
		while (begin < end && a[begin] <= key)
			begin++;
		a[end] = a[begin];
		while (begin < end && a[end] >= key)
			end--;
		a[begin] = a[end];
	}
	a[begin] = key;
	return begin;
}
//前后指针法
int PrationThree(int *a, int begin, int end)
{
	assert(a);
	if (begin >= end)
		return -1;
	int key = a[end];
	int prev = begin - 1;
	int next = begin;
	while (next < end){
		//如果找到小于key的值，并且nxet和prev不相邻时进行交换。注意两个条件的先后位置不能更换
		if (a[next] < key && ++prev != next)
			Swap(&a[prev], &a[next]);
		next++;
	}
	//注意:prev记得+1
	Swap(&a[end], &a[++prev]);
	return prev;
}
//快速排序
void QuickSort(int *a, int left, int right){
	if (left >= right)
		return;
	assert(a);
	//按照基准经left和right标记区间划分成两个部分
	int div = PartionOne(a, left, right);
	//int div = PartionTwo(a, left, right);
	//int div = PrationThree(a, left, right);
	//排列左半部分
	QuickSort(a, left, div - 1);
	//排列右半部分
	QuickSort(a, div + 1, right);
}
//快速排序(小区间优化)
void QuickSortTwo(int *a, int left, int right){
	if (left >= right)
		return;
	assert(a);
	//当要排序的序列比较少时,为了避免开辟过多栈帧,使用插入排序
	if (right - left <= 3){
		for (int i = 0; i < right-1; i++){
			int index = i + 1;
			int cur = a[index];
			if (a[i]>a[index]){
				while (index > 0 && cur > a[index + 1]){
					a[index + 1] = a[index];
					++index;
				}
			}
			a[index] = cur;
		}
	}
	//按照基准经left和right标记区间划分成两个部分
	//int div = PartionOne(a, left, right);
	//int div = PartionTwo(a, left, right);
	int div = PrationThree(a, left, right);
	//排列左半部分
	QuickSort(a, left, div - 1);
	//排列右半部分
	QuickSort(a, div + 1, right);
}
//快速排序(非递归)使用栈来存放下标区间
void QuickSortRecNone(int *a, int left, int right){
	if (left >= right)
		return;
	assert(a);
	Stack s;
	StackInit(&s);
	StackPush(&s, left);
	StackPush(&s, right);
	while (StackEmpty(&s) != 0){
		int end = StackTop(&s);
		StackPop(&s);
		int begin = StackTop(&s);
		StackPop(&s);
		int div = PartionOne(a, begin, end);
		//将左右区间分别压栈
		if (begin < div - 1){
			StackPush(&s, begin);
			StackPush(&s, div - 1);
		}
		if(end > div + 1){
			StackPush(&s, div + 1);
			StackPush(&s, end);
		}
	}
}
//打印数组
void PrintArray(int *a, int len)
{
	assert(a);
	for (int i = 0; i < len; i++)
		printf("%d ", a[i]);
	printf("\n");
}
int main()
{
	int a[] = { 58, 25, 49, 25, 16, 34 };
	QuickSort(a, 0, sizeof(a) / sizeof(int)-1);
	//QuickSortTwo(a, 0, sizeof(a) / sizeof(int)-1);
	//QuickSortRecNone(a, 0, sizeof(a) / sizeof(int)-1)0;
	PrintArray(a, sizeof(a) / sizeof(int));
	system("pause");
	return 0;
}