选择排序

选择排序

简单选择排序 要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。二元选择排序 简单选择排序，每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可 代码示例： /* 选择排序算法 */ #include<iostream> #include<cstdio> #define maxn 1000 using namespace std; void select_sort1(int *a,int n); void select_sort2(int *a,int n); void output(int *a,int n); int selectminkey(int *a,int n,int i); int main(void) { int n,m; cin>>n; int a[maxn],b[maxn]; for(int i=0; i<n; i++) { cin>>a[i]; } select_sort1(a,n); cout<<endl<<endl<<endl; cin>>m; for(int i=0; i<m; i++) { cin>>b[i]; } select_sort2(b,m); return 0; } void output(int *a,int n) { for(int i=0; i<n; i++) { cout<<a[i]<<" "; } cout<<endl; } int selectminkey(int *a,int n,int i) { int k=i; for(int j=i+1; j<n; j++) { if(a[k]>a[j]) { k=j; } } return k; } void select_sort1(int *a,int n) { int key,temp; for(int i=0; i<n; i++) { key=selectminkey(a,n,i); if(key!=i) { temp=a[i]; a[i]=a[key]; a[key]=temp; } output(a,n); } } void select_sort2(int r[],int n) { int i ,j , min ,max, tmp; for (i=0 ; i < n/2; i++) { // 做不超过n/2趟选择排序 min = i; max = i ; //分别记录最大和最小关键字记录位置 for (j= i+1; j<n-i; j++) { if (r[j] > r[max]) { max = j ; continue ; } if (r[j]< r[min]) { min = j ; } } //该交换操作还可分情况讨论以提高效率 tmp = r[i]; r[i] = r[min]; r[min] = tmp; tmp = r[n-i-1]; r[n-i-1] = r[max]; r[max] = tmp; output(r,n); } }