วิธีใช้การเรียงลำดับบิตแมป Java

คัดลอกรหัสรหัส ดังต่อไปนี้:

-
* ดำเนินการเรียงลำดับในส่วนของอาร์เรย์ระหว่างดัชนีที่กำหนด
* ใช้การผสานกับอัลกอริธึมการค้นหาแบบเอกซ์โปเนนเชียล (ซึ่งในการผสาน
* ดำเนินการโดยการค้นหาแบบเอกซ์โปเนนเชียล) รับประกันประสิทธิภาพ n*log(n)
* และในกรณีโดยเฉลี่ยจะเร็วกว่าการผสานรวมใดๆ ที่
* การผสานทำได้โดยการค้นหาเชิงเส้น
-
* @param ใน -
* อาร์เรย์สำหรับการเรียงลำดับ
* @param ออก -
* ผลลัพธ์ เรียงลำดับอาร์เรย์
* @param start
* ดัชนีเริ่มต้น
* @param สิ้นสุด
* ดัชนีท้าย + 1
-
@SuppressWarnings("ไม่ได้เลือก")
โมฆะคงที่ส่วนตัว mergeSort (วัตถุ [] ใน, วัตถุ [] ออก, เริ่มต้น int,
ตั้งใจ) {
int len ​​u003d สิ้นสุด - เริ่มต้น;
// ใช้การเรียงลำดับการแทรกสำหรับอาร์เรย์ขนาดเล็ก
ถ้า (เลน <= SIMPLE_LENGTH) {
สำหรับ (int i = start + 1; i < end; i++) {
เปรียบเทียบ<วัตถุ> ปัจจุบัน = (เปรียบเทียบ<วัตถุ>) ออก[i];
วัตถุก่อนหน้า = ออก [i - 1];
ถ้า (current.compareTo (ก่อนหน้า) < 0) {
อินท์เจ = ฉัน;
ทำ {
ออก[j--] = ก่อนหน้า;
} ในขณะที่ (j > start
&& current.compareTo(ก่อนหน้า = ออก[j - 1]) < 0);
ออก [j] = ปัจจุบัน;
-
-
กลับ;
-
int med = (จบ + เริ่ม) >>> 1;
MergeSort(ออก, ใน, เริ่มต้น, กลาง);
MergeSort(ออก, ใน, กลาง, สิ้นสุด);

// การรวมตัว

// ถ้าอาร์เรย์ถูกเรียงลำดับแล้ว - ไม่มีการผสาน
if (((เปรียบเทียบได้<Object>) ใน[med - 1]).compareTo(ใน[med]) <= 0) {
System.arraycopy(ใน, เริ่มต้น, ออก, เริ่ม, len);
กลับ;
-
int r = แพทย์, i = เริ่มต้น;

// ใช้การรวมเข้ากับการค้นหาแบบเอกซ์โปเนนเชียล
ทำ {
เปรียบเทียบได้<วัตถุ> fromVal = (เปรียบเทียบ<วัตถุ>) ใน[เริ่มต้น];
เปรียบเทียบ<วัตถุ> rVal = (เปรียบเทียบ<วัตถุ>) ใน[r];
ถ้า (fromVal.compareTo(rVal) <= 0) {
int l_1 = ค้นหา (ใน, rVal, -1, เริ่ม + 1, med - 1);
int toCopy = l_1 - เริ่ม + 1;
System.arraycopy(ใน, เริ่มต้น, ออก, i, toCopy);
ฉัน += เพื่อคัดลอก;
ออก [i++] = rVal;
ร++;
เริ่มต้น = l_1 + 1;
} อื่น {
int r_1 = ค้นหา (ใน, fromVal, 0, r + 1, สิ้นสุด - 1);
int toCopy = r_1 - r + 1;
System.arraycopy(ใน, r, ออก, i, toCopy);
ฉัน += เพื่อคัดลอก;
ออก[i++] = จากVal;
เริ่ม++;
ร = r_1 + 1;
-
} ในขณะที่ ((สิ้นสุด - r) > 0 && (med - เริ่มต้น) > 0);

// คัดลอกส่วนที่เหลือของอาร์เรย์
ถ้า ((จบ - r) <= 0) {
System.arraycopy(ใน, เริ่มต้น, ออก, i, med - เริ่มต้น);
} อื่น {
System.arraycopy(in, r, out, i, end - r);
-
-

คัดลอกรหัสรหัส ดังต่อไปนี้:

คลาสสาธารณะ javaUniqueSort {
int สาธารณะคงที่ [] temp = int ใหม่ [1000001];
รายการคงที่สาธารณะ <Integer> tempList = new ArrayList <Integer>();
จำนวน int คงที่สาธารณะ

โมฆะสาธารณะคงที่หลัก (สตริงสุดท้าย [] args) {
รายการ <จำนวนเต็ม> firstNum = ใหม่ ArrayList<จำนวนเต็ม>();
รายการ <จำนวนเต็ม> SecondNum = ใหม่ ArrayList<จำนวนเต็ม>();

สำหรับ (int i = 1; i <= 1000000; i++) {
firstNum.add(i);
SecondNum.add(i);
-

คอลเลกชัน.สับเปลี่ยน(firstNum);
คอลเลกชัน.สับเปลี่ยน(secondNum);

getStartTime();
Collections.sort(firstNum);
getEndTime("เวลารันการเรียงลำดับ Java ");

getStartTime();
SecondNum = ลำดับที่ไม่ซ้ำ (secondNum);
getEndTime("เวลารันการเรียงลำดับเฉพาะ");

-

รายการคงที่สาธารณะ <Integer> UniqueSort (รายการสุดท้าย <Integer> UniqueList) {
javaUniqueSort.tempList.clear();
สำหรับ (int i = 0; i < javaUniqueSort.temp.length; i++) {
javaUniqueSort.temp[i] = 0;
-
สำหรับ (int i = 0; i < UniqueList.size(); i++) {
javaUniqueSort.temp[uniqueList.get(i)] = 1;
-
สำหรับ (int i = 0; i < javaUniqueSort.temp.length; i++) {
ถ้า (javaUniqueSort.temp[i] == 1) {
javaUniqueSort.tempList.add(i);
-
-

กลับ javaUniqueSort.tempList;
-

โมฆะสาธารณะคงที่ getStartTime () {
javaShuffle.start = System.nanoTime();
-

โมฆะสาธารณะคงที่ getEndTime (สตริงสุดท้าย) {
javaShuffle.end = System.nanoTime();
System.out.println(s + ": " + (javaShuffle.end - javaShuffle.start) + "ns");
-
-

เวลาทำงาน:

เวลารันการเรียงลำดับ Java: 1257737334ns
เวลารันการเรียงลำดับที่ไม่ซ้ำกัน: 170228290ns
เวลารันการเรียงลำดับ Java: 1202749828ns
เวลารันการเรียงลำดับที่ไม่ซ้ำกัน: 169327770ns

คัดลอกรหัสรหัส ดังต่อไปนี้:

คลาสสาธารณะ javaDuplicateSort {
รายการคงที่สาธารณะ <Integer> tempList = new ArrayList <Integer>();
จำนวน int คงที่สาธารณะ

โมฆะคงที่สาธารณะหลัก (สตริงสุดท้าย [] args) {
สุ่ม สุ่ม = สุ่มใหม่();
รายการ <จำนวนเต็ม> firstNum = ใหม่ ArrayList<จำนวนเต็ม>();
รายการ <จำนวนเต็ม> SecondNum = ใหม่ ArrayList<จำนวนเต็ม>();

สำหรับ (int i = 1; i <= 100000; i++) {
firstNum.add(i);
SecondNum.add(i);
firstNum.add(random.nextInt(i + 1));
SecondNum.add(random.nextInt(i + 1));
-
คอลเลกชัน.สับเปลี่ยน(firstNum);
คอลเลกชัน.สับเปลี่ยน(secondNum);

getStartTime();
Collections.sort(firstNum);
getEndTime("เวลารันการเรียงลำดับ Java ");

getStartTime();
SecondNum = ลำดับที่ไม่ซ้ำ (secondNum);
getEndTime("เวลารันการเรียงลำดับเฉพาะ");

-

รายการคงที่สาธารณะ <Integer> UniqueSort (รายการสุดท้าย <Integer> UniqueList) {
javaDuplicateSort.tempList.clear();
int[] temp = ใหม่ int[200002];
สำหรับ (int i = 0; i < temp.length; i++) {
อุณหภูมิ[i] = 0;
-
สำหรับ (int i = 0; i < UniqueList.size(); i++) {
อุณหภูมิ[uniqueList.get(i)]++;
-
สำหรับ (int i = 0; i < temp.length; i++) {
สำหรับ (int j = temp[i]; j > 0; j--) {
javaDuplicateSort.tempList.add(i);
-
-

กลับ javaDuplicateSort.tempList;
-

โมฆะสาธารณะคงที่ getStartTime () {
javaShuffle.start = System.nanoTime();
-

โมฆะสาธารณะคงที่ getEndTime (สตริงสุดท้าย) {
javaShuffle.end = System.nanoTime();
System.out.println(s + ": " + (javaShuffle.end - javaShuffle.start) + "ns");
-
-