مقدمة سريعة للفرز والتقسيم والقهر

لقد جعلني الفرز السريع أنظر إليه لفترة طويلة وعذبني لفترة طويلة، لأن لدي فكرة عامة، ولكن تنشأ دائمًا مشكلات مختلفة عند كتابة التعليمات البرمجية، ولا يزال من الصعب علي شخصيًا تصحيحها درجة معينة من الصعوبة، وبسبب العمل والكسل، تم التخلص من الأخطاء التي لا يمكن تصحيحها لفترة طويلة، واليوم تم التخلص منها أخيرًا، وما زلت متحمسًا قليلاً لمشاركة الكود الخاص بي وتقديمه القليل من التفسير.

لتتعلم الفرز السريع، يجب عليك أولاً أن تتعلم طريقة فرق تسد. فكرة فرق تسد هي إعطاء سلسلة من الأرقام غير المرتبة (الأرقام هي افتراضات، ويمكن أن تكون أيضًا كائنات أخرى). بالطبع، يمكن تحديد معلمات الطريقة بنفسك (أنا هنا لنفترض أن هناك مجموعة من الأعداد الصحيحة) ثم أعطها له الرقم الأوسط، طريقة فرق تسد ستقسم هذه الأرقام إلى جزأين بناءً على الرقم الأوسط المعطى له، جزء واحد على يسار الرقم الأوسط، والجزء الآخر على اليمين باستخدام هذا الرقم نقطة التقسيم، فإن الأرقام على كلا الجانبين لا تزال خارج الترتيب، والطريقة التي حددتها هي كما يلي:

 // اليسار هو نقطة النهاية اليسرى لجزء فرق تسد من المصفوفة، واليمين هو نقطة النهاية الإجمالية لجزء فرق تسد من المصفوفة، على سبيل المثال، لمصفوفة بطول 10 أريد تقسيم الأعداد الخمسة الأولى وقهرها، يمكنني تمرير 0 أو 4 كـ public int signalFenZhi(int left,int right){ if(left<0||left>n-1||right<0||right> n-1){ return -1 } int temp = test[left]; j=right; &&i<j){ i++; } if(i<j){ temp = test[i]; test[j]; = اختبار[i]; test[i]=test[left]; test[left]=temp } for(int m=0;m<n;m++){ System.out.print(test[m]+" } return i }

بالطبع، يمكنك أيضًا تمرير الرقم الأوسط كمعلمة. والآن أستخدم فقط الرقم الأيسر الذي تم تمريره كرقم القسمة. هذا للتوضيح فقط.

بعد فهم فرق تسد، يصبح الفرز السريع أمرًا بسيطًا، وهو تقسيم وقهر الأرقام التي تم تقسيمها إلى جزأين، وهكذا حتى تصبح جميع الأرقام مرتبة كما يلي:

 public void QuickSort(int left,int right){ if(right-left<1){ return }else{ int point = this.signalFenZhi(left, right); point!=left&&point!=right){ QuickSort(left,point-1);

كفاءة الفرز السريع ممتازة بين العديد من خوارزميات الفرز. التعقيد الزمني هو O(N*log2n)، ومع ذلك، إذا لم يتم اختيار نقطة التقسيم بشكل جيد، فسيتم تقليل التعقيد الزمني إلى (n تربيع). )، لأنه إذا تم فرز هذه المصفوفة، ثم أخذنا الرقم الذي تم تمريره في أقصى اليسار في كل مرة، فستكون الكفاءة منخفضة جدًا، لذلك يجب علينا تجنب هذا الموقف إذا تم اختبار جميع الخيارات، فسوف يستغرق الأمر الكثير الوقت، لذلك إحدى الطرق التوفيقية هي إضافة رقم متوسط ​​إلى الرقم الموجود في أقصى اليسار والرقم الموجود في أقصى اليمين، والعثور على الرقم الأوسط بينهما، واستخدام هذا كقيمة القسمة سيجعل الأمور أفضل. بناءً على الطريقة المذكورة أعلاه، فإن الكود المعدل هو كما يلي: ولكن بعد أن انتهيت منه، لم يكن هذا النهج جيدًا جدًا، سيكون من الأفضل تمرير قيمة القسمة كطريقة فرق تسد، ويمكن للأصدقاء الحذرين تجربتها بأنفسهم، لكنني لن أحاول ذلك هنا، نفس الشيء في الأساس.

 package com.jll; public class FenZhi { int[] test; int n=10; public FenZhi(){ test = new int[10]; =(int)(Math.random()*100)+1; System.out.print(test[i]+" "); n){ if(n>0){ this.n=n; test = new int[n]; for(int i=0;i<n;i++){ test[i]=(int)(Math.random) ()*100)+1; } } } public int signalFenZhiMajorizationFirst(int left,int right){ if(left<0||left>n-1||right<0||right>n-1||left>=right){ return -1 } if(right-left>=2){ int middle = (يمين+يسار)/2; if(test[left]>test[middle]){ int temp = test[middle]; test[left]; if(test[left]>test[right]){ int temp = test[left]; test[left] = test[right]; ){ int temp = test[middle] = test[right]; test[left]; = int j=right-1; int i=left+1; while(i<j){ while(test[j]>=test[left]&&i<j){ j--; ]<=test[left]&&i<j){ i++; } if(i<j){ temp = test[i]=test[j]; ط == ي) { temp = test[i]; test[i]=test[left]=temp } /*if(i==j){ temp = test[middle]; ]; test[i]=temp }*/ /*for(int m=0;m<n;m++){ System.out.print(test[m]+" "); آخر { if(test[right]<test[left]){ int temp = test[right]; test[left]; test[left] = temp; } return right; ,int right){ if(right-left<1){ return }else{ int point = this.signalFenZhiMajorizationFirst(left, right); is: "+point); QuickSortMajorizationFirst(left,point-1); QuickSortMajorizationFirst(point+1,right); } } public static void main(String[] args) { FenZhi f = new FenZhi(); System.out. println(f.signalFenZhiMajorizationFirst(0, 9)); System.out.println(); f.quickSortMajorizationFirst(0,fn-1); //f.quickSort(0,f.test. length-1); }}

يعمل الكود على النحو التالي:

 95 40 64 18 78 23 73 84 40 النقطة هي:4 النقطة هي:1 النقطة هي:3 النقطة هي:7 النقطة هي:6 النقطة هي:918 23 40 40 64 73 78 84 95

ما سبق هو ما تعلمته، سجله للرجوع إليه في المستقبل.