求大牛解决一个十分基础的算法疑惑~简单选择排序~

Question

public static void selectSort(int[] a) {
for (int k = 0; k < a.length - 1; k++) {
int min = k;
for (int i = k + 1; i < a.length; i++) {
if (a[i] < a[min]) 
min = i;
if(k != min){
int temp = a[k];
a[k] = a[min];
a[min] = temp;
}
}
}
}
这段简单排序的算法我理解感觉有误，请大牛指出哪里理解有误，小纠结中~
a[0] a[1] a[2] a[3] a[4]
初始数组： 5 7 2 6 1

第一次比较
min=k=0,i=1 2 7 5 6 1
此时
min=i=2,k=0
那在接下来的第一次比较的内层循环中由于i++，这样写的话不是变成从a[3]与a[2]比较，照理说不是应该每次都与第一个比较因为第一个总是最小的那个吗否则怎么保证它第一个是最小的那个数呢？

Answer 1

程序有错
if (a[i] < a[min]) 改成 if (a[i] < a[k]) 

Answer 2

给你修改了一下程序, 会打印出每次比较前的数据, 便于理解
import java.util.Arrays;public class Test2 {
public static void main(String[] args) {
int[] ns = { 5, 7, 2, 6, 1 };
System.out.println("Before sorting");
System.out.println(Arrays.toString(ns));
selectSort(ns);
System.out.println("After sorting");
System.out.println(Arrays.toString(ns));
} public static void selectSort(int[] a) {
for (int k = 0; k < a.length - 1; k++) {
int min = k;
for (int i = k + 1; i < a.length; i++) {
if (a[i] < a[min]) {
min = i;
}
} if (k != min) {
int temp = a[k];
a[k] = a[min];
a[min] = temp; System.out.print(Arrays.toString(a));
System.out.println(" min:" + min + ", changing a[" + k + "] and a[" + min + "]");
}
}
}
}输出结果:
Before sorting
[5, 7, 2, 6, 1]
[1, 7, 2, 6, 5] min:4, changing a[0] and a[4] // 找到第k个数后面最小的数与第k个数交换
[1, 2, 7, 6, 5] min:2, changing a[1] and a[2]
[1, 2, 5, 6, 7] min:4, changing a[2] and a[4]
After sorting
[1, 2, 5, 6, 7]

Answer 3

大牛向您这里如果a[0]=5,a[2]=2那么交换后编程a[0]=2,a[2]=5，min=i=2了，那下面不是就是a[3]和a[2]比了吗,实际上不是a[3]继续和a[0]比才对嘛~

Answer 4

我替你精简后的代码，典型的冒泡算法
  public static void selectSort2(int[] a) {
    for (int k = 0; k < a.length - 1; k++) {
      for (int i = k + 1; i < a.length; i++) {
        if (a[i] < a[k]) {
          int temp = a[k];
          a[k] = a[i];
          a[i] = temp;
          System.out.print(Arrays.toString(a));
          System.out.println(" min:" + i + ", changing a[" + k + "] and a[" + i + "]");
        }
      }
    }
  }

Answer 5

public class ArrayTest {
public static void main(String[] args) {
int[] a = new int[] {5, 6, 2, 1, 4, 6, 3, 5, 4, 1};
simpleSelectSort(a);
}
public static void simpleSelectSort(int[] a) {
print(a);
for(int i=0; i<a.length-1; i++) {
System.out.println();
int flag = i+1;
for(int j=i+2; j<a.length; j++) {
if(a[flag] > a[j]) {
flag = j;
}
}
System.out.println();
if(i+1 != flag) {
a[i] = a[i] + a[flag];
a[flag] = a[i] - a[flag];
a[i] = a[i] - a[flag];
System.out.print((i+1) + "\tth sort:a[" + i + "] <--->a[" + flag + "]\t\t");
}else {
System.out.print((i+1) + "\tth sort:No Date change...\t");
}
print(a);
}
}

public static void print(int[] a) {
for(int i=0; i<a.length; i++) {
System.out.print(a[i] + "\t");
}
}

}5 6 2 1 4 6 3 5 4 1 1 th sort:a[0] <--->a[3] 1 6 2 5 4 6 3 5 4 1 2 th sort:a[1] <--->a[9] 1 1 2 5 4 6 3 5 4 6 3 th sort:a[2] <--->a[6] 1 1 3 5 4 6 2 5 4 6 4 th sort:a[3] <--->a[6] 1 1 3 2 4 6 5 5 4 6 5 th sort:a[4] <--->a[8] 1 1 3 2 4 6 5 5 4 6 6 th sort:a[5] <--->a[8] 1 1 3 2 4 4 5 5 6 6 7 th sort:No Date change... 1 1 3 2 4 4 5 5 6 6 8 th sort:No Date change... 1 1 3 2 4 4 5 5 6 6 9 th sort:No Date change... 1 1 3 2 4 4 5 5 6 6
献丑了，O(∩_∩)O~

Answer 6

public static void simpleSelectSort(int[] a) {
print(a);
for(int i=0; i<a.length-1; i++) {
System.out.println();
int flag = i+1;
for(int j=i+1; j<a.length; j++) {
if(a[flag] > a[j]) {
flag = j;
}
}
System.out.println();
if(i+1 != flag && a[i] > a[flag]) {//Modify The Bug Here,O(∩_∩)O~
a[i] = a[i] + a[flag];
a[flag] = a[i] - a[flag];
a[i] = a[i] - a[flag];
System.out.print((i+1) + "\tth sort:a[" + i + "] <--->a[" + flag + "]\t\t");
}else {
System.out.print((i+1) + "\tth sort:No Date change...\t");
}
print(a);
}
}Find Out The Bug...

Answer 7

我试了你提供的程序，有点小问题，做如下修改就OK了
a[min] = temp; 这句后边加上 min = k;最终程序如下import java.util.Arrays;public class Test { public static void selectSort(int[] a) {
for (int k = 0; k < a.length - 1; k++) {
int min = k;
for (int i = k + 1; i < a.length; i++) {
if (a[i] < a[min])
min = i;
if (k != min) {
int temp = a[k];
a[k] = a[min];
a[min] = temp;
min = k;
}
}
}
System.out.println(Arrays.toString(a));
} public static void main(String[] args) {
int a[] = { 2, 10, 6, 9, 3, 11 };
selectSort(a);
}
}