选择排序法的思路及C语言程序代码.doc

(完整word)选择排序法的思路及C语言程序代码
选择排序法
选择排序法是从算法优化的角度对冒泡法的改进,其改进的思想是:经过一轮的两两比较后，并不马上交换数的位置，而是找到本轮最小的数,记下该数的位置（即在数组中的下标），待本轮比较完毕后,通过一次交换即可将本轮最小的数交换到位。
示例详解
假设数组a的5个元素依次为：9、10、8、7、6。下图说明了选择排序法的操作过程:
第一轮比较：
k=0
第一次比较： 9 10 8 7 6 比较a［0］和a[1］, a［0]〈a［1］，k=0
第二次比较: 9 10 8 7 6 比较a［0］和a［2］， a[0]>a［2],k=2
第三次比较： 9 8 10 7 6 比较a［2］和a[3］， a［2］〉a[3］,k=3
第四次比较: 9 8 7 10 6 比较a［3］和a[4], a［3]〉a［4],k=4
第一次交换前：9 8 7 10 6 将a[4］和a［0］进行交换
第一次交换后：6 8 7 10 9 这样，最小的元素就放到了数组最前面的位置
第二轮比较：
k=1
第一次比较： 6 8 7 10 9 比较a[1］和a［2], a[1］〉a［2],k=2
第二次比较： 6 8 7 10 9 比较a[2］和a[3]， a［2]〈a[3],k=2
第三次比较： 6 8 7 10 9 比较a［2］和a[4］, a[2]<a[3]，k=2
第二次交换前：6 8 7 10 9 将a[2］和a［1］进行交换
第二次交换后：6 7 8 10 9
第三轮比较：
k=2
第一次比较: 6 7 8 10 9 比较a［2]和a［3]， a[2]〈a[3]，k=2
第二次比较： 6 7 8 10 9 比较a［2]和a[4］， a[2］<a［4]，k=2
k的值没变,本轮不需要交换
第四轮比较:
k=3
第一次比较： 6 7 8 10 9 比较a[3]和a[4］, a［3]〉a[4]，k=4
第三次交换前：6 7 8 10 9 将a[3］和a［4]进行交换
第三次交换后:6 7 8 9 10
用选择排序法将数组a[13］={2，5，13,1，10，6，3,4,12,8,11,9，7}中的元素从小到大排序后输出，编写的C++程序代码如下：
#include〈iostream>
＃define N 13
using namespace std;
void main(）
｛
float a［]={2，5,13，1,10,6,3，4,12,8,11，9,7｝；
for（int i=0;i<=N—2；i++)
{
int k=i;
for(int j=i+1；j〈=N—1;j++）
if(a[k]〉a[j］)
k=j； //交换标号
if(k!=i）
{
float temp=a[k］; //交换a［k］和a[i]
a[k]=a[i］；
a［i］=temp；
}
}
for（i=0；i<=N—1;i++） cout〈〈a［i]〈<" ”；
cout<<endl；
}
程序运行结果如下：