빠른 분류의 원리에 대한 소개
빠른 분류는 이전에 배운 버블 분류의 업그레이드입니다. 그들은 모두 스왑 분류에 속하며, 모두 정렬을 달성하기 위해 지속적인 비교와 움직임을 사용합니다. 빠른 정렬은 매우 효율적인 정렬 알고리즘입니다. 구현은 레코드의 비교와 이동 사이의 거리를 증가시키고 앞면에서 뒷면에서 더 큰 키워드로 레코드를 이동시키고 뒷면에서 앞쪽에서 직접 키워드가 더 작은 레코드를 통해 총 비교 및 움직임 수가 줄어 듭니다. 동시에, "나누기 및 정복"이라는 아이디어는 빅을 작게 나누고 작은 것을 작은 것으로 나누기 위해 채택됩니다. 원리는 다음과 같습니다. 주어진 레코드 세트의 경우 벤치 마크 요소를 선택하고 일반적으로 첫 번째 요소 또는 마지막 요소가 선택되고 스캔을 통해 정렬 할 시퀀스는 두 부분으로 나뉘어지고 벤치 마크 요소보다 작거나 벤치 마크 요소보다 크게 나뉩니다. 이 시점에서 벤치 마크 요소는 정렬 된 후 올바른 위치에 있으며, 시퀀스의 모든 레코드가 주문 될 때까지 두 부분이 동일한 방식으로 재귀 적으로 정렬됩니다.
1. 가장 작은 k
예를 들어 가장 작은 k 숫자를 찾으려면 n 숫자를 입력하십시오. 예를 들어, 4,5,1,6,2,7,3,8을 입력하고 가장 작은 숫자는 1,2,3,4입니다.
O (n)에 기초하여,이 문제는 파벌 함수를 사용하여 해결할 수 있습니다. kth 번호를 기준으로 어레이의 KTH 번호가 조정 된 경우, KTH 번호보다 작은 모든 숫자가 배열 왼쪽에 있고 Kth 어레이보다 큰 모든 숫자가 배열 오른쪽에 위치합니다. 조정 후 배열 왼쪽의 k 숫자는 가장 작은 k 숫자이며 반드시 주문할 필요는 없습니다.
import java.util.scanner; public class main {public static void main (string [] args) {scanner in = new Scanner (System.in); int n = in.nextint (); int k = in.nextInt (); int [] new int []; int = out = new int [k]; for (for). i = 0; i <n; i ++) {num [i] = in.nextInt ();} boolean b = getMink (n, num, k, out); if (b) {for (int i = 0; i <k; i ++) {system.out.print (out [i]+"")}} public static bolean getmink (int uiinnum, intminnum, intming getmink. int uik, int [] poutputarray) {if (pinputarray == null || poutputarray == null || uik> uiinputnum || uiinputnum <= 0 || uik <= 0) {} int start = 0; int end = uiinputnum-1; int Index = 파티션 (pinputarray, start, start, start, start, start, end index); while (index! = uik-1) {if (index> uik-1) {// index는 k-1 end = index-1; index = partition (pinputArray, start, end);} else {start = index = partition (pinputArray, start, end);}} for (int)의 오른쪽에 있습니다. i = 0; i <uik; i ++) {poutputArray [i] = pinputArray [i];} return true;} // 파티션 파티션 함수 배열의 첫 번째 요소의 빠른 행의 인덱스 값을 반환합니다 public static intition (int [] a, int start, int end) {int privot = in int]; int]; j = end; while (i <j) {while (i <j && privot <= a [j]) {j-;} swap (a, i, j); while (i <j && privot> = a [i]) {i ++;} swap (a, i, j);} return i;} public static void swap (int [] a, int i, int j) {int t = a [i]; a [i] = a [j]; j] = t;}} 2. 배열에서 발생의 절반 이상을 가진 숫자
배열에는 배열 길이의 절반 이상이 나타나는 숫자가 있습니다. 이 번호를 찾으십시오. 예를 들어, 1, 2, 3, 2, 2, 5, 4, 2, 숫자 2는 배열에서 5 번 나타나 배열 길이의 절반을 초과하여 출력 2
빠른 정렬에서 영감을 얻은 빠른 정렬에서 배열에서 숫자를 선택한 다음 배열에서 숫자 순서를 조정하여 선택한 숫자보다 작은 숫자가 왼쪽에 순위가 높고 선택한 숫자보다 큰 숫자가 오른쪽에 순위가 매겨 지도록합니다.
선택한 숫자의 첨자가 N/2 인 경우이 숫자는 배열의 중간 숫자입니다.
import java.util.scanner; public class main {public static void main (string [] args) {scanner in = new Scanner (System.in); int n = in.nextint (); int [] num = new int [n]; for (int i = 0; i <n; i ++) {num [i] = in .nextint (); b = gethalfnum (n, num); if (b! = -1) {system.out.println (b);}} public static int gethalfnum (int uiinputnum, int [] pinputarray) {if (pinputarray == null || uiinputnum <= 0) {} int middle = uiinputnum >> 1; start = 0; int end = uiinputnum-1; int index = 파티션 (pinputArray, start, end); (index! = middle) {// 길이의 절반이 아닌 경우 (색인> 미들) {end = index-1; index = partition (pinputArray, start, end);} else {start = index+1; index = partition (pinputArray, start, end); index [index = index = index]; start, int end) {int privot = a [start]; int i = start; int j = end; while (i <j) {while (i <j && privot <= a [j]) {j-;} swap (a, i, j); while (i <j & privot> = a [i]) {i ++;} swap (a, i, j);} return i;} public static void swap (int [] a, int i, int j) {int t = a [i]; a [i] = a [j]; a [j] = t;}} 3. 배열에서 가장 작은 숫자를 찾으십시오
예를 들어, 배열 1, 5, 2, 6, 8, 0, 6이 주어지면 4 번째로 작은 숫자는 5입니다.
import java.util.scanner; public class main {public static void main (string [] args) {scanner in = new Scanner (System.in); int n = in.nextint (); int k = in.nextint (); int [] num = new int [n]; // int [] out = new int [k]; for (int i = 0; i <n; i ++) {num [i] = in.nextint ();} int b = getmink (n, num, k); if (b! = -1) {system.out.println (b);}} public static int getmink (int uiinputnum, int [] pinputarray, int uik) {if (pinputarray == null || uik> uiinputnum || uiinputnum <= 0 || uik <= 0) {return -1;} int start = 0; int end = uiinputnum -1; int index = 파티션 (pinputarray, start, end); while (index! = uik-1) {// 인덱스가 k-1의 위치가 아닌 경우 (index> uik-1) {end = index-1; index = partition (pinputArray, start, end);} else {start = index = partition (pinputArray, start, start, end); end) {int privot = a [start]; int i = start; int j = end; while (i <j) {while (i <j && privot <= a [j]) {j-;} swap (a, i, j); while (i <j & privot> = a [i]) {i ++;} swap (a, i, j);} return i;} public static void swap (int [] a, int i, int j) {int t = a [i]; a [i] = a [j]; a [j] = t;}}요약
위는 Java 프로그래밍의 빠른 정렬을 기반으로 세 가지 알고리즘 질문의 예제 코드에 대한이 기사의 전체 내용입니다. 모든 사람에게 도움이되기를 바랍니다. 관심있는 친구는이 사이트의 다른 관련 주제를 계속 참조 할 수 있습니다. 단점이 있으면 메시지를 남겨 두십시오. 이 사이트를 지원해 주신 친구들에게 감사드립니다!