자바 정렬 알고리즘 그림 설명
10530 단어 자바알고리즘상세 하 게 해석 하 다
기본 사상:
정렬 된 질서 있 는 표 에 기록 을 삽입 하여 삽 입 된 표 가 질서 있 게 합 니 다.
초기 키워드{49 38 65 97 76 13 27 49}직접 삽입 정렬
package Sort;
//
public class InsertSort {
public static void main(String[] args) {
int [] arr={49,38,65,97,76,13,27,49};
sort(arr);
print(arr);
}
private static void sort(int [] arr) {
for (int i = 1; i < arr.length; i++) {
for(int j=i;j>0;j--){
if(arr[j]<arr[j-1]){
swap(arr,j,j-1);
}
}
}
}
private static void swap(int [] arr,int i,int j){
int temp=0;
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
private static void print(int [] arr) {
for (int i = 0; i <arr.length ; i++) {
System.out.print(arr[i]+" ");
}
}
}
Process finished with exit code 0
2.힐 정렬
힐 정렬 은'증 량 축소 정렬'
Diminishing Increment Sort)）이 라 고도 부 르 는데 삽입 정렬 클래스 에 속한다.기본 사상:
먼저 전체 정렬 대기 기록 을 몇 개의 하위 서열 로 나 누 어 각각'직접 삽입 정렬'을 하고 전체 서열 중의 기록'이 기본적으로 질서 가 있 을 때 전체 기록 에 대해 직접 삽입 정렬 을 한다.
package Sort;
//
public class ShellSort {
public static void main(String[] args) {
int [] arr={16,25,12,30,47,11,23,36,9,18,31};
sort(arr);
print(arr);
}
private static void sort(int [] arr) {
//gap
int h=1;
while(h<arr.length/3){
h=h*3+1;
}
for(int gap=h;gap>0;gap=(gap-1)/3) {//gap:
for (int i = gap; i < arr.length; i++) {
for (int j = i; j >gap-1; j-=gap) {
if (arr[j] < arr[j - gap]) {
swap(arr, j, j - gap);
}
}
}
}
}
private static void swap(int [] arr,int i,int j){
int temp=0;
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
private static void print(int [] arr) {
for (int i = 0; i <arr.length ; i++) {
System.out.print(arr[i]+" ");
}
}
}
Process finished with exit code 0
3.거품 정렬
거품 정렬
4.빠 른 정렬
거품 정렬 개선
기본 사상:
한 번 의 정렬 을 통 해 정렬 대기 기록 을 독립 된 두 부분 으로 나 누 었 는데 그 중의 한 부분의 키 워드 는 모두 다른 부분의 키워드 보다 작 으 면 각각 이 두 부분의 기록 을 계속 정렬 하여 전체 서열 의 질 서 를 달성 할 수 있다.
package Sort;
import java.util.Arrays;
//
public class QuickSort {
public static void main(String[] args) {
int[] arr={49,38,65,97,76,13,27,49};
sort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
private static void sort(int [] arr,int start,int end) {
if(start<end){
// 0
int stared=arr[start];
//
int low=start;
int height=end;
//
while(low<height){
//
while(low<height&&stared<=arr[height]){
height--;
}
//
arr[low]=arr[height];
//
while(low<height&&stared>=arr[low]){
low++;
}
//
arr[height]=arr[low];
}
arr[low]=stared;
sort(arr,start,low);
sort(arr,low+1,height);
}
}
}
Process finished with exit code 0
5.정렬 선택(Selection Sort)
정렬 선택
여섯,더미 정렬
， ， ， ， O(nlogn)， 。
모든 결점 의 값 은 그 좌우 아이의 결점 의 값 보다 작 거나 같 아서 작은 지붕 더미 라 고 부른다
1.큰 더미 의 예 를 들 어 설명 한다.
우 리 는 더미 속 의 결점 을 층 별로 번 호 를 매 겨 배열 에 비 추 는 것 이 바로 아래 와 같다.
큰 더미 특징:arr[i]>=arr[2 i+1]&&arr[i]>=arr[2 i+2]/i 는 몇 번 째 노드 에 대응 하고 i 는 0 부터 번 호 를 매 긴 다.
2.작은 지붕 더미 예 를 들 어 설명
작은 더미:arr[i]<=arr[2 i+1]&&arr[i]<=arr[2 i+2]/i 는 몇 번 째 노드 에 대응 하고 i 는 0 부터 번 호 를 매 긴 다.
일반적으로 상승 순 서 는 큰 지붕 더 미 를 사용 하고,하강 순 서 는 작은 지붕 더 미 를 사용한다.
정렬 기본 사상
1.정렬 의 기본 사상 은:
정렬 대기 서열 을 큰 지붕 더미 로 구성 하 다.
이때 전체 서열 의 최대 치 는 지붕 의 뿌리 노드 이다.
이 를 마지막 요소 와 교환 하면 끝 이 최대 치 입 니 다.
그 다음 에 남 은 n-1 개의 요 소 를 하나의 더미 로 재 구성 하면 n 개의 요소 의 작은 값 을 얻 을 수 있 습 니 다.이렇게 반복 적 으로 집행 하면 질서 있 는 서열 을 얻 을 수 있다.
코드 예시
package Sort;
import java.util.Arrays;
/**
* 1、 i=1 ；arr[i]=6 i=0
* 4 i ， ： 9
* /\ 4 /\
* 6 8 /\ 6 8
* /\ 9 8 /\
* 5 9 /\ 5 4
* 5 6
*/
public class HeapSort {
public static void main(String[] args) {
int [] arr={4,6,8,5,9};
heapSort(arr);
}
//
public static void heapSort(int[] arr){
int temp=0;
for(int i=arr.length/2-1;i>=0;i--){
adjustHeap(arr,i,arr.length);
}
// ， ，
// ， ， ， ，
for(int j=arr.length-1;j>0;j--) {
//
temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
adjustHeap(arr, 0, j);
}
System.out.println(" "+Arrays.toString(arr));
}
//
/**
* ： i
* ：int[]arr={4,6,8,5,9};=>i=1=>adjustHeap=> {4，9，8，5，6}
* adjustHeap i=0,{4，9，8，5，6}=> {9，6，8，5，4}
* @param arr
* @param i
* @param length ，length
*/
public static void adjustHeap(int[]arr,int i,int length){
int temp=arr[i];// ，
//
//k=i*2+1;k i
for(int k=i*2+1;k<length;k=k*2+1){
if(k+1<length&&arr[k]<arr[k+1]){//
k++;//k
}
if(arr[k]>temp){//
arr[i]=arr[k];//
i=k;//!!!i k，
}else{
break;
}
}
// for ， i （ ）
arr[i]=temp;// temp
}
}
배열[4,5,6,8,9]
7.병합 정렬
정의:
또 다른 정렬 방법 은 두 개 이상 의 질서 표를 합 쳐 새로운 질서 표 로 만든다.
보조 공간 필요:
O(n) 전체 병합[log2n]회 필요시간 복잡 도:
O(nlog2n) 단점:병합 정렬 은 추가 저장 소 를 많이 차지 하고 원래 정렬 대상 배열 과 같은 크기 의 보조 배열 이 필요 합 니 다.장점:병합 정렬 은 안정 적 인 정렬 방법 입 니 다.
사고방식 은'다 중 병합'까지 보급 할 수 있다
외부 정렬
package Sort;
//
public class MergeSort {
public static void main(String[] args) {
int [] arr={4,5,7,8,1,2,3,6};
sort(arr);
print(arr);
}
private static void sort(int [] arr) {
int mid=arr.length/2;
int[]temp=new int[arr.length];
int i=0;//
int j=mid+1;//
int k=0;
while(i<=mid&&j<arr.length){
if(arr[i]<=arr[j]){
temp[k]=arr[i];
i++;
k++;
}else{
temp[k]=arr[j];
j++;
k++;
}
}
while(i<=mid){temp[k++]=arr[i++];}// ，
while(j<arr.length){temp[k++]=arr[j++];}// ，
}
private static void print(int [] arr) {
for (int i = 0; i <arr.length ; i++) {
System.out.print(arr[i]+" ");
}
}
}
Process finished with exit code 0
총결산
이 글 은 여기까지 입 니 다.당신 에 게 도움 을 줄 수 있 기 를 바 랍 니 다.또한 당신 이 우리 의 더 많은 내용 에 관심 을 가 져 주 기 를 바 랍 니 다!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Is Eclipse IDE dying?In 2014 the Eclipse IDE is the leading development environment for Java with a market share of approximately 65%. but ac...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
