算法一步一步走之选择排序

mac2025-03-22  22

Java-选择排序

排序之选择排序需求

排序之选择排序

选择排序(Selection sort)是一种简单直观的排序算法。 它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素。 存放在序列的起始位置。 然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。 以此类推,直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法.

需求

对一组数组进行排序。 private static int[] array={-9,-8,-111,-1,01,9,3,4,5,16,7,8,9}; 可以看到我们的需求是对这些数字进行排序。 但这里先只对其中的一部分:正数,做排序。 private static int[] arr = {9,8,7,5,6,4,1,9,2,3}; 代码如下: private static int[] arr = {9,8,7,5,6,4,1,9,2,3}; public static void main(String[] args) { int min = 0; for (int i = 0; i < arr.length; i++) { if(min > arr[i]){ min = arr[i]; } } System.out.format("最小的数字为::%d",min); } 最小的数字为::0

那么这里就是有问题的了。 如果我们的数字里不包含0的话,这里始终得不到真正的最小值的。

我们对它进行修改:

private static int[] arr = {9,8,7,5,6,4,1,9,2,3}; public static void main(String[] args) { int min = arr[0]; for (int i = 0; i < arr.length; i++) { if(min > arr[i]){ min = arr[i]; } } System.out.format("最小的数字为::%d\n",min); } 最小的数字为::1

然后,正式进行排序的时候 那么我们正式对这部分数据进行排序,但是排序的时候又出问题了???啥子情况

private static int[] arr = {9,8,7,5,6,4,1,9,2,3}; public static void main(String[] args) { int min = 0; for (int j = 0; j < arr.length; j++) { System.out.format("排序之qian::%s\n", Arrays.toString(arr)); // 数组中的一个数字,记录最小的数字 min = arr[j]; // 最小数字的位置 int index = 0; for (int i = j ; i < arr.length; i++) { if(min > arr[i]){ min = arr[i]; index = i; } } // 交换位置 int temp = arr[index]; arr[index] = arr[j]; arr[j] = temp; System.out.format("最小的数字位置::%d\n",index); System.out.format("Jde 位置::%d\n",j); System.out.format("排序之后::%s\n", Arrays.toString(arr)); System.out.println("----------------"); } } 排序之qian::[9, 8, 7, 5, 6, 4, 1, 9, 2, 3] 最小的数字位置::6 Jde 位置::0 排序之后::[1, 8, 7, 5, 6, 4, 9, 9, 2, 3] ---------------- 排序之qian::[1, 8, 7, 5, 6, 4, 9, 9, 2, 3] 最小的数字位置::8 Jde 位置::1 排序之后::[1, 2, 7, 5, 6, 4, 9, 9, 8, 3] ---------------- 排序之qian::[1, 2, 7, 5, 6, 4, 9, 9, 8, 3] 最小的数字位置::9 Jde 位置::2 排序之后::[1, 2, 3, 5, 6, 4, 9, 9, 8, 7] ---------------- 排序之qian::[1, 2, 3, 5, 6, 4, 9, 9, 8, 7] 最小的数字位置::5 Jde 位置::3 排序之后::[1, 2, 3, 4, 6, 5, 9, 9, 8, 7] ---------------- 排序之qian::[1, 2, 3, 4, 6, 5, 9, 9, 8, 7] 最小的数字位置::5 Jde 位置::4 排序之后::[1, 2, 3, 4, 5, 6, 9, 9, 8, 7] ----------------

排序之qian::[1, 2, 3, 4, 5, 6, 9, 9, 8, 7] 最小的数字位置::0 Jde 位置::5 排序之后::[6, 2, 3, 4, 5, 1, 9, 9, 8, 7] // 这里排序之后,我擦,怎么回事??

---------------- 排序之qian::[6, 2, 3, 4, 5, 1, 9, 9, 8, 7] 最小的数字位置::9 Jde 位置::6 排序之后::[6, 2, 3, 4, 5, 1, 7, 9, 8, 9] ---------------- 排序之qian::[6, 2, 3, 4, 5, 1, 7, 9, 8, 9] 最小的数字位置::8 Jde 位置::7 排序之后::[6, 2, 3, 4, 5, 1, 7, 8, 9, 9] ---------------- 排序之qian::[6, 2, 3, 4, 5, 1, 7, 8, 9, 9] 最小的数字位置::0 Jde 位置::8 排序之后::[9, 2, 3, 4, 5, 1, 7, 8, 6, 9] ---------------- 排序之qian::[9, 2, 3, 4, 5, 1, 7, 8, 6, 9] 最小的数字位置::0 Jde 位置::9 排序之后::[9, 2, 3, 4, 5, 1, 7, 8, 6, 9] ----------------

好吧。发现问题。这之后的时候,不时出现最小数字位置为:0的语句。之后就会和数组的第一位的数字进行交换。 那么我们就观察,发现,index是决定最小数字位置的。在这里会出现几次最小数字位置为0的情况。 如果它是0的话。说明

if(min > arr[i]){ min = arr[i]; index = i; }

这段比较结果为false。index的值是什么呢,还是0,保持不变。 这时候发现

排序之qian::[1, 2, 3, 4, 5, 6, 9, 9, 8, 7] 最小的数字位置::0 Jde 位置::5

如果我们进行比较的话,就是

arr[j];j = 5; // 6 > 6,6 > 9,6 > 9,6 > 8,6 > 7 if(6 > 6){ // 这里的赋值语句永远执行不了 min = arr[i]; index = i; }

经过修改之后,发现我们不知min需要随着j变化而变化,还有index,也需要:修改后的代码如下:

int min = 0; for (int j = 0; j < arr.length; j++) { System.out.format("排序之qian::%s\n", Arrays.toString(arr)); // 数组中的一个数字,记录最小的数字 min = arr[j]; // 最小数字的位置-----这里进行了修改 int index = j; for (int i = j ; i < arr.length; i++) { if(min > arr[i]){ min = arr[i]; index = i; } } // 交换位置 int temp = arr[index]; arr[index] = arr[j]; arr[j] = temp; }

这里修改 index的初始值为 j。应对,如果第一位就是最小数字的情况。 最终的输出结果为:

排序之后::[1, 2, 3, 4, 5, 6, 7, 8, 9, 9]

那到这里,我们的正数排序就完成了。 接下来看看,带负数的排序。

private static int[]array={-9,-8,-111,-1,0,1,9,3,4,5,16,7,8,9};

第一边,直接用原来的方法排序:

排序之后::[-111, -9, -8, -1, 0, 1, 3, 4, 5, 7, 8, 9, 9, 16]

额,一边就好的吗??? 好吧。这次很顺利。之前在家里写遇到了别的问题。具体情况参考 index 的位置。 是min出现了问题。min的值每次都赋值:0。 因为有负数,每次min记录的都是0,在对负数排序之后,在正数中 0 是最小的。所以导致负数之后排序中的数字位置都变成了0。 这里也是这样。只不过换了个形式。 另一边的解决方案是:

if(min > array[i]){ min = array[i]; index = i; } // 记录最大的数值的位置 if(min < array[i]){ max = array[i]; } // 交换位置 // 略 。。。 。。。 // 这里将min的值记录成为最大值。 min = max;

这就是我看选择排序绝当自己实现的经历以及遇到的一些情况。 当然,这里没有遇到负数排序的问题。 这里是自己公司午休的时间写的,遇到的新问题。以及俩个问题之间的总结。相似而不相同。

最新回复(0)