تتم مقارنة كفاءة الفرز بشكل عام من ثلاثة جوانب: عدد مقارنات البيانات، وعدد عمليات نقل البيانات، ومقدار مساحة الذاكرة المشغولة.
لنقم بإجراء مقارنة عامة بين فرز الفقاعات وفرز التحديد وفرز الإدراج والفرز السريع. لا يتم استخدام خوارزمية فرز الفقاعات بشكل عام لأن عدد المقارنات والحركات الخاصة بها هو الأكبر بين العديد من خوارزميات الفرز. ميزتها الوحيدة هي أن الخوارزمية بسيطة وسهلة الفهم، لذلك يمكن استخدامها عندما تكون كمية البيانات صغيرة سيكون بعض قيمة التطبيق. يحتوي الفرز بالتحديد على نفس عدد المقارنات مثل الفرز الفقاعي، وهو n تربيع، ولكنه يقلل من عدد التبادلات إلى الحد الأدنى، لذلك يمكن تطبيقه عندما تكون كمية البيانات صغيرة ويكون تبادل البيانات أكثر استهلاكًا للوقت من المقارنة حدد فرز.
في معظم الحالات، عندما تكون كمية البيانات صغيرة نسبيًا أو مرتبة بشكل أساسي، فإن خوارزمية فرز الإدراج هي الخيار الأفضل. لفرز كميات أكبر من البيانات، عادةً ما يكون الفرز السريع هو أفضل طريقة.
تشغل خوارزمية الفرز المذكورة أعلاه مساحة صغيرة جدًا من الذاكرة وتتطلب فقط متغيرًا إضافيًا لتخزين عناصر البيانات مؤقتًا أثناء التبادل. ولذلك لا مجال للمقارنة في حجم مساحة الذاكرة المشغولة.
لا يزال عدد مقارنات فرز الإدراج n مربعًا، ولكنه بشكل عام أسرع مرتين من فرز الفقاعات وأسرع قليلاً من فرز التحديد. وغالبًا ما يتم استخدامه في المراحل النهائية من خوارزميات الفرز المعقدة، مثل الفرز السريع.
الخوارزمية: بعد معالجة i-1، تم فرز L[1..i-1]. يقوم التمرير i بإدخال L[i] فقط في الموضع المناسب لـ L[1..i-1]،
بحيث يكون L[1..i] تسلسلًا مرتبًا مرة أخرى. لتحقيق هذا الهدف، يمكننا استخدام المقارنة التسلسلية.
قارن أولاً L[i] وL[i-1]. إذا كان L[i-1]<=L[i]، فقد تم فرز L[1..i] وانتهى مسار المعالجة؛
بخلاف ذلك، قم بتبديل موضعي L[i] وL[i-1]، واستمر في مقارنة L[i-1] وL[i-2] حتى يتم تحديد موضع معين j (1≥j≤i-1) وجد.
حتى L[j] ≥L[j+1]
المزايا: يتم نقل عدد أقل من العناصر ولا يلزم سوى مساحة إضافية
تعقيد الوقت ن * ن
تعد هذه طريقة فرز جيدة عندما يكون عدد السجلات المراد فرزها صغيرًا. ولكن عندما يكون n كبيرًا جدًا، فهو غير مناسب
على سبيل المثال: قيم int[] = { 5, 2, 4, 1, 3 };
عملية الفرز:
المرة الأولى: 2،5،4،1،3
المرة الثانية: 2،4،5،1،3
المرة الثالثة: 1،2،4،5،3
المرة الرابعة: 1،2،3،4،5
كود جافا:
انسخ رمز الكود كما يلي:
الفئة العامة InsertSort {
public static void main(String[] args) {
قيمة int[] = { 5, 2, 4, 1, 3 };
فرز (القيم)؛
لـ (int i = 0; i <values.length; ++i) {
System.out.println(values[i]);
}
}
فرز الفراغ الثابت العام (قيم int []) {
درجة الحرارة الدولية؛
كثافة العمليات ي = 0;
لـ (int i = 1; i <values.length; i++) {
if(values[i]<values[i-1])// الحكم هنا مهم جدًا، وهذا يعكس سبب كون فرز الإدراج أسرع من فرز الفقاعات وفرز التحديد.
{
درجة الحرارة = القيم[i];
// انقل البيانات إلى الخلف
لـ (j=i-1; j>=0 && temp<values[j]; j--)
{
value[j+1] =values[j];
}
// أدخل البيانات في الموضع j+1
value[j+1] =temp;
System.out.print("th" + (i + 1) + "th:");
لـ (int k = 0; k <values.length; k++) {
System.out.print(values[k]+"،");
}
System.out.println("");
}
}
}
}
المثال الثاني
انسخ رمز الكود كما يلي:
الحزمة cn.cqu.coce.xutao;
الطبقة العامة zhijiecharu {
الفراغ الثابت العام الرئيسي(String args[]){
int a[]={1,2,34,67,8,9,6,7,56,34,232,99};
كثافة العمليات ط، ي، ك؛
ل(i=0;i<a.length;i++)
System.out.print(a[i]+"/t");
System.out.println();
ل(i=1;i<a. length;i++){
ل(ي=i-1;ي>=0;ي--)
إذا (أ[i]>أ[ي])
استراحة؛
إذا (ي!=ط-1){
درجة الحرارة الدولية؛
temp=a[i];
ل(ك=i-1;ك>ي;ك--)
a[k+1]=a[k];
a[k+1]=temp;
}
}
ل(i=0;i<a.length;i++)
System.out.print(a[i]+"/t");
System.out.println();
}
}