一、选择排序的基本思想：
首先，找到数组中最小的元素，其次将它和数组第一个元素交换位置（如果第一个元素就是最小元素则和自己交换），然后在剩下的元素中找到最小的元素，将它与数组第二个元素交换位置。如此循环，直到将整个数组排序。这种方法叫做选择排序。
对于长度为N的数组，选择排序需要大约N^2/2次比较和N次交换
C++代码实现：
#include<iostream>
using namespace std;
template<typename T>
void selectionSort(T a[],int N) {
for (int i = 0; i < N; i++) {
int min = i;
for (int j = i + 1; j < N; j++)
if (a[min] > a[j])
min = j;
swap(a[i],a[min]);
}
}
int main() {
int arr[10] = { 10,5,2,6,3,4,7,9,8,1 };
selectionSort(arr,10);
for (int i = 0; i < 10; i++)
cout << arr[i] << " ";
cout << endl;
system("pause");
}
Java代码实现：
package selectionsort;
public class SelectionSort {
public static void selectionSort(Comparable[] a){
int N=a.length;
for(int i=0;i<N;i++){
int min=i;
for(int j=i+1;j<N;j++)
if(less(a[j],a[min]))
min=j;
exch(a,i,min);
}
}
private static boolean less(Comparable v,Comparable w){
return v.compareTo(w)<0;
}
private static void exch(Comparable[] a,int i,int j){
Comparable t=a[i];a[i]=a[j];a[j]=t;
}
public static void main(String[] args) {
Integer[] arr = {4,7,8,3,9,5,6,1,2};
SelectionSort.selectionSort(arr);
for( int i = 0 ; i <arr.length ; i ++ ){
System.out.print(arr[i]);
System.out.print(' ');
}
}
}
二、常见错误
问题描述：运行完程序后发现第一个元素与第二个元素没有排好序。如下图
解决：对于代码selectionSort方法中，if判断语句不要嵌套进第二个for循环中。
因为第二个for循环是为了寻找与i交换位置的元素，要循环找到后，才能判断它与i的大小关系。