思想
将序列分为两段,分别为排序序列段和未排序的序列段。每次从未排序的序列段中选出最大或最小关键字放入到有序序列段的尾或头。
与冒泡排序不同的是,简单选择排序在比较过程中不进行交换,而是选择记录一轮中的最大值,最后将这一轮的最大关键字放入有序序列段中。
过程
实现
下文实现以从小到大进行排序
C++代码
从序列头开始遍历,取最小的关键字放入序列头。
外层循环i控制选出关键字操作。i既是操作次数也是已排序序列段的长度。
内层循环j指向要比较的关键字。n-i为未排序序列段的长度。
核心逻辑:从n-i个记录中选出最小值,与i位置进行交换。
#include <iostream>
using namespace std;
void SimpleSelectSorted(int *array,int length);
void Output(int *array,int length);
int main()
{
int *array=new int[10]{2,4,1,5,6,3,9,2,11,7};
SimpleSelectSorted(array,10);
Output(array,10);
system("pause");
return 0;
}
void SimpleSelectSorted(int *array,int length)
{
//简单选择排序思想:从n-i个记录中选出最小值,与i位置进行交换。
int *p=array;
int temp,j;
for (size_t i = 0; i < length-1; i++)//length-1 最后一轮最后一个元素是最小的,不用遍历。
{
int minIndex=i;
for (size_t j = i+1; j < length; j++)//i不用比较
{
if (p[minIndex]>p[j])
{
minIndex=j;
}
}
temp=p[minIndex];
p[minIndex]=p[i];
p[i]=temp;
}
}
void Output(int *array,int length)
{
for (size_t i = 0; i < length; i++)
{
cout<<array[i]<<ends;
}
}
Java代码
java代码与c++类似,这里从序列尾开始遍历,取最大的关键字放入序列尾。
package Test;
import java.util.Scanner;
public class SimpleSelectSort {
public static void main(String args[])
{
System.out.println("输入十个数:");
Scanner scanner=new Scanner(System.in);
int[] array=new int[10];
for (int i = 0; i < 10; i++) {
array[i]=scanner.nextInt();
}
SimpleSelectSorted(array);
Output(array);
}
public static void SimpleSelectSorted(int[] array)
{
int max=0;
int temp=0;
int j;
for (int i = array.length-1; i >=0; i--) {
max=i;
for (j = i; j >=0; j--) {
if (array[j]>array[max]) {
max=j;
}
}
temp=array[i];
array[i]=array[max];
array[max]=temp;
}
}
public static void Output(int[] array)
{
System.out.println("从小到大排序:");
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]+" ");
}
}
}
示例下载