Shell Sort(Shell Sort)
7525 ワード
Shellソート
ソートの補完アルゴリズムの挿入
1.一定の基準に従って、先に並べ替える必要があるリストを分類する
2.複数の不連続部分リストを作成する
3.挿入ソートを使用して各部分リストをソートする
4.すべての部分リストを並べ替え、リスト全体をより少ない部分リストに再設定し、アルゴリズムを繰り返す
5.重複部分リストの個数は1
時間の複雑さ
最悪:O(n^2)
平均値:O(n^1.5)
最適:O(n)
くうかんふくざつさ
O(n)
長所
ソートの挿入よりも優れている
短所
間隔設定が間違っているとパフォーマンスが非常に悪くなります
public class ShellSort {
public static void main(String[] args) {
int[] arr = {9, 4, 1, 7, 3, 2, 1, 5, 0, 6, 8};
int len = arr.length;
int temp = 0;
int gap = len;
for (; gap > 1;) {
gap = (gap / 3) + 1;
System.out.println("gap : " + gap);
for (int i = 0; i < gap; i++) {// gap 만큼 반복한다
//삽입 정렬 로직
for (int j = i + gap; j < len; j += gap) {
/*
i : 묶음을 구분하기 위한 값
j : 삽입 정렬 종료 인덱스
*/
for (int x = i; x < j; x += gap) {
/*
x인덱스 ~ j인덱스 까지 반복하여 삽입정렬을 실행한다.
*/
if (arr[x] > arr[j]) {
temp = arr[x];
arr[x] = arr[j];
arr[j] = temp;
}
}
}
}
System.out.println(Arrays.toString(arr));
}
}
}Reference
この問題について(Shell Sort(Shell Sort)), 我々は、より多くの情報をここで見つけました https://velog.io/@away0419/쉘-정렬Shell-Sortテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol