Выбор Сортировка в Java прекращает сортировку по истечении времени [дубликат]

/* 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<n ; i++)
        {
            a[i] = in.nextInt();
        }
        System.out.println("Before Sorting: "+Arrays.toString(a));
        a = sort(a);
        System.out.println("After Sorting: "+Arrays.toString(a));
    }

    private static int[] sort(int[] a) {
        // TODO Auto-generated method stub

        for(int i=0; i<a.length-1;i++)
        {
            int index=i;
            for(int j=i+1; j<a.length;j++)

                if(a[j]<a[index])
                {
                    index=j;
                }
                int small = a[index];
                a[index] = a[i];
                a[i]=small;

        }
        return a;
    }
}

Сортировка выбора - это алгоритм, который формирует элементы массива в порядке ANSI или порядке DENSI. Наилучший случай, средний случай и худшая временная сложность - (n2). Сортировка выбора не лучше для сортировки массива ... Реализация сортировки выбора приведена ниже:

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;i<n;i++){
                  ar[i]=sc.nextInt();
             }

             for(i=0;i<(n-1);i++){
                  minVal=ar[i];
                  for(j=(i+1);j<n;j++){
                          if(minVal>ar[j]){
                                  minVal=ar[j];
                                  tmp=ar[i];
                                  ar[i]=minVal;
                                  ar[j]=tmp;
                          }
                  }

            }

            for(i=0;i<n;i++){
                  System.out.print(ar[i]+"  ");
            }
  }

Ваш вопрос, кажется, находится в вашем комментарии

min = i;//Selection sort algorithm says that find the minimum in the
        // array, but first element is not minimum.What's point here?

. То есть вы можете предположить, что первый, который вы проверяете, является самым низким, так что у вас есть место для начала. В конце концов, это может быть не минимальный, а тот, который вы проверили на этой итерации, это самый низкий показатель до сих пор!

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
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.

http://brianredd.com/algorithm/selection-sort

    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;
      }

Это правильный метод сортировки выбора. Вещь, которую вы делаете неправильно, заключается в том, что вы меняете внутри внутреннего цикла, но на самом деле замена должна выполняться после первого полного цикла внутреннего цикла, где минимальный элемент определяется.

Выбор сортировки - это поиск минимального значения на каждом шаге цикла. вы не обнаружили значение min (по выражению 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

Предположим, что самый нижний элемент требует сканирования всех элементов, а затем поменять его на первую позицию.

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]+" ");
        }
    }

Неправильно то, что в вашем внутреннем цикле вы должны обновить свой индекс, используя стратегию, которую вы выполняете для свопа во внутреннем цикле. Я сделал рабочий выбор:

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 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;
        }

Сначала вы должны найти минимум вместо того, чтобы считать, что первым элементом является минимальный

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;
}

Вы должны начать с предположения, что первый элемент является наименьшим, затем перебирайте массив и, если вы найдете меньший элемент, запомните эту позицию и предположите, что это самый маленький. Когда вы дойдете до конца массива, вы должны знать положение наименьшего значения. Переключите это значение со значением в первой позиции. Теперь самое маленькое значение - первое. Начните с следующей позиции, предположите, что это наименьшее значение, итерации по остальной части массива ... (я думаю, вы поняли идею.

Пример:

3,1,2

Предположим Сравните с позицией 2, 1 & lt; 3, так что предположим, что положение 2 имеет наименьшее значение. Сравните с позицией 3, 3 & lt; 1. Поскольку мы находимся на концевом выключателе наименьшим с первой позицией (позиция 1 и 2)

1,3,2

Теперь, поскольку позиция 1 выполнена, начните с позиции 2. Предположим, что 3 (позиция 2) является наименьшим значением. Сравните с позицией 3 (2). 2 и 3 , поэтому предположим, что позиция 3 имеет наименьшее значение. Поскольку мы находимся в конце массива, мы переключаем положение 2 и 3

1,2,3

Выполнено

public class 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<nofele-1;k++)  {





  for(int l=nofele-k,b=1;l>=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]);

}

}

Правильно:

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<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;}
        }
        int temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
        System.out.println(arr[i]);//I print the in ascending order 
    }
}

}

О минимальной части: это просто относится к индексу любого текущего мин. Вы перемещаетесь по массиву до тех пор, пока не встретите новый мин и не установите этот индекс. Итак, 5 - минимальное число [min = 0], пока вы не увидите 4 [так теперь min = 1], но затем вы сравните 3 с тем, что хранится в 4 [когда min = 1], а затем осознайте, что вы должны установить min = 2. ... и т. д. и т. д.