快速选择排序算法

复制纯文本新窗口

#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; 

}

#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;
}