快速排序、二分查找和全排列

实验内容

  • 编程实现快速排序。
  • 编程实现二分查找。
  • 编程实现 输出{1，2，...,n}个数全排列。

我的代码

快速排序

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
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
include irvine32.inc
.data
	arr dd 294,12,9,36,45,645,33,451,33,3,998,231,45
	len dd ($-arr)/4
.code
main proc
	push offset arr
	push len
	call print

	push offset arr
	push 0
	mov eax,len
	dec eax
	push eax
	call quicksort

	push offset arr
	push len
	call print

	exit
main endp

;push offset arr
;push len
;call print
;return nothing
print proc
	push ebp
	mov ebp,esp
	pushad

	mov ebx,[ebp+12]
	mov esi,0
	again:
		cmp esi,[ebp+8]
		jge final
		mov eax,[ebx+4*esi]
		call writeint
		mov al,' '
		call writechar
		inc esi
		jmp again

	final:
	call crlf
	popad
	pop ebp

	ret 8
print endp

;push offset a
;push offset b
;call swap
;return nothing
swap proc
	push ebp
	mov ebp,esp
	pushad

	mov ebx,[ebp+12];ebx=offset a
	mov eax,[ebx]	;tmp=*a
	mov ecx,[ebp+8]	;ecx=offset b
	mov edx,[ecx]
	mov [ebx],edx
	mov [ecx],eax

	popad
	pop ebp
	
	ret 8
swap endp

;push offset a	[ebp+16]
;push low	[ebp+12]
;push high	[ebp+8]
;call partition
;return eax=low
partition proc
	push ebp
	mov ebp,esp
	sub esp,4
	pushad

	mov ebx,[ebp+16];ebx=offset a
	mov esi,[ebp+12];esi=low
	mov edi,[ebp+8] ;edi=high
	mov eax,[ebx+4*esi] ;eax=key=a[low]
	again:
		cmp esi,edi ;low<high
		jge final
		again_1:
			cmp esi,edi
			jge final_1
			cmp [ebx+4*edi],eax ;a[high]<=key?
			jl final_1
			dec edi
			jmp again_1
		final_1:
			;swap(&a[low], &a[high])
			lea edx,[ebx+4*esi]
			push edx
			lea edx,[ebx+4*edi]
			push edx
			call swap

		again_2:
			cmp esi,edi
			jge final_2
			cmp [ebx+4*esi],eax
			jg final_2
			inc esi
			jmp again_2
		final_2:
			lea edx,[ebx+4*esi]
			push edx
			lea edx,[ebx+4*edi]
			push edx
			call swap

		jmp again

	final:
	mov [ebp-4],esi
	popad
	mov eax,[ebp-4]
	add esp,4
	pop ebp

	ret 12
partition endp

;push offset a
;push low
;push high
;call quicksort
;return nothing
quicksort proc
	push ebp
	mov ebp,esp
	pushad

	mov esi,[ebp+12];esi=low
	mov edi,[ebp+8]	;edi=high
	mov ebx,[ebp+16];ebx=offset a
	cmp esi,edi
	jge final
	
	push ebx
	push esi
	push edi
	call partition ;eax=loc
	push ebx
	push esi
	dec eax
	push eax
	call quicksort
	push ebx
	add eax,2
	push eax
	push edi
	call quicksort

	final:
	popad
	pop ebp

	ret 12
quicksort endp

end main

/*
算法代码：
void print(int a[], int n){
	for(int j= 0; j<n; j++){
		cout<<a[j] <<" ";
	}
	cout<<endl;
}

void swap(int *a, int *b){
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int partition(int a[], int low, int high){
	int Key = a[low]; //基准元素
	while(low < high){ //从表的两端交替地向中间扫描
	while(low < high && a[high] >= Key) --high; 
	//从high 所指位置向前搜索，至多到low+1 位置。
	//将比基准元素小的交换到低端
	swap(&a[low], &a[high]);
	while(low < high && a[low] <= Key ) ++low;
	swap(&a[low], &a[high]);
	}
	print(a,10);
	return low;
}

void quickSort(int a[], int low, int high){
	if(low < high){
		int Loc = partition(a, low, high); //将表一分为二
		quickSort(a, low, Loc -1); //递归对低子表递归排序
		quickSort(a, Loc + 1, high); //递归对高子表递归排序
	}
}

int main(){
	int a[10] = {3,1,5,7,2,4,9,6,10,8};
	cout<<"初始值：";
	print(a,10);
	quickSort(a,0,9);
	cout<<"结果：";
	print(a,10);

}
*/

二分查找

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
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
include irvine32.inc
.data
	arr dd 12,4,159,30,74,1,274,33
	len dd ?
	msg db 'key=30在数组中的下标为',0
.code
main proc
	mov len,lengthof arr
	push offset arr
	push len
	call print

	push offset arr
	push 0
	mov eax,len
	dec eax
	push eax
	call quicksort

	push offset arr
	push len
	call print

	push offset arr
	push len
	push 30
	call binsearch
	lea edx,msg
	call writestring
	call writedec
	call crlf

	exit
