تحليل متعمق لإعادة ترتيب المصفوفة (كيفية وضع جميع الأرقام الفردية قبل جميع الأرقام الزوجية)

نقدم هنا خوارزمية فعالة يمكن إكمالها خلال التعقيد الزمني O(n).

الفكرة الأساسية هي: تحديد مؤشرين، يقوم مؤشر واحد بمسح من الأمام إلى الخلف، ومؤشر واحد ب بمسح من الخلف إلى الأمام. يقوم المؤشر A بالمسح إلى رقم زوجي ويتوقف مؤقتًا، ويقوم المؤشر B بالمسح إلى رقم فردي ويتوقف مؤقتًا، ثم يتبادل الرقمين بعد التبادل، استمر في المسح والتبادل كما هو مذكور أعلاه حتى يتطابق المؤشر A والمؤشر B ويتوقفان.

رمز Java لهذه الخوارزمية هو كما يلي:

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

إعادة ترتيب الحزمة؛

إعادة ترتيب الطبقة العامة {

public static void main(String[] args) {

قائمة int[] = { 1, 2, 3, 4, 5, 7, 9, 11 };

reorderOddEven(list);

}

إعادة ترتيب الفراغ الثابت العام (قائمة int[]) {

int length = list.length;

لـ (int i = 0; i < length; i++) {

System.out.print(list[i] + " ");

}

System.out.print("/n");

كثافة العمليات تبدأ = 0؛

نهاية كثافة العمليات = الطول - 1؛

بينما (البدء <النهاية) {

بينما (بدء < نهاية && (قائمة [بدء] & 0x1) ! = 0)

ابدأ++;

بينما (البداية < النهاية && (القائمة[النهاية] & 0x1) == 0)

نهاية--؛

إذا (البدء <النهاية) {

int temp = list[begin];

قائمة[بدء] = قائمة[نهاية];

list[end] = temp;

}

}

لـ (int i = 0; i < length; i++) {

System.out.print(list[i] + " ");

}

}

}