Posted on 2009-03-26 11:16
赞劲小子 阅读(331)
评论(0) 编辑 收藏 引用 所属分类:
算法设计与分析
直接选择排序的基本思想 n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：
①初始状态：无序区为R[1..n]，有序区为空。
②第1趟排序
在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
……
③第i趟排序
第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R[i]交换，使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。
#include "iostream.h"
void selectionSort(int array[], const int size);
int main(){
const int size = 10;
int array[size] = {3,5,1,8,7,4,2,9,6,10};
selectionSort(array,size);
for(int i = 0; i < size; i++){
cout << array[i] << " ";
}
return 0;
}
void selectionSort(int array[], const int size){
int min; // 最小值的位置
int pass,j; //循环控制
int temp;
for(pass = 0; pass < size - 1; pass++){
min = pass;
for(j = pass + 1; j < size; j++){
if(array[j] < array[min])
min = j;
}
if(min != pass){
temp = array[pass];
array[pass] = array[min];
array[min] = temp;
}
}
}