هناك نوع من التحسن في فرز الفقاعات هو أنه إذا تم طلب تسلسل السجل الأولي أو طلبه بشكل أساسي بواسطة الكلمات الرئيسية ، فسوف يتحول إلى فرز الفقاعات. يتم استخدام مبدأ التكرار ، وأداء متوسطه هو الأفضل بين جميع أساليب الفرز بنفس ترتيب الحجم O (N Longn). من حيث متوسط الوقت ، يعتبر حاليًا أفضل طريقة للفرز الداخلي.
الفكرة الأساسية هي: قسّم البيانات المراد فرزها إلى جزأين مستقلين عن طريق الفرز ، وجميع البيانات جزئيًا أصغر من جميع البيانات في الجزء الآخر ، ثم فرز هذين الجزأين من البيانات بسرعة وفقًا لهذه الطريقة .
ثلاثة مؤشرات: يسمى المؤشر الأول مؤشر Pivotkey (PIVOT) ، المؤشر الثاني والمؤشر الثالث مؤشر ترك والمؤشر الأيمن ، على التوالي ، يشير إلى القيمة في أقصى اليسار والقيمة في أقصى اليمين. المؤشر الأيسر والمؤشر الأيمن من كلا الجانبين إلى الوسط في نفس الوقت. المحور إلى الطرف الأعلى.
مطلوب وظيفتان:
① الوظيفة العودية Quicksort Quicksort (int [] n ، int ، int اليمين)
② وظيفة القطاع (وظيفة فرز سريع واحد) قسم int ثابت عام (int [] n ، int اليسار ، int اليمين)
رمز مصدر جافا (تشغيل بنجاح):
نسخة الكود كما يلي:
حزمة testsortalgorithm ؛
الطبقة العامة QuickSort {
الفراغ الثابت العام الرئيسي (سلسلة [] args) {
int [] Array = {49،38،65،97،76،13،27} ؛
QuickSort (Array ، 0 ، Array.Length - 1) ؛
لـ (int i = 0 ؛ i <array.length ؛ i ++) {
System.out.println (Array [i]) ؛
}
}
/*اكتب أولاً الخوارزمية كنموذج أولي للبيانات وفقًا للمصفوفة ، ثم اكتب خوارزمية قابلية التوسع. Array {49،38،65،97،76،13،27}
* */
Quicksort Quicksort Quickors (int [] n ، int ، int يمين) {
int pivot
إذا (اليسار <اليمين) {
// pivot كما المحور ، العنصر الأصغر على اليسار والعنصر الأكبر على اليمين
pivot = partition (n ، يسار ، يمين) ؛
// استدعاء بشكل متكرر من النوع السريع على المصفوفات اليمنى واليسرى حتى يصبح الطلب صحيحًا تمامًا
Quicksort (n ، اليسار ، pivot - 1) ؛
Quicksort (n ، pivot + 1 ، يمين) ؛
}
}
قسم int الثابت العام (int [] n ، int اليسار ، int اليمين) {
int pivotkey = n [left] ؛
// لن يتغير المحور أبدًا بعد اختياره ، وسيكون في النهاية في الوسط ، مع ظهور أمامي صغير وكبير
بينما (اليسار <يمين) {
بينما (يسار <اليمين && n [يمين]> = pivotkey) -اليمين ؛
// حرك العنصر الأصغر من المحور إلى النهاية المنخفضة.
n [يسار] = n [يمين] ؛
بينما (يسار <اليمين && n [يسار] <= pivotkey) ++ اليسار ؛
// حرك العنصر الأكبر من المحور إلى النهاية.
n [يمين] = n [يسار] ؛
}
// عندما تركت == يمينًا ، أكمل رحلة فرز سريعة.
n [اليسار] = pivotkey ؛
العودة إلى اليسار
}
}