|
题目：对于一个int数组，请编写一个选择排序算法，对数组元素排序。
给定一个int数组A及数组的大小n，请返回排序后的数组。
测试样例：[1,2,3,5,2,3],6 [1,2,2,3,3,5]
思路：这里的选择排序指的是直接选择排序，思路很简单直接。对于n个元素，先从i=0~i=n-1遍历数组找出最小值O(n)，将其与位置0的元素交换，即将其放到位置i=0，然后遍历数组i=1~i=n-1，将其放到位置i=1，依次进行，需要遍历的范围逐渐变小；即本方法是一个2层遍历，外层遍历范围是i=0~i=length-1,内层遍历范围是从j=i~length-1。所谓选择排序是指进行n次选择，每次选择是找出当前范围内的最小值。注意，每次找出最小值后将这个最小值与a[i]进行位置交换将其放到前面有序的位置。即不断对剩余数组进行查找，找出最小值将其与前面的有序序列的后面一个元素进行交换。时间复杂度O(n^2)，空间复杂度O(1)，不稳定。
importjava.util.*;
//选择排序：遍历数组，找出当前排序范围内的最小值，将其放在前面已经排序的序列后面
publicclass SelectionSort {
public int[] selectionSort(int[] A, int n){
//特殊输入
if(A==null||A.length<=0) return A;
//定义一个临时变量表示当前最小值
int curMin=0;
//定义一个临时变量表示当前最小值对应的下标，因为只有遍历到结尾才能知道最小元素，而j是变化的，因此需要记录这个j值
int curMinIndex=0;
//双重循环，外层循环表示当前需要遍历的数组范围
for(int i=0;i<A.length;i++){
//内层循环，从i开始到结尾，逐渐缩小，找到最小值后与A[i]交换
//初始时认为最小值就是第一个元素，于是最小值下标是第一个元素的下标
curMin=A[i];
curMinIndex=i;
for(int j=i+1;j<A.length;j++){
//总是将小的值放到数组的前面
if(A[j]<curMin){
curMin=A[j];
//需要记录当前最小值对应的下标，否则j变化之后仅根据curMinIndex找不到这个元素
curMinIndex=j;
}
}
//内层遍历结束，找到当前范围的最小值，将其与A[i]位置交换
int temp=A[i];
A[i]=A[curMinIndex];
A[curMinIndex]=temp;
}
//千万不要忘记返回结果
return A;
}
} | 
转播
