정렬 알고리즘 거품, 선택, 삽입, 빠 른 배열
1. 거품 정렬:
n 번 을 배열 하면 매번 에 원래 의 서열 을 상대 적 으로 질서 있 게 만 들 고 횟수 가 증가 함 에 따라 질서 성도 향상 되 고 최종 적 으로 질서 가 있 습 니 다.
5,4,3,7,2,7
첫 번 째, 5 > 4, 교환 --- 4,5,3,7,2,7
5 > 3, 교환 --- 4, 3, 5, 7, 2, 7
5 < = 7, 교환 하지 않 음
7>2 ,교환
첫 번 째 거품 결과: 4, 3, 5, 2, 7, 7, (그 중) 4, 5, 7, 7 질서 정연)
두 번 째 거품 결과 (첫 번 째 비교 방식 반복): 3, 4, 2, 5, 7, 7 (그 중 3, 4, 5, 7, 7 질서)
세 번 째 거품 결과: 3, 2, 4, 5, 7, 7 (그 중 3, 4, 5, 7, 7 과 2, 4, 질서정연 하 다
네 번 째 거품 결과: 2, 3, 4, 5, 7, 7 (그 중 2, 3, 4, 5, 7, 7 질서)
다섯 번 째 거품: 교환 이 일어나 지 않 았 습 니 다. 거품 은 여기 서 끝 냅 니 다.
규칙: 모든 비 교 는 큰 원 소 를 뒤로 교환 합 니 다.
첫 번 째 비교 로 최대 원 소 를 마지막 으로 교환 할 수 있 습 니 다.
두 번 째 비교 하면 두 번 째 큰 원 소 를 마지막 두 번 째 위치 로 교환 할 수 있다.
******
그러면 매번 비교 하 는 요소 의 수량 은 -- 1 의 추 세 를 나타 내 는데 이것 은 삽입 정렬 과 비슷 하 다.
자바 코드 구현:
public int [] testBubbleSort(int []data){
int maxPos=0;
for(int i=0;idata[j+1])
{
// i
int temp =data[j];
data[j]=data[j+1];
data[j+1]=temp;
}
}
}
return data;
} 최적화:
/ 1,-1,3,5,2,7,8,9
// :-1,1,3,2,5 ,7,8,9 2 ( ) 3
// : -1,1,2,3,5,7,8,9 2 2( ) [0,3] [0, length]
/**
* @author wangwei
* @date 2019/1/24 18:49
* @classDescription :
* : , ,
* :
*/
public class BubbleSort implements Sortable {
@Override
public void sort(int[] array) {
//
// 1: :
// 2: i , i+1
// 1,-1,3,5,2,7,8,9
// :-1,1,3,2,5 ,7,8,9 2 ( ) 3
// : -1,1,2,3,5,7,8,9 2 2( ) [0,3] [0, length]
boolean exchanged = true;
int m = array.length-1;
while (m > 1 && exchanged) {
exchanged = false;
int lastSwapIndex = 1;// , 1
for (int j = 0; j <= m-1; j++) {
if (array[j] > array[j + 1]) {
ArrayUtil.swap(array, j, j + 1);
exchanged = true;
lastSwapIndex = j;
}
}
m = lastSwapIndex;
if (!exchanged) {
return;
}
}
}
}
2. 정렬 선택:
한 단위 의 공간 을 사용 하여 현재 비교 대상 서열 중의 첫 번 째 요 소 를 저장 합 니 다. 이 비교 서열 중의 최소 요소 와 아래 표 시 를 찾 아 이 비교 서열 의 머리 에 교환 하 는 것 이 목표 입 니 다.
첫 번 째: 비교 서열 은? 5,4,3,7,2,7
초기 minPos = 0;
minVal=array[0]=5
이번 비교 에서 나타 날 것 이다. 4
3
2
첫 번 째 비교 가 끝 난 후, 첫 번 째 로 찾 아 낸 최소 원 소 를 시퀀스 헤드 로 교환 합 니 다.
즉, 첫 번 째 비교 전에: 5,4,3,7,2,7,
첫 번 째 비교 후 교환 결과: 2, 4, 3, 7, 5, 7
두 번 째 비교 서열 은: 2, 4,3,7,5,7
비교 교환 후 결과: 2, 3, 4, 7, 5, 7
세 번 째 비교 서열 은 2, 3, 4, 7, 5, 7 이다.
제 i 차 비교 서열 은:
array[i-1],array[i],....,array[array.length-1]
매번 한 번 을 비교 할 때마다 다음 에 비교 하 는 원소 의 수량 은 지난번 보다 하나 적다.
자바 코드 구현
**
* @author wangwei
* @date 2019/1/24 10:47
* @classDescription
* : " " ( ) , ,
* : ,
*/
public class SimpleSelectSort implements Sortable{
@Override
public void sort(int[] array) {
for(int lastSortedIndex=0;lastSortedIndex3, 정렬 삽입:
아 날로 그 카드 를 만 지 는 과정 에서 손 에 들 고 있 는 카드 는 항상 질서 가 있 습 니 다. 공간 array. length 를 신청 해 야 합 니 다. (이것 도 꼭 그렇지 않 습 니 다. 만약 에 원래 배열 을 논리 적 으로 질서 있 고 무질서 한 두 부분 으로 나 누 면 array. length 의 공간 을 분배 하여 질서 있 는 배열 을 따로 저장 할 필요 가 없습니다)
공간 복잡 도: o (1)
시간 복잡 도: o (n ^ 2)
안정성
자바 코드 구현:
/**
* @author wangwei
* @date 2019/1/20 13:26
* @classDescription
* : , , ,
* :o(1)
* :o(n^2)
* :
*/
public class SimpleInsertSort implements Sortable{
@Override
public void sort(int[] array) {
int currIndex=1;/// [0,currIndex)
// , ,
//currIndex
for(;currIndex= 0) && (array[leftIndex] > toBePut)) {
array[leftIndex + 1] = array[leftIndex];
leftIndex--;
}
array[leftIndex+1]=toBePut;
}
}
}
/**
* :
* 1, , o(n) , , lg(n)
* 2, : ,
*/
}
무 작위 배열 의 코드 생 성:
public static int []getArrayRand(int length)
{
int []result=new int[length];
for(int i=0;i이때 속도 비교: 빠 른 줄 > 정렬 삽입 > 정렬 선택 > 거품 정렬
20 만 개의 요소 정렬 시간 (밀리초):
삽입
선택: 1, 6547 (거품 의 개량, 대량의 무효 교환 을 피 함)
거품 발생: 8, 2772 (달팽이 처럼 느 리 고 주요 원인 은 대량의 무효 교환)
쾌속: 47 (나 는 듯 한 느낌)
4. 병합 정렬
사상: 모든 구역 이 하나의 요소 일 때 까지 대규모 배열 을 계속 2 분 으로 나 눈 다음 에 두 개의 질서 있 는 구역 간 의 합병 을 실행 하고 하나의 구역 으로 합 쳐 정렬 을 완성 합 니 다.
시간 복잡 도: o (nlgn), 매 번 의 병합 시간 복잡 도 는 o (n) 이 며, 모두 lgn 회 를 병합 해 야 합 니 다.
공간 복잡 도: o (n)
자바 코드 구현:
여기 서 두 가지 버 전 을 사 용 했 습 니 다.
첫 번 째 는 merge 를 직접 신청 할 때마다 공간 을 신청 하고 병합 후의 질서 있 는 결 과 를 저장 한 다음 에 원래 배열 의 대응 구간 으로 복사 하 는 것 이다.
두 번 째 버 전 은 정렬 이 시작 되 기 전에 정렬 대기 배열 등 큰 배열 tempArrays 를 신 청 했 습 니 다. 매번 병합 작업 은 질서정연 한 결 과 를 tempArrays 에 합 친 다음 에 데 이 터 를 원래 배열 의 대응 구간 으로 복사 합 니 다.
전자 에 필요 한 공간 은 o (nlgn) 입 니 다.
후 자 는 o (n) 만 필요 합 니 다.
/**
* @author wangwei
* @date 2019/1/24 15:09
* @classDescription
* : , , , ( )
*
*/
public class MergeSort implements Sortable {
@Override
public void sort(int[] array) {
int []tempArray=new int[array.length];
// mergeSort(array,0,array.length-1);
mergeSort2(array,tempArray,0,array.length-1);
}
void mergeSort(int[] array, int leftPos, int rightPos) {
if(leftPos5. 빠 른 정렬:
두 개의 태그 i 와 j 는 각각 배열 의 양 끝 을 가리킨다.
k 값 을 선택 하여 비교 대상, 중심 을 표시 합 니 다.
목적 은 k 보다 작은 요 소 를 k 의 왼쪽 에 두 고 k 보다 큰 요 소 를 k 의 오른쪽 에 두 는 것 이다.
정렬 대기 배열:
i
j
아래 표
0
1
2
3
4
5
원소
5
4
3
7
2
7
i=0，j=5
k=array[i]=5;
part 1 오른쪽 에서 왼쪽으로 비교:
j = 5 시, array [j] = 7 > k, 교환 하지 않 음
j--；
j = 4 시, array [j] ]=2 교환
현재 배열:
i
j
아래 표
0
1
2
3
4
5
원소
2
4
3
7
5
7
k=array[ j ] =5;
part2 왼쪽 에서 오른쪽으로 비교
이때: i = 0; j = 4
k = 5 > array [i] = 2, 교환 하지 않 음
i++
k = 5 > array [i] = array [1] = 4, 교환 하지 않 음
i++
k = 5 > array [i] = array [2] = 3, 교환 하지 않 음
i++
k = 5 < = array [i] = array [3] = 7, 교환
교환 결과:
i
j
아래 표
0
1
2
3
4
5
원소
2
4
3
5
7
7
이제 오른쪽 에서 왼쪽으로 비교 하고 파 트 1 로 돌아 갑 니 다.
k=array[i]=array[3]=5
k=5
j--
i 와 j 가 만 나 고 k = 5 의 비 교 를 끝 냅 니 다. k = 5 라 는 요소 의 좌우 양측 에 대해 상기 작업 을 각각 수행 합 니 다. part 1 + part 2
첫 번 째 빠 른 배열 의 결과:
i
j
아래 표
0
1
2
3
4
5
원소
2
4
3
5
7
7
수조 1: 2, 4, 3
수조 2: 7, 7
5,4,3,7,2,7,
자바 코드 구현
public void quickSort(int []array,int from,int to){
if(from<0||to>=array.length){
return;
}
if(from>=to){
return;
}
int kVal=array[from];
int kPos=from;
// int kPos=(from+to)/2;
// int kVal=array[kPos];
int low=from;
int high=to;
while(low=kVal ){
high--;
}
// kVal ，
if(high>low ){
array[kPos]=array[high];
// array[high]=kVal;
kPos=high;
low++;
}
// ， kVal
while(low 빠 른 배열 의 최 적 화 는 관건 적 인 선택 이 가능 한 한 중간 에 있 으 면 재 귀 횟수 를 줄 일 수 있다 는 것 이다.
허브 를 선택 하 는 방식:
/**
* @author wangwei
* @date 2019/1/24 18:58
* @classDescription : (" "), , ,
* : 1,4,3,5,6,2
* 3
* :1,2,3,5,6,4
* :
*
*
* : " "
* :1, ( , 1,2,3,4,5,6)
* 2, ( )
* 3, ( )
*
* : ,
*/
public class QuickSort implements Sortable {
@Override
public void sort(int[] array) {
qkSort(array, 0, array.length - 1);
// quickSort(array,0,array.length-1);
}
void qkSort(int[] array, int low, int high) {
if (low >= high) {
return;
}
// ，
// keyPos , ,( )), ( , )
dealPivot(array, low, high);
int keyPos = high - 1;
System.out.println(keyPos);
int keyVal = array[keyPos];
int left = low +1;
int right = high-1;
while (left < right) {
// kVal x1
while ((left < right) && array[left] <= keyVal) {
left++;
}
// kVal x2
// ,
while ((left < right) && array[right] >= keyVal) {
right--;
}
// x1,x2
if (left < right) {
ArrayUtil.swap(array, left, right);
}
}
// left right kVal, ,
if (array[right] > keyVal) {
ArrayUtil.swap(array, right, keyPos);
}
qkSort(array, low, right - 1);
qkSort(array, right + 1, high);
}
// , , ,
private void dealPivot(int[] array, int left, int right) {
// :1 4 2 4 7 3 8 :1, :4, :8 1,4,8 1,4,2,7,3,4,8
int mid = (left + right) / 2;
if (array[mid] > array[right]) {
ArrayUtil.swap(array, mid, right);
}
if (array[left] > array[right]) {
ArrayUtil.swap(array, left, right);
}
if (array[left] > array[mid]) {
ArrayUtil.swap(array, left, mid);
}
ArrayUtil.swap(array, mid, right - 1);
}
요약:
1. 거품 정렬: 매번 왼쪽 에서 오른쪽으로 인접 요소 와 비교 하고 현재 정렬 대기 서열 에서 가장 큰 요 소 를 마지막 으로 교환 합 니 다.
(주의: 매번 하나의 요소 의 정렬 만 완성 하 는 것 이 아니 라 이 번 의 마지막 교환 위치 입 니 다. 다음 정렬 규 모 를 줄 일 수 있 음 을 기억 할 수 있 습 니 다)
2. 정렬 선택: 거품 과 유사 하지만 자주 요 소 를 교환 하지 않 습 니 다. 하나의 공간 으로 현재 정렬 대기 시퀀스 의 최대 치 를 기록 합 니 다. 이 스 캔 이 끝나 면 시퀀스 의 마지막 에 놓 고 정렬 대기 규모 - 1
3. 정렬 삽입: 카드 를 만 지 는 것 보다 입력 규모 가 같은 공간 (신청 하지 않 아 도 되 고 원래 배열 의 논리 적 으로 질서 와 무질서 구간 으로 나 눌 수 있 습 니 다) 을 신청 하여 정렬 된 요 소 를 저장 합 니 다.
4. 병합 정렬: 큰 배열 을 계속 2 분 으로 나 누고 각 질서 있 는 하위 배열 을 질서 있 는 배열 로 분류 하여 최종 적 으로 정렬 을 완성 합 니 다.
5. 빠 른 정렬: 나 누 어 다스 리 는 사상 으로 정렬 합 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
