import java.util.Random;
/**
* فرز فئة الاختبار
*
* تصنيف خوارزميات الفرز كما يلي: 1. الفرز بالإدراج (فرز الإدراج المباشر، فرز الإدراج النصفي، فرز التل)؛ 2. الفرز التبادلي (فرز الفقاعة، الفرز السريع)؛
* 3. فرز التحديد (فرز التحديد المباشر، فرز الكومة)؛ 4. فرز الدمج؛
*
* فيما يتعلق باختيار طريقة الفرز: (1) إذا كانت n صغيرة (مثل n≥50)، فيمكن استخدام الإدراج المباشر أو الفرز بالاختيار المباشر.
* عندما يكون حجم السجل صغيرًا، يكون الفرز بالإدراج المباشر أفضل، وإلا، نظرًا لأن عدد السجلات المنقولة عن طريق التحديد المباشر أقل من عدد السجلات التي يتم نقلها عن طريق الإدراج المباشر، فإن الفرز بالتحديد المباشر يكون أفضل.
* (2) إذا كانت الحالة الأولية للملف مرتبة بشكل أساسي (بالإشارة إلى الترتيب الإيجابي)، فيجب استخدام الإدراج المباشر أو الفقاعة أو الفرز السريع العشوائي؛
* (3) إذا كانت n كبيرة، فيجب استخدام طريقة فرز ذات تعقيد زمني O(nlgn): فرز سريع أو فرز كومة أو فرز دمج.
*
*/
فرز الطبقة العامة {
/**
* طريقة لتهيئة مجموعة الاختبار
*
* @return مصفوفة تمت تهيئتها
*/
كثافة العمليات العامة[] createArray() {
عشوائي عشوائي = عشوائي جديد ()؛
int[] array = new int[10];
لـ (int i = 0; i < 10; i++) {
array[i] = Random.nextInt(100) - Random.nextInt(100); // أنشئ رقمين عشوائيين واطرحهما للتأكد من وجود أرقام سالبة في الأرقام التي تم إنشاؤها.
}
System.out.println("===================================================================================================================================================================================================================System.
printArray(array);
مصفوفة العودة؛
}
/**
* طباعة العناصر الموجودة في المصفوفة إلى وحدة التحكم
*
* @param المصدر
*/
طباعة الفراغ العام (int [] data) {
لـ (int i: البيانات) {
System.out.print(i + " ");
}
System.out.println();
}
/**
* تبادل مواضع العنصرين المحددين في المصفوفة
*
* @param data
* @paramx
* @param ي
*/
مبادلة باطلة خاصة (int [] data، int x، int y) {
int temp = data[x];
البيانات[x] = البيانات[y];
data[y] = temp;
}
/**
* فرز الفقاعة ---- نوع من فرز التبادل
* الطريقة: مقارنة عنصرين متجاورين واستبدالهما إذا لزم الأمر بعد انتهاء كل دورة، يتم ترتيب العنصر الأكبر في المرتبة الأخيرة (مثل الفرز من الأصغر إلى الأكبر) ستقوم الدورة التالية بإجراء عمليات مماثلة على الأرقام الأخرى.
* الأداء: عدد المقارنات O(n^2),n^2/2; عدد التبادلات O(n^2),n^2/4
*
* @param data
* المصفوفة المراد فرزها
* @param نوع الفرز
* نوع الفرز
* @يعود
*/
public void bubbleSort(int[] data, StringsortType) {
if (sortType.equals("asc")) { // فرز إيجابي، من الصغير إلى الكبير
// عدد جولات المقارنة
لـ (int i = 1; i < data. length; i++) {
// قارن بين رقمين متجاورين، وسيظهر الرقم الأكبر.
for (int j = 0; j < data.length - i; j++) {
إذا (البيانات[ي] > البيانات[ي + 1]) {
// مبادلة رقمين متجاورين
مبادلة(بيانات، ي، ي + 1)؛
}
}
}
} else if (sortType.equals("desc")) { // فرز بترتيب عكسي، من الأكبر إلى الأصغر
// عدد جولات المقارنة
لـ (int i = 1; i < data. length; i++) {
// قارن بين رقمين متجاورين، وسيظهر الرقم الأكبر.
for (int j = 0; j < data.length - i; j++) {
إذا (البيانات[ي] < البيانات[ي + 1]) {
// مبادلة رقمين متجاورين
مبادلة(بيانات، ي، ي + 1)؛
}
}
}
} آخر {
System.out.println("نوع الفرز الذي أدخلته خاطئ!");
}
printArray(data);// إخراج قيمة المصفوفة بعد فرز الفقاعات
}
/**
* طريقة الفرز بالاختيار المباشر ---- نوع من الفرز بالاختيار
* الطريقة: في كل تمريرة، يتم تحديد العنصر الأصغر (أو الأكبر) من عناصر البيانات المراد فرزها، ويتم وضع الترتيب في نهاية المصفوفة التي تم فرزها حتى يتم ترتيب جميع عناصر البيانات المراد فرزها.
* الأداء: عدد المقارنات O(n^2),n^2/2
* عدد التبادلات O(n),n
* عدد التبادلات أقل بكثير من فرز الفقاعات، نظرًا لأن التبادل يتطلب وقتًا أطول لوحدة المعالجة المركزية مقارنة بالمقارنة، فإن فرز التحديد أسرع من فرز الفقاعات.
* ولكن عندما يكون N كبيرًا نسبيًا، فإن وقت وحدة المعالجة المركزية المطلوب للمقارنة هو السائد، وبالتالي فإن الأداء في هذا الوقت لا يختلف كثيرًا عن أداء نوع الفقاعة، ولكنه بلا شك أسرع.
*
* @param data
* المصفوفة المراد فرزها
* @param نوع الفرز
* نوع الفرز
* @يعود
*
*/
تحديد الفراغ العام (int [] data، StringsortType) {
if (sortType.equals("asc")) { // فرز إيجابي، من الصغير إلى الكبير
مؤشر كثافة العمليات؛
لـ (int i = 1; i < data. length; i++) {
الفهرس = 0؛
for (int j = 1; j <= data. length - i; j++) {
إذا (البيانات[ي]> البيانات[الفهرس]) {
مؤشر = ي؛
}
}
// قم بتبديل الرقمين في الموضع data.length-i والفهرس (القيمة القصوى)
مبادلة (بيانات، طول البيانات - ط، فهرس)؛
}
} else if (sortType.equals("desc")) { // فرز بترتيب عكسي، من الأكبر إلى الأصغر
مؤشر كثافة العمليات؛
لـ (int i = 1; i < data. length; i++) {
الفهرس = 0؛
for (int j = 1; j <= data. length - i; j++) {
إذا (البيانات [ي] < البيانات [الفهرس]) {
مؤشر = ي؛
}
}
// قم بتبديل الرقمين في الموضع data.length-i والفهرس (القيمة القصوى)
مبادلة (بيانات، طول البيانات - ط، فهرس)؛
}
} آخر {
System.out.println("نوع الفرز الذي أدخلته خاطئ!");
}
printArray(data);// إخراج قيمة المصفوفة بعد فرز التحديد المباشر
}
/**
*
* نوع الإدراج
*
* الطريقة: إدراج سجل في قائمة مرتبة مرتبة (ربما قائمة فارغة)، وبالتالي الحصول على قائمة مرتبة جديدة مع زيادة عدد السجلات بمقدار 1.
* الأداء: عدد المقارنات O(n^2),n^2/4
* عدد النسخ O(n),n^2/4
* عدد المقارنات متوسط بين الأولين، ويتطلب النسخ وقتًا أقل لوحدة المعالجة المركزية مقارنة بالتبديل، وبالتالي فإن الأداء أكثر من ضعف أداء فرز الفقاعات وأسرع من فرز التحديد.
*
* @param data
* المصفوفة المراد فرزها
* @param نوع الفرز
* نوع الفرز
*/
إدراج الفراغ العام (int [] data، StringsortType) {
if (sortType.equals("asc")) { // فرز إيجابي، من الصغير إلى الكبير
// عدد جولات المقارنة
لـ (int i = 1; i < data. length; i++) {
// تأكد من فرز أرقام i+1 الأولى
لـ (int j = 0; j < i; j++) {
إذا (البيانات[ي] > البيانات[i]) {
// قم بتبديل الرقمين في الموضعين j وi
مبادلة (البيانات، ط، ي)؛
}
}
}
} else if (sortType.equals("desc")) { // فرز بترتيب عكسي، من الأكبر إلى الأصغر
// عدد جولات المقارنة
لـ (int i = 1; i < data. length; i++) {
// تأكد من فرز أرقام i+1 الأولى
لـ (int j = 0; j < i; j++) {
إذا (البيانات[ي] < البيانات[i]) {
// قم بتبديل الرقمين في الموضعين j وi
مبادلة (البيانات، ط، ي)؛
}
}
}
} آخر {
System.out.println("نوع الفرز الذي أدخلته خاطئ!");
}
printArray(data);// إخراج قيمة الصفيف بعد فرز الإدراج
}
/**
*
* طريقة لعكس مجموعة
*
* @param data
* مصفوفة المصدر
*/
عكس الفراغ العام (بيانات int []) {
int length = data. length;
int temp = 0;// متغير مؤقت
لـ (int i = 0; i < length / 2; i++) {
درجة الحرارة = البيانات[i];
data[i] = data[length - 1 - i];
البيانات [الطول - 1 - i] = درجة الحرارة؛
}
printArray(data);// إخراج القيمة إلى المصفوفة المحولة
}
/**
*
* فرز سريع
*
* يستخدم الفرز السريع استراتيجية فرق تسد لتقسيم تسلسل (قائمة) إلى تسلسلين فرعيين (قوائم فرعية).
*
*الخطوات هي:
* 1. اختر عنصرًا من التسلسل يسمى "المحور"،
* 2. أعد ترتيب التسلسل بحيث يتم وضع جميع العناصر الأصغر من القيمة الأساسية أمام القاعدة، ويتم وضع جميع العناصر الأكبر من القيمة الأساسية خلف القاعدة (يمكن وضع نفس الرقم على كلا الجانبين). وبعد هذا الانقسام، يكون المسند في موضعه النهائي. وهذا ما يسمى عملية التقسيم.
* 3. قم بفرز المصفوفة الفرعية للعناصر الأصغر من القيمة الأساسية بشكل متكرر والمصفوفة الفرعية للعناصر الأكبر من القيمة الأساسية.
*
* الحالة السفلية للتكرار هي عندما يكون حجم المصفوفة صفرًا أو واحدًا، أي أنه تم فرزها دائمًا. على الرغم من استمرارها في التكرار، إلا أن هذه الخوارزمية ستنتهي دائمًا، لأنها في كل تكرار (تكرار)، ستنقل عنصرًا واحدًا على الأقل إلى موضعه النهائي.
*
* @param data
* المصفوفة المراد فرزها
* @param منخفض
* @param عالي
* @انظر SortTest#qsort(int[], int, int)
* @انظر SortTest#qsort_desc(int[], int, int)
*
*/
فرز سريع باطل عام (int [] data، StringsortType) {
if (sortType.equals("asc")) { // فرز إيجابي، من الصغير إلى الكبير
qsort_asc(data, 0, data. length - 1);
} else if (sortType.equals("desc")) { // فرز بترتيب عكسي، من الأكبر إلى الأصغر
qsort_desc(data, 0, data. length - 1);
} آخر {
System.out.println("نوع الفرز الذي أدخلته خاطئ!");
}
}
/**
*
* تنفيذ محدد للفرز السريع والفرز بالترتيب الصحيح
*
* @param data
* @param منخفض
* @param عالي
*/
qsort_asc باطلة خاصة (بيانات int []، int low، int High) {
إنت ط، ي، س؛
if (low < High) { // يُستخدم هذا الشرط لإنهاء التكرار
أنا = منخفض؛
ي = عالي؛
x = البيانات[i];
بينما (ط < ي) {
بينما (i < j && data[j] > x) {
j--; // ابحث عن الرقم الأول الأقل من x من اليمين إلى اليسار
}
إذا (أنا <ي) {
data[i] = data[j];
أنا++;
}
بينما (i < j && data[i] < x) {
i++; // ابحث عن الرقم الأول الأكبر من x من اليسار إلى اليمين
}
إذا (أنا <ي) {
البيانات[ي] = البيانات[i];
ي--؛
}
}
البيانات[i] = x;
qsort_asc(data, low, i - 1);
qsort_asc(data, i + 1, High);
}
}
/**
*
* تنفيذ محدد للفرز السريع، والفرز بترتيب عكسي
*
* @param data
* @param منخفض
* @param عالي
*
*/
qsort_desc باطلة خاصة (بيانات int []، int low، int High) {
إنت ط، ي، س؛
if (low < High) { // يُستخدم هذا الشرط لإنهاء التكرار
أنا = منخفض؛
ي = عالي؛
x = البيانات[i];
بينما (ط < ي) {
بينما (i < j && data[j] < x) {
j--; // ابحث عن الرقم الأول الأقل من x من اليمين إلى اليسار
}
إذا (أنا <ي) {
data[i] = data[j];
أنا++;
}
بينما (i < j && data[i] > x) {
i++; // ابحث عن الرقم الأول الأكبر من x من اليسار إلى اليمين
}
إذا (أنا <ي) {
البيانات[ي] = البيانات[i];
ي--؛
}
}
البيانات[i] = x;
qsort_desc(data, low, i - 1);
qsort_desc(data, i + 1, High);
}
}
/**
*
* البحث الثنائي عن موضع عدد صحيح محدد في مصفوفة أعداد صحيحة (متكرر)
*
* يجب أن تكون قائمة البحث الخطية قائمة مرتبة
*
* @paramdataset
* @paramdata
* @parambeginIndex
* @paramendIndex
* @returnindex
*
*/
عام int ثنائي البحث (int [] dataset، int data، int beginIndex،int endIndex) {
int midIndex = (beginIndex + endIndex) >>> 1; // يعادل منتصف = (منخفض + مرتفع)
// / 2، ولكن الكفاءة ستكون أعلى
إذا (البيانات < مجموعة البيانات [beginIndex] || البيانات > مجموعة البيانات [endIndex] || beginIndex > endIndex)
العودة -1؛
إذا (البيانات < مجموعة البيانات [ميديندكس]) {
إرجاع البحث الثنائي (مجموعة البيانات، البيانات، BeginIndex، midIndex - 1)؛
} else if (data > dataset[midIndex]) {
إرجاع البحث الثنائي (مجموعة البيانات، البيانات، midIndex + 1، endIndex)؛
} آخر {
إرجاع الفهرس المتوسط؛
}
}
/**
*
* البحث الثنائي عن موضع عدد صحيح محدد في مصفوفة أعداد صحيحة (غير عودي)
*
* يجب أن تكون قائمة البحث الخطية قائمة مرتبة
*
* @paramdataset
* @paramdata
* @returnindex
*
*/
البحث الثنائي العام (int [] dataset، int data) {
int beginIndex = 0;
int endIndex = dataset. length - 1;
int midIndex = -1;
إذا (البيانات < مجموعة البيانات [beginIndex] || البيانات > مجموعة البيانات [endIndex] || beginIndex > endIndex)
العودة -1؛
بينما (beginIndex <= endIndex) {
midIndex = (beginIndex + endIndex) >>> 1; // يعادل midIndex =
// (beginIndex +
// endIndex) / 2، ولكن الكفاءة ستكون أعلى
إذا (البيانات < مجموعة البيانات [ميديندكس]) {
endIndex = midIndex - 1;
} وإلا إذا (بيانات > مجموعة البيانات[ميديندكس]) {
beginIndex = midIndex + 1;
} آخر {
إرجاع الفهرس المتوسط؛
}
}
العودة -1؛
}
public static void main(String[] args) {
فرزsortTest = new Sort();
int[] array =sortTest.createArray();
System.out.println("==========بعد فرز الفقاعة (ترتيب إيجابي)===================================================================================================================================================================================================================================================================System_out
SortTest.bubbleSort(array, "asc");
System.out.println("========== بعد فرز الفقاعة (ترتيب عكسي)==========================================================================================================================================================================================================>
sortTest.bubbleSort(array, "desc");
المصفوفة =sortTest.createArray();
System.out.println("========== بعد عكس المصفوفة==========");
SortTest.reverse(array);
المصفوفة =sortTest.createArray();
System.out.println ("=========== بعد اختيار فرز (ترتيب إيجابي) ==========") ؛
sortTest.selectSort(array, "asc");
System.out.println("========== بعد الفرز بالاختيار (ترتيب عكسي)=========================================================================================================================================================================================================================================== في
sortTest.selectSort(array, "desc");
المصفوفة =sortTest.createArray();
System.out.println("==========الفرز بعد الإدراج (تسلسل إيجابي)==================================================================================================================================================================================================================================================System_out_print في
sortTest.insertSort(array, "asc");
System.out.println("========== الفرز بعد الإدراج (ترتيب عكسي)======================================================================================================================================================================================================>
sortTest.insertSort(array, "desc");
المصفوفة =sortTest.createArray();
System.out.println("========== بعد الفرز السريع (ترتيب إيجابي)===============================================================================================================================================================================================================================System_out
sortTest.quickSort(array, "asc");
printArray(array);
System.out.println("========== بعد الفرز السريع (ترتيب عكسي)===========================================System.out.
sortTest.quickSort(array, "desc");
printArray(array);
System.out.println("==========البحث الثنائي في المصفوفة=====================================================================================================================================================================
System.out.println("الرقم الذي تبحث عنه موجود" +sortTest.binarySearch(array, 74)
+ "المقاعد. (المنخفض يُحسب من 0)");
}
}