퀵 정렬은 일반적인 생각은 있기 때문에 오랫동안 살펴보게 하고 오랫동안 괴롭혔지만, 코드를 작성할 때 항상 여러 가지 문제가 발생하기 때문에 개인적으로 디버그하기는 어렵습니다. 어느 정도의 어려움과 작업과 게으름으로 인해 디버깅할 수 없는 오류를 오랫동안 치워두었는데, 오늘 드디어 나왔네요, 그래도 제 코드를 공유해서 전해드리도록 하겠습니다. 약간의 설명.
빠른 정렬을 배우려면 먼저 분할 정복 방법을 배워야 합니다. 분할 정복의 개념은 순서가 잘못된 숫자의 문자열을 제공하는 것입니다(숫자는 가정이며 다른 객체일 수도 있습니다. 물론 메소드의 매개변수는 직접 정의할 수 있습니다. 정수 배열이 있다고 가정해 보겠습니다. 중간 숫자, 분할 정복 방법은 주어진 중간 숫자를 기준으로 이 숫자를 두 부분으로 나누고, 한 부분은 중간 숫자의 왼쪽에 있고 다른 부분은 이 숫자를 오른쪽에 있습니다. 나누는 점에서 양쪽의 숫자는 여전히 순서가 잘못되었습니다. 제가 정의한 방식은 다음과 같습니다.
//왼쪽은 배열 분할 정복 부분의 왼쪽 끝점이고 오른쪽은 배열 분할 정복 부분의 전체 끝점입니다. 예를 들어 길이가 10인 배열의 경우 처음 5개의 정수를 나누어 정복하고 싶습니다. public int signalFenZhi(int left,int right){ if(left<0||left>n-1||right<0||right>로 0 또는 4를 전달할 수 있습니다. n-1){ 반환 -1; } int temp = test[left]; j=right; int i=left; while(i<j){ while(test[j]>=test[left]&&i<j){ j-- } while(test[i]<=test[left] &&i<j){ i++; } if(i<j){ temp = test[i]; test[i]=test[j] test[j]=temp; = 테스트[i]; test[i]=test[left]; test[left]=temp; } for(int m=0;m<n;m++){ System.out.print(test[m]+" ") return i ;물론 중간 숫자를 매개변수로 전달할 수도 있습니다. 이제 전달된 왼쪽 숫자를 단지 설명을 위한 것입니다.
분할 정복을 이해한 후, 빠른 정렬은 두 부분으로 나누어진 숫자를 분할하여 정복하는 등 모든 숫자가 순서대로 될 때까지 수행하는 것입니다.
public voidquickSort(int left,int right){ if(right-left<1){ return }else{ int point = this.signalFenZhi(left, right); //if( point!=왼쪽&&point!=오른쪽){ QuickSort(왼쪽,점-1) QuickSort(점+1,오른쪽) //} } }많은 정렬 알고리즘 중에서 퀵 정렬의 효율성은 O(N*log2n)이지만 분할 정복의 분할 지점을 잘 선택하지 않으면 시간 복잡도가 (n 제곱)으로 줄어듭니다. ), 이 배열이 정렬된 다음 매번 전달되는 가장 왼쪽 숫자를 취하면 효율성이 매우 낮기 때문에 모든 옵션을 테스트하면 이 상황을 피해야 합니다. 시간이 그래서 절충 방법은 가장 왼쪽 숫자와 가장 오른쪽 숫자에 중간 숫자를 더하고, 이를 나누는 값으로 사용하면 상황이 더 좋아집니다. 하지만 다 마친 후에는 이 접근 방식이 별로 좋지 않았습니다. 분할 정복 방법으로 나누는 것이 더 나을 것입니다. 신중한 친구들이 직접 시도해 볼 수도 있지만 여기서는 기본적으로 동일하게 시도하지 않겠습니다.
package com.jll; public class FenZhi { int[] test; public FenZhi(){ test = new int[10] for(int i=0;i<n;i++); =(int)(Math.random()*100)+1; System.out.print(test[i]+" ") } System.out.println() } public FenZhi(int n){ if(n>0){ this.n=n; test = new int[n]; for(int i=0;i<n;i++){ test[i]=(int)(Math.random ()*100)+1; } } } public int signalFenZhiMajorizationFirst(int left,int right){ if(왼쪽<0||왼쪽>n-1||오른쪽<0||오른쪽>n-1||왼쪽>=오른쪽){ return -1 } if(오른쪽-왼쪽>=2){ int middle = (오른쪽+왼쪽)/2; if(테스트[왼쪽]>테스트[가운데]){ int temp = 테스트[가운데]; 테스트[왼쪽] = 테스트[왼쪽]; if(테스트[왼쪽]>테스트[오른쪽]){ int temp = 테스트[왼쪽]; 테스트[왼쪽] = 테스트[오른쪽] = 임시 } if(테스트[중간]>테스트[오른쪽] ){ int temp = test[middle]; test[right]; test[right] = temp; } int temp = test[middle] = test[left]; = temp; int j=right-1; int i=left+1; while(test[j]>=test[left]&&i<j) { j-- } ]<=test[left]&&i<j){ i++; } if(i<j){ temp = test[i]; test[i]=test[j] } } if( 나는==j){ temp = test[i]; test[i]=test[left]; test[left]=temp; } /*if(i==j){ temp = test[middle]=test[i ]; test[i]=temp; }*/ /*for(int m=0;m<n;m++){ System.out.print(test[m]+" ") }*/ return i; 또 다른 { if(test[right]<test[left]){ int temp = test[right]; test[left] = test[left] = temp; } return right; ,int right){ if(right-left<1){ return ; }else{ int point = this.signalFenZhiMajorizationFirst(left, right)("점 is: "+point);quickSortMajorizationFirst(왼쪽,point-1);quickSortMajorizationFirst(point+1,right); } } public static void main(String[] args) { FenZhi f = new FenZhi(); System.out. println(f.signalFenZhiMajorizationFirst(0, 9)); System.out.println(); f.quickSortMajorizationFirst(0,fn-1); //f.quickSort(0,f.test.length-1) for(int i:f.test){ System.out.print(i+" "); }}코드는 다음과 같이 실행됩니다.
95 40 64 18 78 23 73 84 40 요점은:4점은:1점은:3점은:7점은:6점은:918 23 40 40 64 73 78 84 95
위 내용은 제가 배운 내용이므로 나중에 참고할 수 있도록 기록해 두세요.