Java选择排序 [英] Java Selection Sort
问题描述
我在检查每个索引时遇到问题.它会跳过j的第三个索引，因为它会从i[0]，j[2]到i[0]，j[4]，我不知道为什么这样做.另外，我实际上无法调换我的电话号码.有人知道我的错误在哪里吗?
I am having issues getting my sort to check every index. It skips the 3rd indices for j as in it goes i[0], j[2], to i[0], j[4] I don't know why it is doing that?. Also, I am having trouble with my numbers actually be swapped. Does anybody know where my error is?
static void selectionSort(int[] arr) {
final long startTime = System.nanoTime(); // starts timer
System.out.println("Selection Sort");
//************** Code For Sorting *****************//
//*************************************************//
int counter = 0;
int first = 0;
int second = 0;
//int[] sorted = Arrays.copyOf(arr, arr.length); // Copies unsorted array to new array
//Arrays.sort(sorted); // sorts unsorted array for compairison later on
for( int i = 0; i < arr.length-1; i++) // comparing the first index value to the rest of the values in the array
{
int minIndex = i;
for(int j = 1; j < arr.length-1; j++) // representing the next index value to the original and comparing it
{
int nextIndex = j;
if( arr[minIndex] < arr[nextIndex])
{
System.out.println("i: " +i);
System.out.println("j: " +j);
System.out.println("Checking next index");
}
if(arr[minIndex] > arr[nextIndex])
{
System.out.println("i: " +i);
System.out.println("j: " +j);
//counter = j; // getting array index
first = arr[minIndex];
second = arr[nextIndex];
minIndex = second;
arr[minIndex] = second;
System.out.println("first:" + first);
System.out.println("second:" + second);
System.out.println("minIndex:" + minIndex);
System.out.println("arr[minIndex]:" + arr[minIndex]) ;
System.out.println("Possible lowest unsorted value");
}
//Swap here
if(arr[arr.length-1] == arr[j]){
arr[0] = second;
arr[counter] = first;
counter = 0;
//minIndex= i+1;
}
}
for(int k = 0; k < arr.length; k++)
{
System.out.print(arr[k] + ", ");
}
System.out.println();
}
推荐答案
您犯的第一个错误是在嵌套的for循环中.对于外部for循环的每次迭代，内部循环的起始索引(j)应该始终从i + 1(在索引器i之前的位置)开始不
The first mistake you've made is within your nested for loop. the starting index (j) for the inner loop should always start at i + 1 (one place ahead of the indexer i) for each iteration of the outer for loop not j = 1 as you've done.
第二，通过满足条件j < arr.length-1，您将始终排除数组中的最后一个元素.
Second, by having the condition j < arr.length-1 you'll always exclude the last element within the array.
更改此内容:
for(int j = 1; j < arr.length-1; j++)
对此:
for(int j = i + 1; j < arr.length; j++)
继续，您的算法似乎存在一些问题，包括您的swap功能，因此，让我们重新开始.
Moving on, there seems to be several problems with your algorithm including your swap functionality so, let's start again.
选择排序是一种基于就地比较的算法，其中将数组分为两部分，左端为已排序部分，右端为未排序部分.最初，排序的部分为空，未排序的部分为整个数组.
Selection sort is an in-place comparison-based algorithm in which the array is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Initially, the sorted part is empty and the unsorted part is the entire array.
从未排序的数组中选择最小的元素，并与最左边的元素交换，该元素成为排序数组的一部分.此过程继续将未排序的数组边界向右移动一个元素.
The smallest element is selected from the unsorted array and swapped with the leftmost element, and that element becomes a part of the sorted array. This process continues moving unsorted array boundary by one element to the right.
考虑到这一点，现在我们可以启动算法了.
with that in mind, now we can start the algorithm.
public static void selectionSort(int[] arr){
for(int i = 0; i < arr.length-1; i++){
int minIndex = i; // smallest element index
for(int j = i + 1; j < arr.length; j++){
if(arr[j] < arr[i]){ // find smallest element
if(arr[j] < arr[minIndex])
minIndex = j; // update smallest element index
}
}
if(i != minIndex){ // swap
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
// print the result
Arrays.stream(arr).forEach(System.out::println);
}
作为补充，选择排序复杂度为Ο(N2)，其中N是数组中元素的数量.
as a side note, Selection sort complexities are of Ο(N2), where N is the number of elements within the array.
这篇关于Java选择排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
