javaidea选择排序,每次遍历找到最大值和最小值,最大值放在最右边,最小值放在最左边,拥有begin,end,min,max四个下标
选择排序每次循环都要找出最大值最小值,每次两次交换,我用了自己写的一个类里的方法交换数据
,这个交换方法写成通过第三者交换是可以让算法成功执行的.我用的对数器大数据量下检测出来的
public class SelectSort {
public static void selectsort(int[] arr) {
Swap s = new Swap();
/*初始化左端、右端元素索引*/
int left = 0;
int right = arr.length - 1;
while (left < right) {
/*初始化最小值、最大值元素的索引*/
int min = left;
int max = right;
for (int i = left; i <= right; i++) {
/*标记每趟比较中最大值和最小值的元素对应的索引min、max*/
if (arr[i] < arr[min]) {
min = i;
}
if (arr[i] > arr[max]) {
max = i;
}
}
/*最大值放在最右端*/
s.swap(arr, right, max);
/*此处是先排最大值的位置,所以得考虑最小值(arr[min])在最大位置(right)的情况*/
if (min == right) {
min = max;
}
/*最小值放在最左端*/
s.swap(arr, left, min);
/*每趟遍历,元素总个数减少2,左右端各减少1,left和right索引分别向内移动1*/
left++;
right--;
}
}
}
交换类
public class Swap {
public void swap(int[]arr,int i,int j) {
/* arr[i] = arr[i] + arr[j];
arr[j] = arr[i] - arr[j];
arr[i] = arr[i] - arr[j];*/
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
也就是说,交换类中被注释掉的这种交换方法,我只能用一次才能保证算法的正确,两次就会使算法出错,编译,运行可以成功,就是算法排序不正确.不被注释掉的部分是可以用的,用两次也可以让算法排序结果正确.
问题应该是出现在我注释掉的交换类方法的代码上,为什么选择排序算法类中创建这个对象,用这个方法只能用一次才能保证正确?用第二次就会使算法排序结果错误.
我想知道为什么,三克油!
恕我直言,您是否没有注意到列表中的值是在随时变化的:
arr[i] = arr[i] + arr[j];
arr[j] = arr[i] - arr[j];
arr[i] = arr[i] - arr[j]
这是一个比较糟糕的设计,其主要原因在于并没有注意到汇总值的 i与j可能存在两个值相同的时候,一旦 i==j,那么我们可以看到,当您修改arr[i]时,也就同时修改了arr[j]的值,将会引入一个值 0 到您的序列中,最终排序结果将会失败!这是一个运行案例:
解决办法也很简单,定义一个中间值total,来存储两值之和,或者当i==j时,不执行交换过程,希望对您有所帮助!
用注释到的部分的话,如果i=j,就会出现问题了,arr[i]和arr[j]都会等于0