مقدمة لمبادئ الفرز السريع
الفرز السريع هو ترقية لفرز الفقاعة الذي تعلمناه من قبل. ينتميون جميعًا إلى فرز المبادلة ، ويستخدمون جميعًا مقارنة مستمرة وحركة لتحقيق الفرز. الفرز السريع هو خوارزمية فرز فعالة للغاية. يزيد تنفيذها من المسافة بين المقارنة وحركة السجلات ، وينقل السجلات بكلمات رئيسية أكبر مباشرة من الأمام إلى الخلف ، والسجلات بكلمات رئيسية أصغر مباشرة من الخلف إلى الأمام ، مما يقلل من إجمالي عدد المقارنات والحركات. في الوقت نفسه ، تم اعتماد فكرة "القسمة والقهر" لتقسيم الكبير إلى صغير ، والصغيرة إلى أصغر. المبدأ هو كما يلي: بالنسبة لمجموعة معينة من السجلات ، حدد عنصرًا قياسيًا ، وعادةً ما يتم تحديد العنصر الأول أو العنصر الأخير ، ومن خلال الفحص ، يتم تقسيم التسلسل المراد فرزه إلى جزأين ، وجزء أصغر من العنصر القياسي ، وجزء أكبر من أو يساوي العنصر القياسي. في هذا الوقت ، يكون العنصر القياسي في الموضع الصحيح بعد فرزه ، ثم يتم فرز الجزأين بشكل متكرر بنفس الطريقة حتى يتم طلب جميع السجلات في التسلسل.
1. أصغر عدد من ك
أدخل أرقام N للعثور على أصغر أرقام K ، على سبيل المثال ، أدخل 4،5،1،6،2،7،3،8 ، وأصغر عدد هو 1،2،3،4
بناءً على O (n) ، يمكن حل هذه المشكلة باستخدام وظيفة Partion. إذا تم ضبط الرقم KTH من الصفيف على أساس رقم KTH ، بحيث توجد جميع الأرقام الأصغر من رقم KTH على يسار الصفيف ، وجميع الأرقام أكبر من صفيف KTH موجودة على يمين الصفيف. بعد التعديل ، تكون أرقام K على يسار الصفيف هي أصغر أرقام K ، والتي لا يتم طلبها بالضرورة.
استيراد java.util.scanner ؛ الطبقة العامة الرئيسية {public static void main (string [] args) {scanner in = new scanner (system.in) ؛ int n = in.nextint () ؛ int k = in.nextint () ؛ int [] num = new [n] i = 0 ؛ i <n ؛ i ++) {num [i] = in.nextint () ؛} boolean b = getMink (n ، num ، k ، out) ؛ if (b) {for (int i = 0 ؛ i <k ؛ i ++) {system.out.print (out [i] int uik ، int [] poutputarray) {if (pinputarray == null || poutputarray == null || uik> uiinputnum || uiinputnum <= 0 || uik <= 0) {return false ؛} int start = 0 ؛ int end = uiinputnum ؛ int index = partition (end ، start ، end) ؛ بينما (index! = uik-1) {if (index> uik-1) {// index يكون على الجانب الأيمن من k-1 end = index-1 ؛ index = partition (pinputarray ، start ، end) ؛} {start = index+1 ؛ index = partition (pinputarray ، start ، end) i = 0 ؛ i <uik ؛ i ++) {poutputarray [i] = pinputarray [i] ؛} return true ؛} // intromition struction strupt the inducture stable struction of Quick elect of the first artray a index in in int static in int ، int ، int int ، int end) j = end ؛ بينما (i <j) {بينما (i <j && privot <= a [j]) {j-؛} swap (a ، i ، j) ؛ بينما (i <j && privot> = a [i]) {i ++ ؛} swap (a ، i ، j) ؛} return i ؛} swap public static void (int [] a ، int i ، int j) {int t = a [i] ؛ a [i] = a [j] ؛ 2. أرقام بأكثر من نصف الأحداث في الصفيف
يوجد رقم في الصفيف يظهر أكثر من نصف طول الصفيف. يرجى العثور على هذا الرقم. على سبيل المثال ، 1 ، 2 ، 3 ، 2 ، 2 ، 5 ، 4 ، 2 ، يظهر الرقم 2 5 مرات في الصفيف ، يتجاوز نصف طول الصفيف ، الإخراج 2
مستوحاة من الفرز السريع ، في نوع سريع ، حدد الآن رقمًا في المصفوفة ، ثم ضبط ترتيب الأرقام في الصفيف بحيث يتم تصنيف الأرقام الأصغر من الرقم المحدد على يساره ويتم تصنيف أرقامه أكبر من الرقم المحدد على يمينه.
إذا كان المفرد من الرقم المحدد هو N/2 ، فإن هذا الرقم هو الرقم المتوسط في المصفوفة
استيراد java.util.scanner ؛ الطبقة العامة الرئيسية {public static void main (string [] args) {scanner in = new scanner (system.in) ؛ int n = in.nextint () ؛ int [] num = new int [n] b = gethalfnum (n ، num) ؛ if (b! = -1) {system.out.println (b) ؛}} int int int int gethalfnum (int uiinputnum ، int [] pinputarray) {if (pinputarray == null || uiinutnum <= 0) start = 0 ؛ int end = uiinputnum-1 ؛ int index = partition (pinputarray ، start ، end) ؛ بينما (index! = middle) {// إذا لم يكن مساويًا لنصف الطول ، فهذا يعني أنه لا يتم العثور على الوسيط إذا (index> middle) {end = index-1 ؛ index = partition (pinputarray ، start ، End) ؛ start ، int end) {int privot = a [start] ؛ int i = start ؛ int j = end ؛ بينما (i <j) {بينما (i <j && privot <= a [j]) {j-؛} swap (a ، i ، j) ؛ بينما (i <j & privot> = a [i]) {i ++ ؛} swap (a ، i ، j) ؛} return i ؛} تبديل الفراغ الثابت العام (int [] a ، int i ، int j) {int t = a [i] ؛ a [i] = a [j] ؛ 3. ابحث عن رقم KTH الأصغر في المصفوفة
على سبيل المثال ، تم إعطاء المصفوفة 1 ، 5 ، 2 ، 6 ، 8 ، 0 ، 6 ، وأصغر عدد أصغره هو 5
استيراد java.util.scanner ؛ الفئة العامة الرئيسية {public static void main (string [] args) {scanner in = new scanner (system.in) ؛ int n = in.nextint () ؛ int k = in.nextint () ؛ int [] num = new int [n] ؛ لـ (int i = 0 ؛ i <n ؛ i ++) {num [i] = in.nextint () ؛} int b = getMink (n ، num ، k) ؛ if (b! =-1) {system.out.println (b) ؛}} int int int int uiinputnum ، int [] Uik) {if (pinputarray == null || uik> uiinputnum || uiinputnum <= 0 || uik <= 0) {return -1 ؛} int start = 0 ؛ int end = uiinputnum -1 ؛ int index = partition (pinputarray ، start ، end) ؛ بينما (index! = uiK-1) {// إذا لم يكن الفهرس هو موضع k-1 if (index> uiK-1) {end = index-1 ؛ index = partition (pinputarray ، start ، end) ؛} else {start = index+1 ؛ index = partition (pinputarray ، end ، end) ؛}} الإرجاع [index] ؛ end) {int privot = a [start] ؛ int i = start ؛ int j = end ؛ بينما (i <j) {بينما (i <j && privot <= a [j]) {j-؛} swap (a ، i ، j) ؛ بينما (i <j & privot> = a [i]) {i ++ ؛} swap (a ، i ، j) ؛} return i ؛} تبديل الفراغ الثابت العام (int [] a ، int i ، int j) {int t = a [i] ؛ a [i] = a [j] ؛لخص
ما سبق هو المحتوى الكامل لهذه المقالة حول رمز المثال لثلاثة أسئلة خوارزمية بناءً على الفرز السريع لبرمجة Java. آمل أن يكون ذلك مفيدًا للجميع. يمكن للأصدقاء المهتمين الاستمرار في الرجوع إلى الموضوعات الأخرى ذات الصلة على هذا الموقع. إذا كانت هناك أي أوجه قصور ، فيرجى ترك رسالة لإشارةها. شكرا لك يا أصدقائك لدعمكم لهذا الموقع!