[伯俊]2750数ソートjava

質問する

N個の数字が与えられた場合、昇順で並べ替えられたプログラムを作成します.

入力

第1行は、数の個数N(1≦N≦1000)を与える.2行目からN行に数を与える.この数は整数で、節値は1000以下です.数量は重複しません.

しゅつりょく

1行目からN行目まで昇順に並べた結果、1行ずつ出力されます.

私の答え

並べ替え問題はArraysを簡単に解決できる.sort()関数を使用して簡単にソートできます.
その動作原理を表すために,選択ソートと挿入ソートの2つの異なるプールを追加した.

羅東彬の「これが就職のためのコードテストだ」を参考にした.

ソートの選択とは?

未処理のデータの中から最小のデータを選択し、一番前のデータと置き換えるソートアルゴリズム.

step1

0番目のインデックスの7を置き換えるには、範囲全体で最小の数値0を選択します.

step2

置換後の0以外の未処理データの中で最小の1を選択して置換する5.

step3

置換1以外の未処理データの中で最小の2置換9を選択します.

step4

置換した2以外の未処理データの中で最小の数字3を選択して置換します.

step5

この手順を繰り返すと、昇順でソートされます.

挿入ソートとは?

データ配列のすべての要素を前から順番に並べ替えられた配列部分と比較し、自分の位置を検索して挿入することで並べ替えのアルゴリズムを完了します.

step1

1番目のデータ7自体がソートされ、2番目のデータ5がどの位置に入るか.7の左側、右側、または両方の場合にのみ存在します.

step2

次に9がどの位置に入るかを判断します.

step3

そして0がどの位置に入るかを判断する.

step4

この手順を繰り返して、次のソートを行います.

アルゴリズムを実際の問題のパーセントに並べ替えます。Javaに適用

import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

int n = sc.nextInt(); //길이
int []arr = new int[n];
for(int i = 0;i<n;i++){
  arr[i] = sc.nextInt();
}

//Arrays.sort(arr);

// 1.선택정렬
// for(int i = 0;i<n;i++){
//   int min_index = i;
//   for(int j = i+1;j<n;j++){
//     if(arr[min_index] > arr[j]){
//       min_index = j;
//     }
//   }
//   int temp = arr[i];
//   arr[i] = arr[min_index];
//   arr[min_index] = temp;
// }

//2.삽입정렬
for(int i = 1;i<n;i++){
  for(int j = i-1;j >= 0;j--){
    if(arr[j] > arr[j+1]){
      int temp = arr[j];
      arr[j] = arr[j+1];
      arr[j+1] = temp;
    }else{
      break;
    }
  }
}

for(int i = 0;i<arr.length;i++){
  System.out.println(arr[i]);
}

}
}