كيفية استخدام فرز الصور النقطية في جافا

انسخ رمز الكود كما يلي:

/**
* إجراء فرز على قسم المصفوفة بين الفهارس المحددة
* استخدام فرز الدمج مع خوارزمية البحث الأسي (حيث يتم دمج
* يتم تنفيذه عن طريق البحث الأسي). أداء n*log(n) مضمون
* وفي الحالة المتوسطة سيكون أسرع من أي عملية فرز يتم فيها دمج
* يتم إجراء الدمج عن طريق البحث الخطي.
*
* @param في -
* المصفوفة للفرز.
* @param خارج -
* النتيجة، مجموعة مرتبة.
* @param البداية
* مؤشر البداية
* @param نهاية
*مؤشر النهاية +1
*/
@SuppressWarnings("تم إلغاء التحديد")
دمج الفراغ الثابت الخاص (Object[] in، Object[] out، int start،
ينوي) {
int len ​​= النهاية - البداية؛
// استخدم فرز الإدراج للمصفوفات الصغيرة
إذا (لين <= SIMPLE_LENGTH) {
لـ (int i = start + 1; i < end; i++) {
Comparable<Object> current = (Comparable<Object>) out[i];
الكائن السابق = خارج[i - 1];
إذا (current.compareTo(السابق) < 0) {
كثافة العمليات ي = أنا؛
يفعل {
out[j--] = prev;
} بينما (j > start
&& current.compareTo(prev = out[j - 1]) < 0);
خارج[ي] = الحالي؛
}
}
يعود؛
}
int med = (النهاية + البداية) >>> 1;
mergeSort(out, in, start, med);
mergeSort(out, in, med, end);

// دمج

// إذا كانت المصفوفات مرتبة بالفعل - فلا داعي للدمج
إذا (((Comparable<Object>) in[med - 1]).compareTo(in[med]) <= 0) {
System.arraycopy(in, start, out, start, len);
يعود؛
}
int r = med, i = start;

// استخدم الدمج مع البحث الأسي
يفعل {
Comparable<Object> fromVal = (Comparable<Object>) in[start];
Comparable<Object> rVal = (Comparable<Object>) in[r];
إذا (fromVal.compareTo(rVal) <= 0) {
int l_1 = find(in, rVal, -1, start + 1, med - 1);
int toCopy = l_1 - start + 1;
System.arraycopy(in, start, out, i, toCopy);
i += toCopy;
out[i++] = rVal;
ص++;
البداية = 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;
out[i++] = fromVal;
ابدأ++;
ص = r_1 + 1؛
}
} while ((end - r) > 0 && (med - start) > 0);

// انسخ بقية المصفوفة
إذا ((النهاية - ص) <= 0) {
System.arraycopy(in, start, out, i, med - start);
} آخر {
System.arraycopy(in, r, out, i, end - r);
}
}

انسخ رمز الكود كما يلي:

فئة عامة جافاUniqueSort {
public static int[] temp = new int[1000001];
public static List<Integer> tempList = new ArrayList<Integer>();
عدد كثافة العمليات الثابت العام؛

public static void main(final String[] args) {
List<Integer> firstNum = new ArrayList<Integer>();
List<Integer> SecondNum = new ArrayList<Integer>();

لـ (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 = UniqueSort( SecondNum);
getEndTime("وقت التشغيل الفريد");

}

قائمة ثابتة عامة<Integer> UniqueSort(القائمة النهائية<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++) {
إذا (javaUniqueSort.temp[i] == 1) {
javaUniqueSort.tempList.add(i);
}
}

إرجاع javaUniqueSort.tempList؛
}

الفراغ الثابت العام getStartTime() {
javaShuffle.start = System.nanoTime();
}

public static void getEndTime(final String s) {
javaShuffle.end = System.nanoTime();
System.out.println(s + ": " + (javaShuffle.end - javaShuffle.start) + "ns");
}
}

وقت التشغيل:

وقت تشغيل فرز جافا: 1257737334ns
وقت التشغيل الفريد للفرز: 170228290ns
وقت تشغيل فرز جافا: 1202749828ns
وقت التشغيل الفريد للفرز: 169327770ns

انسخ رمز الكود كما يلي:

فئة عامة جافادوبليكاتيسورت {
public static List<Integer> tempList = new ArrayList<Integer>();
عدد كثافة العمليات الثابت العام؛

public static void main(final String[] args) {
عشوائي عشوائي = عشوائي جديد ()؛
List<Integer> firstNum = new ArrayList<Integer>();
List<Integer> SecondNum = new ArrayList<Integer>();

لـ (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 = UniqueSort( SecondNum);
getEndTime("وقت التشغيل الفريد");

}

قائمة ثابتة عامة<Integer> UniqueSort(القائمة النهائية<Integer> UniqueList) {
javaDuplicateSort.tempList.clear();
int[] temp = new int[200002];
لـ (int i = 0; i < temp.length; i++) {
درجة الحرارة[i] = 0;
}
for (int i = 0; i < UniqueList.size(); i++) {
temp[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();
}

public static void getEndTime(final String s) {
javaShuffle.end = System.nanoTime();
System.out.println(s + ": " + (javaShuffle.end - javaShuffle.start) + "ns");
}
}