|
选择排序： 思路： 1、首先拿数组第一个元素依次与除其自身外的其他每个元素顺序比较，如果第一个元素大于剩下的某个元素，就互换内 容。 2、经过第一轮比较之后，此时第一个元素就是数组中最小的元素。然后再拿第二个元素与除第一个元素和其自身的元素 进行比较，如果第二个元素大于剩下的某个元素，就互换内容。 3、依次类推，直到最后一个元素。
具体流程如下图所示：
代码：
public class SelectSort {
public static void main(String[] args) {
int[] arr = { 89, 34, -270, 17, 3, 100 };
System.out.print("排序前数组：");
printArray(arr);
selectSort(arr);
System.out.print("排序后数组：");
printArray(arr);
}
public static void selectSort(int[] arr) {
for (int x = 0; x < arr.length - 1; x++) {
for (int y = x + 1; y < arr.length; y++) {
if (arr[x] > arr[y]) {
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
}
}
}
public static void printArray(int[] arr) {
System.out.print("[");
for (int x = 0; x < arr.length; x++) {
if (x != arr.length - 1)
System.out.print(arr[x] + ",");
else
System.out.println(arr[x] + "]");
}
}
}
上面的选择排序算法效率比较低，因为数组每一个元素与剩下的元素比较就是为了获得最小的元素并且与之互换。例 如：{89,34,-270,17,3,100}这个数组，第一轮就要互换 4 次才能使第一个元素存储的是这个数组中最小的元素。如果是 这样，那么更高效率的方式则是只需要通过两个变量，一个记录最小值，一个记录最小值所在的角标即可。等当前元素 与余下的所有元素比较完，直接互换，这样只需互换一次就能达到目标，效率自然就会提高。
代码：
public class SelectSort2 {
public static void main(String[] args) {
int[] arr = { 89, 34, -270, 17, 3, 100 };
System.out.print("排序前数组：");
printArray(arr);
selectSort(arr);
System.out.print("排序后数组：");
printArray(arr);
}
public static void selectSort(int[] arr) {
for (int x = 0; x < arr.length - 1; x++) {
int num = arr[x];
int index = x;
for (int y = x + 1; y < arr.length; y++) {
if (num > arr[y]) {
num = arr[y];
index = y;
}
} // 如果最小的就是自己，就没有必要执行 swap 操作
if (index != x)
swap(arr, x, index);
}
}
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
public static void printArray(int[] arr) {
System.out.print("[");
for (int x = 0; x < arr.length; x++) {
if (x != arr.length - 1)
System.out.print(arr[x] + ",");
else
System.out.println(arr[x] + "]");
}
}
}
| 
转播
