يتم استخدام خوارزمية الفرز في العديد من الأماكن، وقد قمت مؤخرًا بمراجعة الخوارزمية مرة أخرى وقمت بتنفيذها بنفسي، وسأقوم بتسجيلها هنا وحفظ بعض المواد للمراجعة المستقبلية.
دون مزيد من اللغط، دعونا نلقي نظرة على خوارزميات الفرز الكلاسيكية واحدة تلو الأخرى:
1. حدد الفرز
الفكرة الأساسية لفرز التحديد هي أنه أثناء عملية اجتياز المصفوفة، إذا كنت تمثل رقم التسلسل الحالي الذي يحتاج إلى الفرز، فأنت بحاجة إلى العثور على الحد الأدنى للقيمة بين [i...n-1] المتبقية ، ثم أشر إلى الحد الأدنى للقيمة التي تم العثور عليها حيث يتم تبادل القيم. نظرًا لأن كل عملية تحديد العناصر سيكون لها عملية فرعية لاختيار القيمة القصوى، فإن الناس يطلقون عليها بوضوح فرز الاختيار. لنأخذ مثالا:
الأولي: [38، 17، 16، 16، 7، 31، 39، 32، 2، 11]
ط = 0: [2، 17، 16، 16، 7، 31، 39، 32، 38، 11] (0 [38]<->8 [2])
ط = 1: [2، 7، 16، 16، 17، 31، 39، 32، 38، 11] (الأول [38]<->الرابع [17])
ط = 2: [2، 7، 11، 16، 17، 31، 39، 32، 38، 16] (الثاني [11]<->التاسع [16])
i = 3: [2، 7، 11، 16، 17، 31، 39، 32، 38، 16] (لا يلزم التبديل)
ط = 4: [2، 7، 11، 16، 16، 31، 39، 32، 38، 17] (الرابع [17]<->التاسع [16])
ط = 5: [2، 7، 11، 16، 16، 17، 39، 32، 38، 31] (الخامس [31]<->التاسع [17])
ط = 6: [2، 7، 11، 16، 16، 17، 31، 32، 38، 39] (6 [39]<->9 [31])
i = 7: [2، 7، 11، 16، 16، 17، 31، 32، 38، 39] (لا يلزم التبديل)
i = 8: [2، 7، 11، 16، 16، 17، 31، 32، 38، 39] (لا يلزم التبديل)
i = 9: [2، 7، 11، 16، 16، 17، 31، 32، 38، 39] (لا يلزم التبديل)
كما يتبين من المثال، مع استمرار فرز التحديد (i يزداد تدريجيًا)، سيصبح عدد المقارنات أقل فأقل، ومع ذلك، بغض النظر عما إذا كان المصفوفة مرتبة في البداية أم لا، فإن فرز التحديد سيؤدي إلى مقارنة التحديد من i إلى نهاية المصفوفة، لذلك بالنسبة لمصفوفة ذات طول معين، يكون عدد المقارنات في فرز التحديد ثابتًا: 1 + 2 + 3 + …. + n = n * (n + 1) / 2 ، ويرتبط عدد التبادلات بترتيب المصفوفة الأولية إذا كان ترتيب المصفوفة الأولي عشوائيًا، ففي أسوأ الحالات، سيتم تبادل عناصر المصفوفة n مرات، وفي أفضل الأحوال قد يكون 0 مرة ( المصفوفة نفسها عبارة عن تسلسل).
يمكن استنتاج أن التعقيد الزمني والتعقيد المكاني لفرز التحديد هما O(n2) وO(1) على التوالي (يتطلب فرز التحديد مساحة إضافية فقط لتبادل عناصر المصفوفة).
كود التنفيذ:
انسخ رمز الكود كما يلي:
/**
* فرز الاختيار
*/
التحديد (جديد قابل للفرز () {
public <T Extends Comparable<T>> voidsort(T[] array, boolean ascend) {
int len =ray.length;
لـ (int i = 0; i < len; i++) {
int المحدد = i;
لـ (int j = i + 1; j < len; j++) {
int Compare = array[j].compareTo(array[selected]);
إذا (قارن!= 0 && قارن <0 == تصاعدي) {
المحدد = ي؛
}
}
تبادل (صفيف، أنا، المحدد)؛
}
}
})
2. فرز الإدراج
الفكرة الأساسية لفرز الإدراج هي أنه أثناء عملية اجتياز المصفوفة، بافتراض أن العناصر قبل الرقم التسلسلي i، أي [0..i-1]، قد تم فرزها، فإن هذه الرحلة تحتاج إلى العثور على الموضع الصحيح k للعنصر x المقابل لـ i، وفي عملية العثور على هذا الموضع k، يتم إرجاع العناصر المقارنة إلى موضع واحد تلو الآخر "لإفساح المجال" للعنصر x وأخيرًا، يتم تعيين قيمة العنصر المقابلة لـ k x يتم تسمية فرز الإدراج أيضًا وفقًا لخصائص الفرز.
فيما يلي مثال على ذلك، الأرقام المميزة باللون الأحمر هي أرقام مدرجة، والأرقام المشطوبة هي عناصر لا تشارك في هذا الفرز واحداً تلو الآخر، مثل العناصر المشاركة في الفرز الثاني هي [11، 31، 12]، والعنصر المطلوب إدراجه هو 12، لكن 12 ليس في موضعه الصحيح حالياً، لذا نحتاج إلى إدراجه مع العناصر السابقة 31 و 11 بالتسلسل. قارن، وحرك العناصر المقارنة أثناء المقارنة، وتوقف عن المقارنة عندما تجد العنصر الأول 11 أصغر من 12. في هذا الوقت، الفهرس 1 المقابل لـ 31 هو الموضع الذي يجب إدراج 12 فيه.
الأولي: [11، 31، 12، 5، 34، 30، 26، 38، 36، 18]
التمريرة الأولى: [11، 31، 12، 5، 34، 30، 26، 38، 36، 18] (لا توجد عناصر متحركة)
الرحلة الثانية: [11، 12، 31، 5، 34، 30، 26، 38، 36، 18] (31 حركة للخلف)
الرحلة الثالثة: [5، 11، 12، 31، 34، 30، 26، 38، 36، 18] (11، 12، 31 جميعها تتحرك للخلف)
التمريرة الرابعة: [5، 11، 12، 31، 34، 30، 26، 38، 36، 18] (بدون عناصر متحركة)
الرحلة الخامسة: [5، 11، 12، 30، 31، 34، 26، 38، 36، 18] (31، 34 حركة للخلف)
الرحلة السادسة: [5، 11، 12، 26، 30، 31، 34، 38، 36، 18] (30، 31، 34 حركة للخلف)
التمريرة السابعة: [5، 11، 12، 26، 30، 31، 34، 38، 36، 18] (بدون عناصر متحركة)
الرحلة الثامنة: [5، 11، 12، 26، 30، 31، 34، 36، 38، 18] (38 حركة للخلف)
الرحلة التاسعة: [5، 11، 12، 18، 26، 30، 31، 34، 36، 38] (26، 30، 31، 34، 36، 38 ذهاباً وإياباً)
يعد الفرز بالإدراج أفضل من الفرز بالاختيار لأنه يمكن الاستفادة من حقيقة أن الجزء الأول من عناصر المصفوفة قد تم فرزه أثناء عملية الفرز، مما يقلل بشكل فعال عدد المقارنات، بالطبع، تعتمد هذه الميزة على الترتيب الأولي للعناصر array في النهاية، في الحالة السيئة (يصادف أن المصفوفة المحددة في ترتيب عكسي) سيكون عدد المقارنات والتحركات المطلوبة لفرز الإدراج مساويًا لـ 1 + 2 + 3... + n = n * (n). + 1) / 2. في هذه الحالة القصوى، تكون كفاءة الفرز بالإدراج أسوأ من الفرز بالاختيار. لذلك، يعد فرز الإدراج طريقة فرز غير مستقرة، وترتبط كفاءة الإدراج ارتباطًا وثيقًا بالترتيب الأولي للمصفوفة. بشكل عام، التعقيد الزمني والتعقيد المكاني لفرز الإدراج هما O(n2) وO(1) على التوالي.
كود التنفيذ:
انسخ رمز الكود كما يلي:
/**
* فرز الإدراج
*/
الإدراج (جديد قابل للفرز () {
public <T Extends Comparable<T>> voidsort(T[] array, boolean ascend) {
int len =ray.length;
لـ (int i = 1; i < len; i++) {
T toInsert = array[i];
كثافة العمليات ي = أنا؛
من أجل (؛ ي > 0؛ ي) {
int Compare = array[j - 1].compareTo(toInsert);
إذا (قارن == 0 || قارن <0 == تصاعدي) {
استراحة؛
}
المصفوفة[j] = المصفوفة[j - 1];
}
array[j] = toInsert;
}
}
})
3. فرز الفقاعة
يمكن اعتبار فرز الفقاعات أكثر خوارزميات الفرز كلاسيكية. أتذكر أن هذه الخوارزمية كانت أول خوارزمية تعاملت معها عندما كنت في المدرسة. نظرًا لأن طريقة التنفيذ هي الأبسط، فهي عبارة عن حلقة من مستويين الحلقة الداخلية، يتم الحكم على ما إذا كان العنصران المتجاوران في ترتيب عكسي. إذا كان الأمر كذلك، قم بتبادل العنصرين وتنفيذ حلقة خارجية واحدة "لتعويم" أصغر عنصر بين العناصر المتبقية في المصفوفة إلى الأمام، لذلك يطلق عليها. فرز الفقاعة.
ولنعطي مثالا بسيطا كالعادة:
الحالة الأولية: [24، 19، 26، 39، 36، 7، 31، 29، 38، 23]
الرحلة الأولى للطبقة الداخلية: [24، 19، 26، 39، 36، 7، 31، 29، 23، 38] (9 [23]<->8 [38)
التمريرة الثانية للطبقة الداخلية: [24، 19، 26، 39، 36، 7، 31، 23، 29، 38] (الثامن [23]<->السابع [29])
الممر الثالث للطبقة الداخلية : [24, 19, 26, 39, 36, 7, 23, 31, 29, 38] (7 [23]<->6 [31])
الممر الرابع للطبقة الداخلية: [24، 19، 26، 39، 36، 7، 23، 31، 29، 38] (7 و 23 كلها بالترتيب الصحيح، لا حاجة للتبديل)
الرحلة الخامسة للطبقة الداخلية: [24، 19، 26، 39، 7، 36، 23، 31، 29، 38] (الخامس [7]<->الرابع [36])
الرحلة السادسة للطبقة الداخلية: [24، 19، 26، 7، 39، 36، 23، 31، 29، 38] (الرابع [7]<->الثالث [39])
الممر السابع للطبقة الداخلية: [24، 19، 7، 26، 39، 36، 23، 31، 29، 38] (الثالث [7]<->الثاني [26])
الممر الثامن للطبقة الداخلية : [24, 7, 19, 26, 39, 36, 23, 31, 29, 38] (الثاني [7]<->الأول [19])
الرحلة التاسعة للطبقة الداخلية: [7، 24، 19، 26، 39، 36، 23، 31، 29، 38] (الأول [7]<->0 [24])
……….
في الواقع، يشبه الفرز الفقاعي الفرز بالاختيار، وعدد المقارنات هو نفسه، n * (n + 1) / 2. ومع ذلك، سيؤدي الفرز الفقاعي إلى إجراء تبادلات إضافية في عملية تحديد الحد الأدنى للقيمة (يحتاج الفرز الفقاعي فقط إلى ذلك). إذا وجد أن ترتيب العناصر المتجاورة غير صحيح، فسيتم تبادله، وفي المقابل، سيقرر الفرز الاختياري فقط ما إذا كان سيتم التبادل وفقًا للموقف بعد اكتمال مقارنة الحلقة الداخلية)، لذلك في رأيي، ينتمي الفرز الاختياري. لفرز الفقاعة.
كود التنفيذ:
انسخ رمز الكود كما يلي:
/**
* فرز الفقاعات، وهو مشابه جدًا لفرز الإدراج
*/
فقاعة (جديدة قابلة للفرز () {
public <T Extends Comparable<T>> voidsort(T[] array, boolean ascend) {
int length = array.length;
int lastExchangedIdx = 0;
لـ (int i = 0; i < length; i++) {
// ضع علامة على الهوية سواء حدث التبادل أم لا
boolean isExchanged = false;
// حدثت آخر مقارنة وتبادل قبل الوصول إلى الفهرس i
int currOrderedIdx = lastExchangedIdx > i ? lastExchangedIdx : i;
لـ (int j = length 1; j > currOrderedIdx; j) {
int Compare = array[j - 1].compareTo(array[j]);
إذا (قارن != 0 && قارن > 0 == تصاعدي) {
تبادل(صفيف، ي 1، ي)؛
isExchanged = true;
lastExchangedIdx = j;
}
}
// إذا لم يحدث أي تبادل فهذا يعني أن المصفوفة في حالة جيدة بالفعل
إذا (يتم تبادل == خطأ) {
استراحة؛
}
}
}
})
4. فرز التل
وُلد فرز التل لأن فرز الإدراج واجه مشكلة نقل عدد كبير جدًا من العناصر عند التعامل مع صفائف كبيرة. فكرة فرز التل هي "تقسيم تسد" مصفوفة كبيرة إلى عدة مصفوفات صغيرة، مقسمة حسب الفجوات، مثل المصفوفة [1، 2، 3، 4، 5، 6، 7، 8]. = 2 للتقسيم، يمكن تقسيمها إلى مصفوفتين [1، 3، 5، 7] و [2، 4، 6، 8] (على التوالي، مثل الفجوة = 3) ، ثم المصفوفات المقسمة هي: [1، 4، 7]، [2، 5، 8]، [3، 6]) ثم قم بإجراء فرز الإدراج على المصفوفات المقسمة، ثم قم بتقليلها بعد فرز كل مصفوفة فرعية. كرر الخطوات السابقة حتى الفجوة = 1 أي أنه يتم إجراء فرز الإدراج على المصفوفة بأكملها في هذا الوقت، ويتم فرز المصفوفة بشكل أساسي، وبالتالي فإن العناصر التي يجب نقلها ستكون صغيرة جدًا، مما يحل مشكلة المزيد من النقلات في فرز الإدراج عند المعالجة الكبيرة. صفائف النطاق.
الرجاء الرجوع إلى فرز الإدراج للحصول على أمثلة محددة.
يعد فرز التل نسخة محسنة من فرز الإدراج، وهو مفيد جدًا في تحسين الكفاءة عندما تكون كمية البيانات كبيرة، ويوصى باستخدام فرز الإدراج مباشرة.
كود التنفيذ:
انسخ رمز الكود كما يلي:
/**
* فرز القشرة
*/
شل (جديد قابل للفرز () {
public <T Extends Comparable<T>> voidsort(T[] array, boolean ascend) {
int length = array.length;
فجوة كثافة العمليات = 1؛
// استخدم الأكثر بجوار الطول / 3 كالفجوة الأولى
بينما (الفجوة <الطول / 3) {
فجوة = فجوة * 3 + 1؛
}
بينما (الفجوة >= 1) {
لـ (int i = فجوة؛ i < length؛ i++) {
T next = array[i];
كثافة العمليات ي = أنا؛
بينما (ي >= فجوة) {
int Compare = array[j - الفجوة].compareTo(next);
// العثور على موقعه بالفعل
إذا (قارن == 0 || قارن <0 == تصاعدي) {
استراحة؛
}
صفيف[j] = صفيف[j - فجوة];
ي -= فجوة؛
}
إذا (ي != أنا) {
المصفوفة[j] = التالي؛
}
}
الفجوة / = 3؛
}
}
})
5. دمج الفرز
يتم تنفيذ فرز الدمج عن طريق العودية، وهي طريقة "تقسيم تسد"، ويتم تقسيم المصفوفة المستهدفة إلى قسمين من المنتصف، ثم يتم فرز المصفوفتين بشكل منفصل، ويتم "دمج" المصفوفتين المصنفتين "في معًا، أهم شيء في فرز الدمج هو عملية "الدمج". تتطلب عملية الدمج مساحة إضافية تتوافق مع طول المصفوفتين اللتين تحتاجان إلى الدمج. على سبيل المثال، المصفوفات التي تحتاج إلى تحديد هي: [3، 6، 8، 11] و [1، 3، 12، 15] (على الرغم من تقسيمها منطقيًا إلى مصفوفتين، إلا أن هذه العناصر لا تزال في الواقع في المصفوفة الأصلية، ولكنها مقسمة إلى مصفوفتين من خلال بعض الفهارس. المصفوفة الأصلية لـ [3، 6، 8، 11، 1، 3، 12، 15، قمنا بتعيين ثلاثة مؤشرات منخفضة ومتوسطة وعالية إلى 0 و3 و7 على التوالي. يمكن تحقيق التقسيم المنطقي للمصفوفة الفرعية) ثم يكون طول المصفوفة الإضافية المطلوبة 4 + 4 = 8. ويمكن تلخيص عملية الدمج بإيجاز على النحو التالي:
1) انسخ العناصر الموجودة في المصفوفتين الفرعيتين إلى المصفوفة الجديدة copiedArray. بأخذ المثال المذكور أعلاه كمثال، copiedArray = [3, 6, 8, 11, 1, 3, 12, 15];
2) قم بتعيين مؤشرين للإشارة إلى العنصر الأول المقابل في المصفوفة الذرية على التوالي، افترض أن المؤشرين تم تسميتهما leftIdx وrightIdx، ثم leftIdx = 0 (المتوافق مع العنصر الأول [3] في copiedArray)، rightIdx = 4 ( الموافق للعنصر الخامس [1] في المصفوفة المنسوخة)؛
3) قارن قيم عناصر المصفوفة المشار إليها بواسطة leftIdx وrightIdx، وحدد العنصر الأصغر وقم بتعيين قيمته إلى الموضع المقابل i في المصفوفة الأصلية، بعد اكتمال التعيين، قم بإجراء عملية زيادة تلقائية على فهارسان مشاركان في المهمة إذا وصلت قيمة leftIdx أو rigthIdx إلى نهاية المصفوفة المقابلة، فكل ما تبقى هو نسخ عناصر المصفوفة المتبقية إلى المواضع المتبقية بالترتيب.
فيما يلي مثال محدد للدمج:
الرحلة الأولى:
المصفوفة المساعدة [21، 28، 39 |. 35، 38] (يتم تقسيم المصفوفة إلى صفيفتين فرعيتين أيمن وأيسر، مفصولتين بـ |)
[21, , , , ] (في المرة الأولى التي تتم فيها مقارنة 21 بـ 35، تفوز المصفوفة الفرعية اليسرى، leftIdx = 0، i = 0)
الرحلة الثانية:
المصفوفة المساعدة [21، 28، 39 |.35، 38]
[21، 28،،، ] (في المرة الثانية تتم مقارنة 28 بـ 35، تفوز المصفوفة الفرعية اليسرى، leftIdx = 1، i = 1)
الرحلة الثالثة: [٢١، ٢٨، ٣٩ |.
[21، 28، 35، ] (في المرة الثالثة تتم مقارنة 39 بـ 35، تفوز المصفوفة الفرعية الصحيحة، rightIdx = 0، i = 2)
الرحلة الرابعة: [21، 28، 39 |.
[21، 28، 35، 38،] (في المرة الرابعة التي تتم فيها مقارنة 39 و 38، تفوز المصفوفة الفرعية الصحيحة، rightIdx = 1، i = 3)
الرحلة الخامسة: [21، 28، 39 |.
[21، 28، 35، 38، 39] (تم نسخ المصفوفة الفرعية اليمنى للمرة الخامسة، لا حاجة لمقارنة leftIdx = 2، i = 4)
ما سبق هو عملية دمج يمكننا تقسيم المصفوفة بأكملها التي تحتاج إلى فرزها لعدد محدود من المرات (مقسمة إلى قسمين في كل مرة) حتى يتم تقسيمها إلى مصفوفة صغيرة بطول 1. عندما يكون الطول 1، لم تعد هناك حاجة إلى فرز المصفوفة. بعد ذلك، يتم دمج هذه المصفوفات بترتيب عكسي (بسبب التكرار) حتى يتم دمج المصفوفة الفرعية الأخيرة ذات الطول n / 2، وبعد اكتمال الدمج، يكتمل فرز المصفوفة أيضًا.
يتطلب فرز الدمج أكبر مساحة إضافية من جميع عمليات الفرز، ويتطلب كل دمج نفس عدد العناصر كمجموع أطوال المصفوفتين المشاركين في الدمج (من أجل توفير مصفوفة مساعدة). ثم يمكن استنتاج أن التعقيد المكاني للفرز المدمج هو 1 + 2 + 4 + ... + n = n * ( n + 2) / 4 (تجاهل حكم التكافؤ لـ n) ومن الصعب تقدير التعقيد الزمني هنا نسيت أيضًا كم ().
كود التنفيذ:
انسخ رمز الكود كما يلي:
/**
* دمج الفرز
*/
دمج (جديد قابل للفرز () {
public <T Extends Comparable<T>> voidsort(T[] array, boolean ascend) {
this.sort(array, 0, array.length 1, ascend);
}
خاص <T يمتد Comparable<T>> voidsort(T[] array, int lo, int hi, boolean ascend) {
// تحسين واحد
// إذا كان طول السلسلة الفرعية أقل من 20،
// استخدم فرز الإدراج لتقليل الاستدعاء العودي
إذا (مرحبا لو <20) {
لـ (int i = lo + 1; i <= hi; i++) {
T toInsert = array[i];
كثافة العمليات ي = أنا؛
لـ (؛ ي > لو؛ ي) {
int Compare = array[j - 1].compareTo(toInsert);
إذا (قارن == 0 || قارن <0 == تصاعدي) {
استراحة؛
}
المصفوفة[j] = المصفوفة[j - 1];
}
array[j] = toInsert;
}
يعود؛
}
int mid = lo + (hi lo) / 2;
فرز (صفيف، لو، منتصف، تصاعدي)؛
فرز (صفيف، منتصف + 1، مرحبا، تصاعدي)؛
دمج (صفيف، لو، منتصف، مرحبا، تصاعدي)؛
}
خاص <T يمتد للمقارنة<T>> دمج باطل(T[] array, int lo, int mid, int hi, boolean ascend) {
// تحسين اثنين
// إذا كان بالفعل في الترتيب الصحيح، تخطي هذا الدمج
// لأنه ليس هناك حاجة للقيام بذلك
int leftEndCompareToRigthStart = array[mid].compareTo(array[mid + 1]);
إذا (leftEndCompareToRigthStart == 0 || leftEndCompareToRigthStart < 0 == ascend) {
يعود؛
}
@SuppressWarnings("تم إلغاء التحديد")
T[] arrayCopy = (T[]) new Comparable[hi - lo + 1];
System.arraycopy(array, lo, arrayCopy, 0, arrayCopy.length);
int lowIdx = 0;
int HighIdx = mid lo + 1;
لـ (int i = lo; i <= hi; i++) {
إذا (lowIdx > منتصف لو) {
// تم استنفاد المصفوفة الفرعية اليسرى
array[i] = arrayCopy[highIdx++];
} وإلا إذا (highIdx > مرحبًا لو) {
// تم استنفاد المصفوفة الفرعية اليمنى
array[i] = arrayCopy[lowIdx++];
} else if (arrayCopy[lowIdx].compareTo(arrayCopy[highIdx]) < 0 == ascend) {
array[i] = arrayCopy[lowIdx++];
} آخر {
array[i] = arrayCopy[highIdx++];
}
}
}
})
6. الفرز السريع
الفرز السريع هو أيضًا خوارزمية فرز "فرق تسد" يتم تنفيذها باستخدام طريقة الدمج، وسحرها هو أنه يمكنها تحديد الموضع الصحيح النهائي للفرز لعنصر مصفوفة في كل قسم (جوهر خوارزمية الفرز) (مرة واحدة). إذا كان تحديد الموقع دقيقًا، فلن يتم أخذ هذا العنصر في الاعتبار في الدورة التالية).