题目
设计一个算法可将{4, 2, -3, 6, 1} （或其他乱序的数组）按升序排序得到 {-3, 1, 2, 4, 6}。
解题思路
如果有一沓人民币，怎么按照面额从小到大按顺序排序？
答：每次从这沓人民币中取出面额最小的放到一边，循环往复直到原有的这沓人民币被取完就排序完成了。
同理，我们可以循环遍历题目中的数组A每次将最小的element移动到数组A的左边，等for循环执行完之后数组A就是一个排好序的数组了。
{4, 2, -3, 6, 1} >
-3 { 2, 4, 6, 1} >
-3, 1 { 4, 6, 2} >
-3, 1, 2 { 6, 4} >
-3, 1, 2, 4 {6} >
{-3, 1, 2, 4 6}
Code
public void selectSort(int[] arr){
//corner case: 没有边界值判断的代码是不健壮的
if(arr == null || arr.length <=1){
return;
}
for(int i=0;i<arr.length-1;i++){//为什么是arr.length-1 ?因为最后一个element已经没有其他ele与其比较了
int minIndex = i;
for (int j=minIndex+1;j<arr.length;j++){//为什么j=minIndex+1？因为上次操作之后minIndex+1角标左边的元素已经是sort好的了。
if(arr[j]<arr[minIndex]){
minIndex = j;
}
}
swap2(arr, minIndex, i);
}
}
//交换数组的元素
private void swap1(int[] arr, int index1, int index2){
int temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
//交换数组的元素 实现2，在函数调用次数巨大的情况下可以提高一些效率
private void swap2(int[] arr, int index1, int index2){
if(index1 == index2)return;
arr[index1] = arr[index1] + arr[index2];
arr[index2] = arr[index1] - arr[index2];
arr[index1] = arr[index1] - arr[index2];
}
时空复杂度分析
time complexity:
嵌套for => for循环中的代码执行了n*(n-1)次 = > n^2-n => 去掉对复杂度影响较小的系数 => 时间复杂度为O(n^2)
space complexity:
没有创建多余的数组也没有递归,所以空间复杂度是O(1).
