算法之4选择排序

2.4.1 算法思路

此方法为暴力求解，在此非重点。
首先选择第一个元素，初始化minIndex=0，然后从第二个元素开始从左往右遍历，找出右边比sortedData[minIndex]更小的元素，就将其序号赋值给minIndex，遍历完右边的所有元素后，交换第i个元素和第minIndex元素。
然后选择第二个元素，从第三个元素开始从左往右遍历，其余步骤同上。

2.4.2 代码实现

public static int[] selectionSort(int[] originalData){
	int [] sortedData=originalData.clone();//复制一份原始数据，用来保存排序好的数组
	/*核心代码*/
	//注意：这里i取到sortedData.length-2就能保证排序好
	for(int i=0;i<sortedData.length-1;i++){
		int minIndex=i;
		for(int j=i+1;j<sortedData.length;j++){//j必须遍历到最后一位
			if(sortedData[minIndex]>sortedDate[j]){//如果大于最小值，则将索引保存到minIndex
				minIndex=j;
			}
		}
		swap(sortedData,i,minIndex);//将i和minIndex的元素交换
	}
	return sortedData;
}

2.4.3 时间复杂度

时间复杂度：Θ(n²)
分析：(n-1)+(n-2)+(n-3)+….1=n(n-1)/2