快速选择排序算法

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
#include <stdio.h> 
#include <stdlib.h> 
#include <iostream>
using namespace std;

 
int partition(int arr[], int low, int high)
{ 

int key; 

 key = arr[low];
// 定义一个变量key，接下来以key的取值为基准将数组A划分为左右两个部分

while(low<high)

{ 


  
 //从high所指向的数组元素开始向左扫描，扫描的同时将下标为high的数组元素依次与划分基准值key进行比较操作;



//直到high不大于low或找到第一个小于基准值key的数组元素，然后将该值赋值给low所指向的数组元素





while
(
low 
<
high 
&&
 arr
[
high
]>=
 key 
)
 



high
--;

 



arr
[
low
]
 
=
 arr
[
high
];
 



//如果low依然小于high，那么由low所指向的数组元素开始向右扫描，扫描的同时将下标为low的数组元素值依次与划分的基准值key进行比较操作;



//直到low不小于high或找到第一个大于基准值key的数组元素，然后将该值赋给high所指向的数组元素。





while
(
 low
<
high 
&&
 arr
[
low
]<=
key 
)
 



low
++;
 



arr
[
high
]
 
=
 arr
[
low
];
 





}
 



//重复步骤(3) (4)，直到low的植不小于high为止，这时成功划分后得到的左右两部分分别为A[low……pos-1]和A[pos+1……high];



//其中，pos下标所对应的数组元素的值就是进行划分的基准值key





arr[low] = key; 



return low; 



}
 

void quick_sort(int arr[], int start, int end)
{ 
 int pos=0; 

 if (start<end)

{ 

pos = partition(arr, start, end); 

quick_sort(arr,start,pos-1); 

quick_sort(arr,pos+1,end); 

} 

return; 
} 


int main(void)
{ 
int i=0; 
int arr[]={32,12,7, 78, 23,45}; 
int N=sizeof(arr)/sizeof(arr[0]);
 
cout<<"排序前,对于数组中元素的输出"<<endl; 
for(i=0;i<N;i++) 
cout<<arr[i]<<endl;

quick_sort(arr,0,N-1); 
cout<<"进行输出排序之后的数组元素"<<endl; 

for(i=0; i<N; i++) 
cout<<arr[i]<<endl; 

system("pause");
 
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
#include <stdio.h>
#include <stdlib.h>
#define N 6
int partition(int arr[], int low, int high){
int key;
key = arr[low];
while(low<high){
while(low <high && arr[high]>= key )
high--;
if(low<high)
arr[low++] = arr[high];
while( low<high && arr[low]<=key )
low++;
if(low<high)
arr[high--] = arr[low];
}
arr[low] = key;
return low;
}
void quick_sort(int arr[], int start, int end){
int pos;
if (start<end){
pos = partition(arr, start, end);
quick_sort(arr,start,pos-1);
quick_sort(arr,pos+1,end);
}
return;
}
int main(void){
int i;
int arr[N]={32,12,7, 78, 23,45};
printf("排序前 n");
for(i=0;i<N;i++)
printf("%dt",arr[i]);
quick_sort(arr,0,N-1);
printf("n 排序后 n");
for(i=0; i<N; i++)
printf("%dt", arr[i]);
printf ("n");
system("pause");
return 0;
}