main endp

;push offset arr
;push lengthof arr
;push key
;call binsearch
;return mid
binsearch proc
	push ebp
	mov ebp,esp
	sub esp,4
	pushad

	mov esi,0	;esi=low
	mov edi,[ebp+12]
	dec edi		;edi=len-1=high
	mov ecx,[ebp+16];ecx=offset arr
	mov edx,-1
	again:
		cmp esi,edi
		jg final
		mov ebx,esi
		add ebx,edi
		shr ebx,1	;ebx=mid

		mov eax,[ebp+8]
		cmp eax,[ecx+ebx*4]
		jz next
		
		L1:
		mov eax,[ebp+8]
		cmp eax,[ecx+ebx*4]
		jl L2
		mov esi,ebx
		inc esi	;low=mid+1
		jmp again

		L2:
		mov edi,ebx
		dec edi	;high=mid-1
		jmp again

		next:
		mov edx,ebx
		jmp final

	final:
	mov [ebp-4],edx
	popad
	mov eax,[ebp-4]
	add esp,4
	pop ebp

	ret 12
binsearch endp

;push offset arr
;push len
;call print
;return nothing
print proc
	push ebp
	mov ebp,esp
	pushad

	mov ebx,[ebp+12]
	mov esi,0
	again:
		cmp esi,[ebp+8]
		jge final
		mov eax,[ebx+4*esi]
		call writeint
		mov al,' '
		call writechar
		inc esi
		jmp again

	final:
	call crlf
	popad
	pop ebp

	ret 8
print endp

;push offset a
;push offset b
;call swap
;return nothing
swap proc
	push ebp
	mov ebp,esp
	pushad

	mov ebx,[ebp+12];ebx=offset a
	mov eax,[ebx]	;tmp=*a
	mov ecx,[ebp+8]	;ecx=offset b
	mov edx,[ecx]
	mov [ebx],edx
	mov [ecx],eax

	popad
	pop ebp
	
	ret 8
swap endp

;push offset a	[ebp+16]
;push low	[ebp+12]
;push high	[ebp+8]
;call partition
;return eax=low
partition proc
	push ebp
	mov ebp,esp
	sub esp,4
	pushad

	mov ebx,[ebp+16];ebx=offset a
	mov esi,[ebp+12];esi=low
	mov edi,[ebp+8] ;edi=high
	mov eax,[ebx+4*esi] ;eax=key=a[low]
	again:
		cmp esi,edi ;low<high
		jge final
		again1:
			cmp esi,edi
			jge final1
			cmp [ebx+4*edi],eax ;a[high]<=key?
			jl final1
			dec edi
			jmp again1
		final1:
			;swap(&a[low], &a[high])
			;push offset a
			lea edx,[ebx+4*esi]
			push edx
			lea edx,[ebx+4*edi]
			push edx
			call swap

		again2:
			cmp esi,edi
			jge final2
			cmp [ebx+4*esi],eax
			jg final2
			inc esi
			jmp again2
		final2:
			lea edx,[ebx+4*esi]
			push edx
			lea edx,[ebx+4*edi]
			push edx
			call swap

		jmp again

	final:
	mov [ebp-4],esi
	popad
	mov eax,[ebp-4]
	add esp,4
	pop ebp

	ret 12
partition endp

;push offset a
;push low
;push high
;call quicksort
;return nothing
quicksort proc
	push ebp
	mov ebp,esp
	pushad

	mov esi,[ebp+12];esi=low
	mov edi,[ebp+8]	;edi=high
	mov ebx,[ebp+16];ebx=offset a
	cmp esi,edi
	jge final
	
	push ebx
	push esi
	push edi
	call partition ;eax=loc
	push ebx
	push esi
	dec eax
	push eax
	call quicksort
	push ebx
	add eax,2
	push eax
	push edi
	call quicksort

	final:
	popad
	pop ebp

	ret 12
quicksort endp

end main

/*
二分查找:
把数据分成两半，再判断所查找的key在哪一半中，
再重复上述步骤知道找到目标key;
#include<stdio.h>
int BinSearch(int arr[],int len,int key){ //二分法
 int low=0;        //定义初始最小
 int high=len-1;   //定义初始最大
 int mid;              //定义中间值
 while(low<=high) {
	mid=(low+high)/2;  //找中间值
	if(key==arr[mid]) //判断min与key是否相等
		return mid;  
	else if(key>arr[mid]) //如果key>mid 则新区间为[mid+1,high]
		low=mid+1;
	else                //如果key<mid 则新区间为[low,mid-1]
		high=mid-1;
 }
 return -1;         //如果数组中无目标值key，则返回 -1 ；
}

int main(){
 int arr[]={1,2,3,4,5,6,7,8,9,10,11};   //首先要对数组arr进行排序
 printf("%d \n",BnSearch(arr,(sizeof(arr)/sizeof(arr[0])),7));
 return 0;
}
*/

