تصف هذه المقالة عملية اختيار الوقت الخطي التي تنفذها Java استنادًا إلى خوارزمية التقسيم والقهر. شاركه للرجوع إليه ، على النحو التالي:
مشكلة اختيار الوقت الخطي: بالنظر إلى عناصر n و k k ، 1 ≤ K≤N ، من الضروري معرفة أصغر عنصر في هذه العناصر n (المجموعة الخطية المحددة هنا مضطربة).
اختيار خطي مقسمة بشكل عشوائي
يمكن أن تقليد طريقة التقسيم العشوائي للوقت الخطي تصميم خوارزمية الفرز السريع العشوائي. الفكرة الأساسية هي تقسيم مجموعة الإدخال بشكل متكرر. على عكس الفرز السريع ، فإنه يعالج بشكل متكرر واحدة فقط من الطوائف الفرعية المقسمة.
شرح البرنامج: استخدم وظيفة عشوائية لإنشاء معيار تقسيم ، وقسّم المصفوفة A [P: R] إلى اثنين من الطوائف الفرعية A [P: I] و A [I+1: R] ، بحيث لا يكون كل عنصر في [P: I] أكبر من كل عنصر في A [I+1: R]. ثم "J = I-P+1" يحسب عدد العناصر J في A [P: i]. إذا كان k <= j ، فإن عنصر K-th الأصغر في [p: r] هو في المباراة الفرعية A [p: i] ، وإذا كان k> j ، فإن عنصر K-th أصغر في الجهاز الفرعي A [i+1: r]. ملاحظة: نظرًا لأنه من المعروف أن العناصر الموجودة في العائق الفرعي A [P: I] كلها أصغر من العنصر الصغير K-Th ، العنصر الصغير K-Th في [P: R] هو العنصر الصغير K-Th في A [I+1: R].
في أسوأ الحالات ، على سبيل المثال: عندما يتم العثور على أصغر عنصر دائمًا ، يتم تقسيمه دائمًا في أكبر عنصر ، وهو التعقيد الزمني لـ O (n^2) . ومع ذلك ، يرتبط متوسط التعقيد الزمني خطيًا بـ N ، وهو O (N)
حزمة الرياضيات ؛ استيراد java.util.scanner ؛ استيراد java.util.random ؛ الطبقة العامة العشوائية {public static void swap (int x ، int y) {int temp = x ؛ x = y ؛ y = درجة الحرارة ؛ } public int random (int x ، int y) {random random = new random () ؛ int num = random.nextint (y) ٪ (y - x + 1) + x ؛ عودة NUM ؛ } public int partition (int [] list ، int low ، int high) {int tmp = list [low] ؛ . } list [low] = list [High] ؛ // السجلات الأصغر من المحور المركزي يتم نقلها إلى النهاية المنخفضة بينما (Low High && list [low] <TMP) {low ++ ؛ } قائمة [عالية] = قائمة [low] ؛ // يتم نقل السجلات الأكبر من المحور المركزي إلى قائمة الراقية} [low] = TMP ؛ // يتم إرجاع السجلات الأكبر من المحور المركزي. // العودة إلى موضع المحور المركزي} public int randomizedpartition (int [] صفائف ، int اليسار ، int اليمين) {int i = عشوائي (يسار ، يمين) ؛ مبادلة (المصفوفات [i] ، المصفوفات [اليسار]) ؛ إرجاع قسم (المصفوفات ، اليسار ، اليمين) ؛ } public int syndyasedselect (int [] starrays ، int left ، int right ، int k) {if (left == right) {return arrays [left] ؛ } int i = عشوائيات (صفائف ، يسار ، يمين) ؛ int j = i - Left + 1 ؛ if (k <= j) {return randomizedselect (المصفوفات ، اليسار ، i ، k) ؛ } آخر {return randomizedselect (المصفوفات ، i+1 ، يمين ، kj) ؛ }} public static void main (String args []) {system.out.println ("Wulin.com test result:") ؛ int [] a = {7،5،3،4،8،6،9،1،2} ؛ لـ (int i = 0 ؛ i <9 ؛ i ++) {system.out.print (a [i]+"") ؛ } system.out.println () ؛ عشوائي R = new RandomEct () ؛ System.out.println ("ما أصغر عنصر تريد الاستعلام عنه في المصفوفة؟") ؛ suppressWarnings ("Resource") SCANNER SC = NEW SCANNER (System.in) ؛ int m = sc.nextint () ؛ int n = randomizedelect (a ، 0،8 ، m) ؛ system.out.println ("the th" th "في هذه الصفيف" + m + "أصغر عنصر هو:" + n) ؛ }}نتائج التشغيل:
لمزيد من المعلومات حول خوارزميات Java ، يمكن للقراء المهتمين بهذا الموقع عرض الموضوعات: "بنية بيانات Java وبرنامج تعليمي الخوارزمية" ، "ملخص" Tips Java ".
آمل أن يكون هذا المقال مفيدًا لبرمجة Java للجميع.