Java – 选择排序算法
我对选择排序有一些疑问。我有点困惑。
int [] arr = {5,4,3,2,1}; // This is my array int min = 0; for(int i = 0;i<arr.length;i++) { //Assume first element is min min = i;//Selection sort algorithm says that find the minimum in the // array, but first element is not minimum.What's point here? for(int j = i + 1;j<arr.length;j++) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; System.out.println(arr[i]);//I print the in ascending order } } 输出是：
4 3 2 1 4 3 2 4 3 4
怎么了 ？
选择排序是关于在循环的每个步骤中找到最小值。 你没有找到最小值（可能是if语句），只需简单地交换内循环中的值即可。 所以你实际上没有做一个排序。
根据您的实施进行更正：
final int[] arr = { 5, 4, 3, 2, 1 }; // This is my array int min; for (int i = 0; i < arr.length; i++) { // Assume first element is min min = i; for (int j = i + 1; j < arr.length; j++) { if (arr[j] < arr[min]) { min = j; } } if (min != i) { final int temp = arr[i]; arr[i] = arr[min]; arr[min] = temp; } System.out.println(arr[i]);// I print the in ascending order }
这应该给你输出：
1 2 3 4 5
正确：
public class Test { public static void main(String args[]){ int[] arr = {5,4,3,2,1}; // This is my array int min = 0; for(int i = 0;i
关于min部分：它只是指当前min的索引。 继续向下移动数组，直到达到新的min，然后将min设置为该索引。 所以5是最小数[min = 0]，直到你看到4 [所以现在min = 1]，然后你将3与存储在4 [当min = 1]的任何东西进行比较，然后意识到你应该设置min = 2。等等
您的问题似乎出现在您的评论中
min = i;//Selection sort algorithm says that find the minimum in the // array, but first element is not minimum.What's point here?
关键是你可以假设你检查的第一个是最低的，所以你有一个起点。 毕竟，它可能不是最小的，但是你已经在这次迭代中检查了一个，它是迄今为止最低的！
您应首先找到最小值，而不是假设第一个元素是最小值
int[] array = {5, 4, 3, 2, 1}; for ( int i = 0; i < array.length; i++ ) { //find minimum, starting from index i int minIndex = i; int min = array[i]; for ( int j = i + 1; j < array.length; j++ ) { if ( array[ j ] < min ) { minIndex = j; min = array[j]; } } // now move the smallest element to the front, and the element at index i to the index of the minimal element int temp = array[ i ]; array[ i ] = min; array[ minIndex ] = temp; }
选择排序算法通过从未排序的部分重复查找最小元素（考虑升序）并将其放在开头来对数组进行排序。 该算法在给定数组中维护两个子数组。
1）已经排序的子arrays。 2）未分类的剩余子数组。
在选择排序的每次迭代中，挑选来自未排序子arrays的最小元素（考虑升序）并将其移动到排序子arrays。
例：
arr[] = 64 25 12 22 11 // Find the minimum element in arr[0...4] // and place it at beginning 11 25 12 22 64 // Find the minimum element in arr[1...4] // and place it at beginning of arr[1...4] 11 12 25 22 64 // Find the minimum element in arr[2...4] // and place it at beginning of arr[2...4] 11 12 22 25 64 // Find the minimum element in arr[3...4] // and place it at beginning of arr[3...4] 11 12 22 25 64
Java代码是：
void sort(int arr[]) { int n = arr.length; // One by one move boundary of unsorted subarray for (int i = 0; i < n-1; i++) { // Find the minimum element in unsorted array int min_idx = i; for (int j = i+1; j < n; j++) if (arr[j] < arr[min_idx]) min_idx = j; // Swap the found minimum element with the first // element int temp = arr[min_idx]; arr[min_idx] = arr[i]; arr[i] = temp; } }
并明确表示arrays通过参考传递！
您应该首先假设第一个元素是最小元素，然后迭代数组，如果找到一个更小的元素，请记住该位置并假设它是最小的元素。 当你到达数组的末尾时，你应该知道最小值的位置。 使用第一个位置的值切换该值。 现在最小的值是第一个。 从下一个位置开始，假设它是最小的值，迭代在arrays的其余部分……（我想你明白了。
例：
3,1,2
假设3（pos 1）最小。 与位置2,1 <3比较，假设位置2具有最小值。 与位置3相比，3 <1。因为我们在最后一个开关最小的位置。 （位置1和2）
1,3,2
现在，由于位置1已完成，因此从位置2开始。假设3（位置2）是最小值。 与位置3（2）比较。 2 <3，因此假设位置3具有最小值。 由于我们在阵列的末尾，我们切换位置2和3
1,2,3
完成
有问题的是，在你的内循环中你应该更新你的索引，使用你在内循环中进行交换的策略我做了一个工作选择排序：
import java.util.Arrays; public class SelectionSort { public static void main(String[] args) { int[] input = new int[] {5,2,4,6,1,3}; System.out.println( Arrays.toString(selectionSort(input)) ); } public static int[] selectionSort(int[] input) { int length = input.length; int minimumValue = Integer.MAX_VALUE; for (int i = 0; i < length; ++i) { // find the minimumValue when j > i and swap it with input[i] location for (int j =i; j < length; ++j) { if (input[j] <= minimumValue ) { minimumValue = input[j]; input[j] = input[i]; input[i] = minimumValue; } } minimumValue = Integer.MAX_VALUE; } return input; } }
我加入了github 。
public class SelectionSort { public static void main(String[] args) { int[] A = {5,4,3,2,1}; int l = A.length; for (int i = 0; i < l-1; ++i ){ int minPos = i; // Find the location of the minimal element for (int j = i + 1; j < l; ++j){ if ( A[j] < A[minPos]){ minPos = j; } } if (minPos != i){ int temp = A[i]; A[i] = A[minPos]; A[minPos] = temp; } } System.out.println(Arrays.toString(A)); } }
如前所述，您没有在内循环中更新’min’变量。 内循环的目标是找到最小元素的索引。 您还应该将’swap’移动到外循环。 下面是Selection Sort伪代码：
Selection Sort Inputs: A: an array n: the number of elements in A to sort Procedure SELECTION-SORT (A, n) 1. For i = 0 to n – 1: A. Set minIndex to i. B. For j = i + 1 to n: i. If A[j] < A[minIndex], then set minIndex to j. // Add this C. Swap A[i] with A[minIndex]. // Move this to outside of the inner loop
请查看下面我博客的链接，查看选择排序算法的完整说明。 有Java，C ++，Python和JavaScript的实现。
假设最低元素，需要扫描所有元素，然后将其交换到第一个位置。
private static void selectionSortMethod(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { //no of iterations for array length for (int j = i + 1; j < arr.length; j++) { //starting from next index to lowest element(assuming 1st index as lowest) if (arr[i] > arr[j]){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } } //print for (int i = 0; i < arr.length; i++) { System.out.print(arr[i]+" "); } }
/* Implementation of selection sort */ import java.util.Arrays; import java.util.Scanner; public class SelectionSort { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub Scanner in = new Scanner(System.in); System.out.println("Enter the number of elements of the array"); int n = in.nextInt(); int []a = new int[n]; System.out.println("Enter the integer array of elements"); for (int i=0; i
int[] arr = {5,4,3,2,1}; for (int i = 0; i < arr.length - 1; i++) { int index = i; for (int j = i + 1; j < arr.length; j++) if (arr[j] < arr[index]) index = j; int smallerNumber = arr[index]; arr[index] = arr[i]; arr[i] = smallerNumber; }
这是选择排序的正确方法你做错了的事情是你在内循环中交换，但实际上交换需要在确定最小元素的第一轮内循环之后完成。
公共类Selectionsort {
public static int arr []; public static int y;
public static void main（String args []）{
System.out.println（“输入要输入的元素数量以进行排序”）;
int nofele= Integer.parseInt(args[0]); System.out.println("Enter number of element entered for sorting is "+ "\n" +nofele); arr = new int[nofele]; System.out.println("Entered array is"); for(int i=1,j=0;i<=nofele;i++,j++){ arr[j]=Integer.parseInt(args[i]); System.out.println(arr[j]); } System.out.println("Sorted array for selection sort is "); for(int k=0;k=2;l--,b++){ if(arr[k]>arr[k+b]){ int temp=arr[k]; arr[k]=arr[k+b]; arr[k+b] = temp; } } System.out.println(arr[k]); } System.out.println(arr[nofele-1]);
}
}
选择排序是一种以ANSI顺序或DENSI顺序形成数组元素的算法。 最佳案例，平均案例和最差案例时间复杂度为（n 2 ）。 选择排序不是更好的排序数组…选择排序实现如下：
import java.util.Scanner; class selection{ public static void main(String a[]){ Scanner sc=new Scanner(System.in); System.out.print("size :"); int n=sc.nextInt(); int i,j,tmp,minVal; int[] ar=new int[n]; for(i=0;iar[j]){ minVal=ar[j]; tmp=ar[i]; ar[i]=minVal; ar[j]=tmp; } } } for(i=0;i
传递未排序的数组获取排序的数组
public int[] selectionSort(int[] list) { int i, j, minValue, minIndex, temp = 0; for (i = 1; i < list.length; i++) { minValue = list[i]; minIndex = i; j = i - 1; for (j = i; j < list.length; j++) { if (list[j] < minValue) { minValue = list[j]; minIndex = j; } } if (list[i] > minValue) { temp = list[i]; list[i] = list[minIndex]; list[minIndex] = temp; } } return list; }