问题描述
最近，我一直在研究排序算法，就像许多算法入门书籍一样，我已经开始阅读的一本书是从选择排序实现开始的。
代码如下...
Recently i have been looking into sorting algorithms, and like many intro to algorithms books the one I have begun to read starts off with a selection sort implementation.the code went as follows...
实施A
//a is an array of ints.
int n = a.length;
for(int i = 0; i < n; i ++){
int min =0;
for( int x = i+1; x <n;x++){
if(a[x].compareTo(a[i])<0){
Comparable tmp = a[i];
a[i] = a[x];
a[x] = tmp;
}
}
}
分析代码块后，将算法更改为以下内容。
After analyzing the code block i altered the algorithm to the following.
实现B
//a is an array of ints
int n = a.length;
for(int i = 0; i < n; i ++){
int min =i;
for( int x = i+1; x <n;x++){
if(a[x].compareTo(a[min])<0){
min=x;
}
}
if(min>i){
Comparable tmp = a[i];
a[i] = a[min];
a[min] = tmp;
}
}
我也在网上找到了类似的实现使用最小值在数组中找到最小值，然后将其与数组中位置i的项交换出去。我的问题是，第二个实现是否存在某些错误？这不是一个正确的选择排序方法，因为它没有交换掉所定位的每个比位置i处的元素小的元素，而是等到它在数组中找到最小的元素后再交换？
I have also found similar implementations online using the min value to locate the smallest value within the array and then swapping it out with the item in position i of the array. My question, Is there something incorrect with the second implementation? is this not a proper selection sort because it is not swapping out every element it locates that is smaller then the item at position i, but instead waits till it finds the smallest item in the array prior to swapping?
我已经使用两种算法对超过10000个数组值的算法进行了一些测试，并且第二种实现总是先完成，速度几乎提高了一倍。这些测试是在随机阵列上进行的。
I have run some tests with both algorithms with over 10000 array values and the second implementation always finishes first, by almost double the speed. These tests were on randomized arrays.
推荐答案
实现B是正确的选择排序。实现A并不是因为它总是将较小的值交换到前面，而有时不是最小的值。
Implementation B is a correct Selection Sort. Implementation A is not because it always swap smaller value into the front which sometimes is not smallest value.
根据维基百科
这篇关于选择排序的两个版本的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！