Java 비트맵 정렬을 사용하는 방법

다음과 같이 코드 코드를 복사합니다 .

/**
* 주어진 인덱스 사이의 배열 섹션에 대해 정렬을 수행합니다.
* 지수 검색 알고리즘을 사용하는 병합 정렬 사용(여기서 병합은
* 지수 검색으로 수행됨) n*log(n) 성능이 보장됩니다.
* 그리고 평균적인 경우에는 병합 정렬보다 더 빠릅니다.
* 병합은 선형 검색으로 수행됩니다.
*
* @param in -
* 정렬을 위한 배열.
* @param 출력 -
* 결과, 정렬된 배열.
* @param 시작
* 시작 인덱스
* @param 끝
* 끝 인덱스 + 1
*/
@SuppressWarnings("선택 해제됨")
private static void mergeSort(Object[] in, Object[] out, int start,
의도하다) {
int len ​​​​= 끝 - 시작;
// 작은 배열에는 삽입 정렬을 사용합니다.
if (len <= SIMPLE_LENGTH) {
for (int i = 시작 + 1; i < 끝; i++) {
Comparable<Object> 현재 = (Comparable<Object>) out[i];
객체 prev = out[i - 1];
if (current.compareTo(prev) < 0) {
int j = i;
하다 {
out[j--] = 이전;
} 동안 (j > 시작
&& current.compareTo(prev = out[j - 1]) < 0);
출력[j] = 현재;
}
}
반품;
}
int med = (끝 + 시작) >>> 1;
mergeSort(아웃, 인, 시작, med);
mergeSort(아웃, 인, 메드, 엔드);

// 병합

// 배열이 이미 정렬되어 있는 경우 - 병합하지 않음
if (((Comparable<Object>) in[med - 1]).compareTo(in[med]) <= 0) {
System.arraycopy(in, start, out, start, len);
반품;
}
int r = med, i = 시작;

// 지수 검색과 병합을 사용합니다.
하다 {
Comparable<Object> fromVal = (Comparable<Object>) in[start];
Comparable<Object> rVal = (Comparable<Object>) in[r];
if (fromVal.compareTo(rVal) <= 0) {
int l_1 = find(in, rVal, -1, start + 1, med - 1);
int toCopy = l_1 - 시작 + 1;
System.arraycopy(in, start, out, i, toCopy);
i += toCopy;
아웃[i++] = rVal;
r++;
시작 = l_1 + 1;
} 또 다른 {
int r_1 = find(in, fromVal, 0, r + 1, end - 1);
int toCopy = r_1 - r + 1;
System.arraycopy(in, r, out, i, toCopy);
i += toCopy;
아웃[i++] = fromVal;
시작++;
r = r_1 + 1;
}
} while ((end - r) > 0 && (med - start) > 0);

// 나머지 배열 복사
if ((end - r) <= 0) {
System.arraycopy(in, start, out, i, med - 시작);
} 또 다른 {
System.arraycopy(in, r, out, i, end - r);
}
}

다음과 같이 코드 코드를 복사합니다 .

공개 클래스 javaUniqueSort {
공개 정적 int[] 임시 = 새로운 int[1000001];
공개 정적 List<Integer> tempList = new ArrayList<Integer>();
공개 정적 정수 개수;

공개 정적 무효 메인(최종 문자열[] 인수) {
List<Integer> firstNum = new ArrayList<Integer>();
List<Integer> secondNum = new ArrayList<Integer>();

for (int i = 1; i <= 1000000; i++) {
firstNum.add(i);
secondNum.add(i);
}

Collections.shuffle(firstNum);
Collections.shuffle(secondNum);

getStartTime();
Collections.sort(firstNum);
getEndTime("java 정렬 런타임");

getStartTime();
secondNum = 고유정렬(secondNum);
getEndTime("uniqueSort 런타임");

}

공개 정적 List<Integer> UniqueSort(최종 List<Integer> UniqueList) {
javaUniqueSort.tempList.clear();
for (int i = 0; i < javaUniqueSort.temp.length; i++) {
javaUniqueSort.temp[i] = 0;
}
for (int i = 0; i < UniqueList.size(); i++) {
javaUniqueSort.temp[uniqueList.get(i)] = 1;
}
for (int i = 0; i < javaUniqueSort.temp.length; i++) {
if (javaUniqueSort.temp[i] == 1) {
javaUniqueSort.tempList.add(i);
}
}

javaUniqueSort.tempList를 반환합니다.
}

공개 정적 무효 getStartTime() {
javaShuffle.start = System.nanoTime();
}

공개 정적 무효 getEndTime(최종 문자열 s) {
javaShuffle.end = System.nanoTime();
System.out.println(s + ": " + (javaShuffle.end - javaShuffle.start) + "ns");
}
}

실행 시간:

자바 정렬 런타임: 1257737334ns
UniqueSort 런타임: 170228290ns
자바 정렬 런타임: 1202749828ns
UniqueSort 런타임: 169327770ns

다음과 같이 코드 코드를 복사합니다 .

공개 클래스 javaDuplicateSort {
public static List<Integer> tempList = new ArrayList<Integer>();
공개 정적 정수 개수;

공개 정적 무효 메인(최종 문자열[] 인수) {
무작위 무작위 = 새로운 무작위();
List<Integer> firstNum = new ArrayList<Integer>();
List<Integer> secondNum = new ArrayList<Integer>();

for (int i = 1; i <= 100000; i++) {
firstNum.add(i);
secondNum.add(i);
firstNum.add(random.nextInt(i + 1));
secondNum.add(random.nextInt(i + 1));
}
Collections.shuffle(firstNum);
Collections.shuffle(secondNum);

getStartTime();
Collections.sort(firstNum);
getEndTime("java 정렬 런타임");

getStartTime();
secondNum = 고유정렬(secondNum);
getEndTime("uniqueSort 런타임");

}

공개 정적 List<Integer> UniqueSort(최종 List<Integer> UniqueList) {
javaDuplicateSort.tempList.clear();
int[] 임시 = 새로운 int[200002];
for (int i = 0; i < temp.length; i++) {
온도[i] = 0;
}
for (int i = 0; i < UniqueList.size(); i++) {
임시[uniqueList.get(i)]++;
}
for (int i = 0; i < temp.length; i++) {
for (int j = temp[i]; j > 0; j--) {
javaDuplicateSort.tempList.add(i);
}
}

javaDuplicateSort.tempList를 반환합니다.
}

공개 정적 무효 getStartTime() {
javaShuffle.start = System.nanoTime();
}

공개 정적 무효 getEndTime(최종 문자열 s) {
javaShuffle.end = System.nanoTime();
System.out.println(s + ": " + (javaShuffle.end - javaShuffle.start) + "ns");
}
}