设所排序序列的记录个数为ｎ。i取1,2,…,n-1,从所有n-i+1个记录（R,Ri+1,…,Rn中找出排序码最小的记录，与第ｉ个记录交换。执行n-1趟 后就完成了记录序列的排序。

简单选择排序算法分析

实现(Java实现)

C源码

简单选择排序算法分析

在简单选择排序过程中，所需移动记录的次数比较少。最好情况下，即待排序记录初始状态就已经是正序排列了，则不需要移动记录。

最坏情况下，即待排序记录初始状态是按逆序排列的，则需要移动记录的次数最多为3（n-1）。简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。当i=1时，需进行n-1次比较；当i=2时，需进行n-2次比较；依次类推，共需要进行的比较次数是(n-1)+(n-2)+…+2+1=n(n-1)/2，即进行比较操作的时间复杂度为 O(n^2)。

简单选择排序是不稳定排序。

实现

用C++描述算法如下：

template <class datatype >

void seqlist <datatype > ∷insertsort( )

{int i ,j,k;

datatype temp;

for(i =1;i<last;i++ )

{

k=i;

for(j=i+1;j<=last;j++)if(data[j]<data[k])k=j;

if(i!=k) //第i个元素与第k个元素交换

{

temp=data[k];

data[k]=data[i];

data[i]=temp;

}

}

delete_ data(1);

};

数据结构课本上算法：

void Select_Sort（datatype R[ ],int n)

{/*对排序表R[1].....R[n]进行冒泡排法，n是记录个数*/

for(i=1;i<n;i++) /*做n-1趟选取*/

{k=i; /*在i开始的n-i+1个记录中选关键码最小的记录*/

for(j=i+1;j<=n;j++)

if(R[j].key<r[k].key)k=j; /*k中存放关键码最小记录的下标*/

if(i!=k) /*关键码最小的记录与第i个记录交换*/

{R[0]=R[k];

R[k]=R[i];

R[i]= R[0]；

}

}

}

Java实现

public class SimpleSort {

public static void sort(Comparable[] data) {

// 数组长度

int len = data.length;

for (int i = 0; i < len; i++) {

// 记录当前位置

int position = i;

// 找出最小的数，并用position指向最小数的位置

for (int j = i + 1; j < len; j++) {

if (data[position].compareTo(data[j]) > 0) {

position = j;

}// end if

}// end for

// 交换最小数data[position]和第i位数的位置

Comparable temp = data[i];

data[i] = data[position];

data[position] = temp;

}// end for

}// end sort

public static void main(String[] args) {

// 在JDK1.5版本以上,基本数据类型可以自动装箱

// int,double等基本类型的包装类已实现了Comparable接口

Comparable[] c = { 4, 9, 23, 1, 45, 27, 5, 2 };

sort(c);

for (Comparable data : c) {

System.out.println(data);

}

}

}

C源码

简单选择排序算法原理：每次从右至左扫描序列，记下最小值的位置。--------------------------------------c语言实现-----------------------------------

#include<stdio.h>

void main(){

int r[5]={5,4,3,2,1};

int i,j,k,tmp;

printf("Before selecting sort:");

for(i=0;i<5;i++)

printf("%-3d",r[i]);

printf("\");

for(i=1;i<5;i++){

k=5-1;//先假设序列最后一个数为最小值，记下此刻位置

for(j=k-1;j>=i-1;j--){//自右向左扫描

if(r[j]<r[k])

k=j;

}

if(k!=i-1){//如果最小值不是无序列（排序后）第一个元素

tmp=r[i-1];

r[i-1]=r[k];

r[k]=tmp;

}

}

printf("After selecting sort:");

for(i=0;i<5;i++)

printf("%-3d",r[i]);

printf("\");

}

--------------------------------------c语言实现-----------------------------------