全排列

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
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
include irvine32.inc
.data
	arr dd 100 dup(?)
	msg1 db '请输入一个小于10的正整数:',0
	msg2 db '全排列如下：',0
	len dd ?
.code
main proc
	lea edx,msg1
	call writestring
	call crlf
	call readint
	mov len,eax
	push offset arr
	push len
	call creatarr

	push offset arr
	push len
	call print
	lea edx,msg2
	call writestring
	call crlf

	push offset arr
	push 0
	push len
	call fullpermutation

	ret
main endp

;push offset arr
;push len
;call creactarr
;retrun nothing
creatarr proc
	push ebp
	mov ebp,esp
	pushad

	mov edi,[ebp+12];edi=offset arr
	mov ecx,[ebp+8]	;ecx=len
	mov esi,0
	again:
		cmp esi,ecx
		jge final
		mov ebx,esi
		inc ebx
		mov [edi+esi*4],ebx
		inc esi
		jmp again

	final:
	popad
	pop ebp

	ret 8
creatarr endp

;push offset arr
;push begin
;push end
;call fullpermutation
;return nothing
fullpermutation proc
	push ebp
	mov ebp,esp
	pushad

	mov ebx,[ebp+12];ebx=begin
	mov ecx,[ebp+8]	;ecx=end
	mov edi,[ebp+16];edi=offset arr

	mov esi,ebx	;i=begin
	cmp ebx,ecx
	jl again

	push edi
	push ecx
	call print
	
	again:
		cmp esi,ecx
		jge final

		cmp ebx,esi
		jz next
		
		push edx
		lea edx,[edi+ebx*4]
		push edx
		lea edx,[edi+esi*4]
		push edx
		call swap
		pop edx

		next:
		push edi
		mov eax,ebx
		inc eax
		push eax
		push ecx
		call fullpermutation

		cmp ebx,esi
		jz L
		push edx
		lea edx,[edi+ebx*4]
		push edx
		lea edx,[edi+esi*4]
		push edx
		call swap
		pop edx
		
		L:
		inc esi
		jmp again

	final:
	popad
	pop ebp

	ret 12
fullpermutation endp

;push offset arr
;push len
;call print
;return nothing
print proc
	push ebp
	mov ebp,esp
	pushad

	mov ebx,[ebp+12]
	mov esi,0
	again:
		cmp esi,[ebp+8]
		jge final
		mov eax,[ebx+4*esi]
		call writedec
		mov al,' '
		call writechar
		inc esi
		jmp again

	final:
	call crlf
	popad
	pop ebp

	ret 8
print endp

;push offset a
;push offset b
;call swap
;return nothing
swap proc
	push ebp
	mov ebp,esp
	pushad

	mov ebx,[ebp+12];ebx=offset a
	mov eax,[ebx]	;tmp=*a
	mov ecx,[ebp+8]	;ecx=offset b
	mov edx,[ecx]
	mov [ebx],edx
	mov [ecx],eax

	popad
	pop ebp
	
	ret 8
swap endp

end main

/*
全排列算法
主要思路：
1.把第1个数换到最前面来（本来就在最前面），准备打印1xx，再对后两个数2和3做全排列。
2.把第2个数换到最前面来，准备打印2xx，再对后两个数1和3做全排列。
3.把第3个数换到最前面来，准备打印3xx，再对后两个数1和2做全排列。
这是一个递归的过程，把对整个序列做全排列的问题归结为对它的子序列做全排列的问题


include <stdio.h>
void Swap(int *lhs, int *rhs){
	int t = *lhs;
	*lhs = *rhs;
	*rhs = t;
}
*/
/************************************************************************/
/* 功能：实现全排列功能
/* 参数：
/*       source--整数数组，存放需要全排列的元素
/*       begin --查找一个排列的开始位置
/*       end   --查找一个排列的结束位置，当begin=end时，表明完成一个排列
/************************************************************************/
/*
void FullPermutation(int source[], int begin, int end){
	int i;
	if (begin >= end){ // 找到一个排列
		for(i = 0; i < end; i++){
		    printf("%d", source[i]);
		}
		printf("\n");
	}
	else{ // 没有找完一个排列，则继续往下找下一个元素
		for (i = begin; i < end; i++){
		    if (begin != i){
			Swap(&source[begin], &source[i]); // 交换
		    }
		    // 递归排列剩余的从begin+1到end的元素
		    FullPermutation(source, begin + 1, end);

		    if (begin != i){
			Swap(&source[begin], &source[i]); // 回溯时还原
		    } 
		}
	   }
}

int main( ){
	int source[30];
	int i, count;
	scanf("%d", &count);
	for (i = 0; i < count; i++){
		source[i] = i + 1;
	}
	FullPermutation(source, 0, count);
	return 0;
}
*/

补充文件