الفرز السريع هو العثور على عنصر (في الأصل يمكنك العثور على واحد) كمرجع (PIVOT) ، ثم تقسيم الصفيف بحيث لا تكون قيمة العنصر على يسار المرجع أكبر من القيمة المرجعية ، والقيمة من العنصر على يمين المرجع لا يقل عن القيمة المرجعية. فرز سريع متكرر ، اضبط عناصر N-1 الأخرى على الموضع الصحيح بعد الفرز. أخيرًا ، يكون كل عنصر في الموضع الصحيح بعد الفرز ويتم الانتهاء من الفرز. لذلك ، فإن الخوارزمية الأساسية لخوارزمية الفرز السريع هي تقسيم التشغيل ، أي كيفية ضبط موضع المعيار وتعديل الموضع النهائي لمعيار العودة من أجل تقسيم العودة وقهرها.
خوارزمية الفرز السريع هي:
1) قم بتعيين متغيرين I و J ، عندما يبدأ الفرز: i = 0 ، j = n-1 ؛
2) استخدم عنصر الصفيف الأول كبيانات مفتاح وقم بتعيينه إلى المفتاح ، أي المفتاح = A [0] ؛
3) ابدأ من J إلى البحث إلى الأمام ، أي ابدأ من الخلف إلى البحث إلى الأمام (J--) ، والعثور على القيمة الأولى A [J] أصغر من المفتاح ، ومبادلة A [J] و A [i] ؛
4) ابدأ من I للبحث إلى الوراء ، أي ، ابدأ من الأمام إلى الوراء (i ++) ، والعثور على أول [i] أكبر من المفتاح ، وتبديل A [i] و A [j] ؛
5) كرر الخطوات 3 و 4 حتى i = j ؛ 4 ليس أكبر من تغيير قيم J و I بحيث J = J-1 ، i = i+1 حتى يتم العثور عليها. لا يزال دون تغيير.
اسمحوا لي أن أعطيك مثالاً ، قد لا يكون من السهل فهمه. افترض أن التسلسل المراد فرزه
نسخة الكود كما يلي:
حزمة com.zc.ManyTherD ؛
استيراد java.util.random ؛
/**
* نوع سريع
* Author Administrator
*
*/
الطبقة العامة qsort {
INT [] التاريخ ؛
عام QSort (int [] تاريخ) {
this.date = date ؛
}
/**
* وظيفة التبادل
* param
* param أنا
* param j
*/
مبادلة الفراغ الخاصة (int a [] ، int i ، int j) {
int t ؛
t = a [i] ؛
a [i] = a [j] ؛
a [j] = t ؛
}
/***************************
* فرز وظيفة
* param
* param lo0
* param hi0
* @يعود
*/
int [] Quicksort (int a [] ، int lo0 ، int hi0) {// طريقة التقسيم والعلاج هي تقسيم الصفيف إلى [lo0..q-1] و A [q+1..hi0]
int lo = lo0 ؛
int مرحبا = hi0 ؛
int منتصف
if (hi0> lo0) {
mid = a [(hi0+lo0)/2] ؛
بينما (lo <= hi) {
بينما ((lo <hi0) && (a [lo] <mid)) ++ lo ؛
بينما ((مرحبًا> lo0) && (a [hi]> mid)) -hi ؛
if (lo <= hi) {
مبادلة (a ، lo ، مرحبا) ؛
++ lo ؛
--أهلاً؛
}
}
إذا (lo0 <hi) {
Quicksort (a ، lo0 ، hi) ؛
}
إذا (lo <hi0) {
Quicksort (a ، lo ، hi0) ؛
}
}
إرجاع أ ؛
}
/******************
*
* إنشاء بيانات صفيف مكررة
********************/
int static int [] تم إنشاؤه (عدد int) {
int [] data = new int [count] ؛
لـ (int i = 0 ؛ i <data.length ؛ i ++) {
البيانات [i] = (int) (math.random ()*count) ؛
}
إرجاع البيانات ؛
}
/**
* لا توجد بيانات صفيف مكررة
* @param العد
* @يعود
*/
int int static int [] createate1 (int count) {
int [] data = new int [count] ؛
Rand Rand = New Random () ؛
Boolean [] Bool = New Boolean [100] ؛
int num = 0 ؛
لـ (int i = 0 ؛ i <count ؛ i ++) {
يفعل {
// إذا كان الرقم الذي تم إنشاؤه هو نفسه ، فاستمر في الحلقة
num = rand.nextint (100) ؛
} بينما (bool [num]) ؛
Bool [num] = true ؛
البيانات [i] = num ؛
}
إرجاع البيانات ؛
}
/************ الوظيفة الرئيسية *******************/
الفراغ الثابت العام الرئيسي (سلسلة [] args) {
عدد int النهائي = 10 ؛
int [] data = createTate1 (count) ؛
لـ (int n: data) {
system.out.print (n+"/t") ؛
}
QSort Data1 = QSort جديد (بيانات) ؛
System.out.println () ؛
int [] a = data1.QuickSort (البيانات ، 0 ، count-1) ؛
لـ (int n: a) {
system.out.print (n+"/t") ؛
}
}
}
النتائج كما يلي:
ما سبق هو كل المحتوى الموضح في هذه المقالة.