الاستقرار (الاستقرار)
خوارزمية الفرز مستقرة، أي أنه عندما يكون هناك سجلان متساويان للمفاتيح R وS، ويظهر R قبل S في القائمة الأصلية، فسيظهر R أيضًا قبل S في القائمة التي تم فرزها.
فرز تصنيف الخوارزمية
تتضمن العناصر الشائعة الإدراج (فرز الإدراج/فرز التل)، والتبادل (فرز الفقاعات/الفرز السريع)، والاختيار (فرز التحديد)، والدمج (فرز الدمج)، وما إلى ذلك.
1. فرز الإدراج
يعمل فرز الإدراج (فرز الإدراج) عن طريق إنشاء تسلسل مرتب بالنسبة للبيانات غير المصنفة، فإنه يقوم بالمسح من الخلف إلى الأمام في التسلسل المصنف للعثور على الموضع المقابل وإدراجه. في تنفيذ فرز الإدراج، يتم استخدام الفرز الموضعي عادةً (أي الفرز الذي يستخدم مساحة إضافية O(1) فقط). لذلك، أثناء عملية المسح من الخلف إلى الأمام، من الضروري تحويل الترتيب بشكل متكرر وتدريجي تم فرز العناصر إلى الخلف، مما يوفر مساحة للإدراج لأحدث عنصر.
بشكل عام، يتم تنفيذ فرز الإدراج على المصفوفات باستخدام موضعي. يتم وصف الخوارزمية المحددة على النحو التالي:
بدءًا من العنصر الأول، يمكن اعتبار العناصر مرتبة.
احصل على العنصر التالي وقم بمسحه ضوئيًا من الخلف إلى الأمام في التسلسل المرتب للعناصر.
إذا كان العنصر (المفرز) أكبر من العنصر الجديد، انقل العنصر إلى الموضع التالي.
كرر الخطوة 3 حتى تجد موضعًا يكون فيه العنصر الذي تم فرزه أقل من العنصر الجديد أو يساويه.
بعد إدخال العنصر الجديد في هذا الموضع.
كرر الخطوات من 2 إلى 5.
انسخ رمز الكود كما يلي:
إدراج الفراغ الثابت العام (int [] data) {
for (int Index = 1; Index < data. length; Index++) {
مفتاح int = البيانات[الفهرس];
موضع كثافة العمليات = الفهرس؛
// انقل القيم الأكبر إلى اليمين
بينما (الموضع > 0 && البيانات[الموضع - 1] > المفتاح) {
البيانات[الموضع] = البيانات[الموضع - 1]؛
موضع--؛
}
البيانات [الموضع] = المفتاح؛
}
}
2. فرز التل
فرز Shell هو نوع من فرز الإدراج. إنه تحسين لخوارزمية فرز الإدراج المباشر. وتسمى هذه الطريقة أيضًا تقليل الفرز التزايدي، لأن DL. تم تسمية شركة شل بهذا الاسم نسبة إلى اقتراحها في عام 1959.
يقترح فرز التل طريقة محسنة تعتمد على الخاصيتين التاليتين لفرز الإدراج:
يكون فرز الإدراج فعالاً للغاية عند العمل على بيانات تم فرزها تقريبًا، أي أنه يمكنه تحقيق كفاءة الفرز الخطي.
لكن فرز الإدراج غير فعال بشكل عام لأن فرز الإدراج لا يمكنه سوى نقل البيانات بمعدل بت واحد في كل مرة.
انسخ رمز الكود كما يلي:
ثابت <E يمتد للمقارنة<؟ سوبر E>> void shellSort(List<E> a) {
كثافة العمليات ح = 1؛
while (h < a.size()/3) h = h*3 + 1; // <O(n^(3/2)) بواسطة Knuth,1973>: 1, 4, 13, 40, 121, . ..
لـ (؛ ح >= 1؛ ح /= 3)
لـ (int i = h; i < a.size(); i++)
for (int j = i; j >= h && a.get(j).compareTo(a.get(jh)) < 0; j-=h)
Collections.swap(a, j, jh);
}
3. فرز الفقاعات
Bubble Sort (Bubble Sort، تُرجمت من تايوان كـ: Bubble Sort أو Bubble Sort) هي خوارزمية فرز بسيطة. فهو يتنقل بشكل متكرر عبر التسلسل المطلوب فرزه، ويقارن عنصرين في كل مرة ويتبادلهما إذا كانا في الترتيب الخاطئ. يتم تكرار عمل زيارة المصفوفة حتى لا تكون هناك حاجة لمزيد من التبادلات، مما يعني أنه تم فرز المصفوفة. يأتي اسم هذه الخوارزمية من حقيقة أن العناصر الأصغر سوف "تطفو" ببطء إلى أعلى المصفوفة من خلال المبادلة.
تعمل خوارزمية فرز الفقاعة على النحو التالي:
قارن بين العناصر المتجاورة، وإذا كان الأول أكبر من الثاني، قم بتبديلهما معًا.
افعل الشيء نفسه مع كل زوج من العناصر المتجاورة، بدءًا من الزوج الأول وانتهاءً بالزوج الأخير، وعند هذه النقطة يجب أن يكون العنصر الأخير هو أكبر رقم.
كرر الخطوات المذكورة أعلاه لجميع العناصر باستثناء العنصر الأخير.
استمر في تكرار الخطوات المذكورة أعلاه لعدد أقل وأقل من العناصر في كل مرة حتى لا يتبقى أي أزواج من الأرقام للمقارنة.
انسخ رمز الكود كما يلي:
فقاعة فارغة عامة ثابتة (int [] data) {
درجة الحرارة المؤقتة = 0؛
من أجل (int i = data.length - 1; i > 0; --i) {
boolean isSort = false;
لـ (int j = 0; j < i; ++j) {
إذا (البيانات[ي + 1] < البيانات[ي]) {
درجة الحرارة = البيانات[ي]؛
data[j] = data[j + 1];
البيانات[ي + 1] = درجة الحرارة؛
isSort = true;
}
}
// إذا حدث تبادل في حلقة داخلية، فاستمر في المقارنة، وإذا لم يحدث أي تبادل في حلقة داخلية، فسيتم اعتباره قد تم فرزه.
إذا (! فرز)
استراحة؛
}
}
4. الفرز السريع
يعد الفرز السريع تحسينًا لفرز الفقاعات. اقترحه CAR Hoare في عام 1962. فكرتها الأساسية هي تقسيم البيانات المراد فرزها إلى جزأين مستقلين من خلال فرز واحد، بحيث تكون جميع البيانات في جزء واحد أصغر من جميع البيانات الموجودة في الجزء الآخر، ثم تستخدم هذه الطريقة لفصل جزأين البيانات بسرعة. الفرز، يمكن إجراء عملية الفرز بأكملها بشكل متكرر، بحيث تصبح البيانات بأكملها تسلسلًا مرتبًا.
يستخدم الفرز السريع استراتيجية فرق تسد لتقسيم القائمة إلى قائمتين فرعيتين.
الخطوات هي:
يُطلق على اختيار عنصر من التسلسل اسم "المحور".
أعد ترتيب المصفوفة بحيث يتم وضع جميع العناصر الأصغر من القيمة الأساسية أمام القاعدة، ويتم وضع جميع العناصر الأكبر من القيمة الأساسية خلف القاعدة (يمكن أن يذهب نفس الرقم إلى أي من الجانبين). بعد خروج هذا القسم، تكون القاعدة في منتصف التسلسل. وهذا ما يسمى عملية التقسيم.
قم بفرز المصفوفة الفرعية للعناصر الأقل من القيمة الأساسية بشكل متكرر والمصفوفة الفرعية للعناصر الأكبر من القيمة الأساسية.
انسخ رمز الكود كما يلي:
/*
* أدوات أكثر كفاءة للفرز السريع
* استخدم القيمة المتوسطة اليسرى والوسطى واليمنى (@see #median()) للمحور، و
* الحلقة الداخلية الأكثر كفاءة لجوهر الخوارزمية.
*/
التصنيف السريع للفئة العامة {
النهائي العام الثابت CUTOFF = 11؛
/**
* خوارزمية الفرز السريع
*
*param arr مصفوفة من العناصر القابلة للمقارنة <br />
*/
عام ثابت <T يمتد للمقارنة<?
QuickSort(arr, 0, arr.length - 1);
}
/**
* احصل على متوسط اليسار والوسط واليمين <br />
* قم بترتيب هذه العناصر وإخفاء المحور بوضعها في نهاية المصفوفة
*
*param arr مصفوفة من العناصر القابلة للمقارنة <br />
* غادر @param الفهرس الموجود في أقصى يسار المصفوفة الفرعية <br />
* @param قم بتوجيه الفهرس الأيمن للمصفوفة الفرعية.<br />
* @عودة ت
*/
عام ثابت <T يمتد للمقارنة<? T median(T[] arr, int left, int right) {
int center = (يسار + يمين) / 2;
إذا (arr[left].compareTo(arr[center]) > 0)
SwapRef(arr, left, center);
إذا (arr[left].compareTo(arr[right]) > 0)
SwapRef(arr, left, right);
إذا (arr[center].compareTo(arr[right]) > 0)
SwapRef(arr, center, right);
SwapRef(arr, center, right - 1);
العودة آر [يمين - 1]؛
}
/**
* طريقة داخلية لفرز المصفوفة باستخدام خوارزمية الفرز السريع
*
*param arr مصفوفة من العناصر القابلة للمقارنة <br />
* غادر @param الفهرس الموجود في أقصى يسار المصفوفة الفرعية <br />
* @param يمين الفهرس الموجود في أقصى يمين المصفوفة الفرعية <br />
*/
خاص ثابت <T يمتد للمقارنة<? super T>> void QuickSort(T[] arr, int left, int right) {
إذا (يسار + قطع <= يمين) {
// ابحث عن المحور
T المحوري = الوسيط (arr، left، right)؛
// ابدأ التقسيم
int i = يسار، j = يمين - 1؛
ل (؛؛) {
بينما (arr[++i].compareTo(pivot) < 0);
بينما (arr[--j].compareTo(pivot) > 0);
إذا (ط <ي)
SwapRef(arr, i, j);
آخر
استراحة؛
}
// قم بتبديل المرجع المحوري مرة أخرى إلى المجموعة الصغيرة.
SwapRef(arr, i, right - 1);
QuickSort(arr, left, i - 1); // فرز المجموعة الصغيرة.
QuickSort(arr, i + 1, right);
} آخر {
// إذا كان العدد الإجمالي أقل من CUTOFF، نستخدم فرز الإدراج
// بدلاً من ذلك (لأنه أكثر كفاءة).
فرز (arr، الإدراج لليسار، لليمين)؛
}
}
/**
* طريقة تبديل المراجع في المصفوفة.<br />
*
*param arr مصفوفة من الكائنات <br />
* @param idx1 فهرس العنصر الأول <br />
* @param idx2 فهرس العنصر الثاني <br />
*/
عام ثابت <T> void SwapRef(T[] arr, int idx1, int idx2) {
T tmp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = tmp;
}
/**
* طريقة لفرز مصفوفة فرعية من البداية إلى النهاية عن طريق فرز الإدراج
* الخوارزمية <br />
*
*param arr مصفوفة من العناصر القابلة للمقارنة <br />
* @param ابدأ موضع البداية <br />
* @param أنهي موضع النهاية <br />
*/
عام ثابت <T يمتد للمقارنة<?
كثافة العمليات أنا؛
لـ (int j = start + 1; j <= end; j++) {
T tmp = arr[j];
for (i = j; i > start && tmp.compareTo(arr[i - 1]) < 0; i--) {
arr[i] = arr[i - 1];
}
arr[i] = tmp;
}
}
طباعة باطلة ثابتة خاصة (Integer[] c) {
لـ (int i = 0; i < c.length; i++)
System.out.print(c[i] + ""،");
System.out.println();
}
public static void main(String[] args) {
عدد صحيح[] البيانات = {10، 4، 9، 23، 1، 45، 27، 5، 2}؛
System.out.println("فقاعة الفرز...");
printArray(data);
فرز سريع(بيانات);
printArray(data);
}
}
5. فرز الاختيار
فرز التحديد هو خوارزمية فرز بسيطة وبديهية. وإليك كيف يعمل. أولاً، ابحث عن العنصر الأصغر (الكبير) في التسلسل غير المصنف وقم بتخزينه في بداية التسلسل المصنف، ثم تابع العثور على العنصر الأصغر (الكبير) من العناصر المتبقية غير المصنفة، ثم ضعه في نهاية التسلسل تسلسل مرتبة. وهكذا حتى يتم فرز جميع العناصر.
نظرًا لأن كل عملية تحديد العناصر سيكون لها عملية فرعية لاختيار الحد الأدنى من القيمة، فإن الناس يطلقون عليها اسم الفرز بالاختيار.
على سبيل المثال، في التسلسل 5 8 5 2 9، نعلم أنه سيتم تبادل العنصر الأول 5 مع 2 في التمريرة الأولى، ثم سيتم تدمير الترتيب النسبي للعنصرين 5 في التسلسل الأصلي، وبالتالي يتم فرز التحديد خوارزمية الفرز غير مستقرة.
انسخ رمز الكود كما يلي:
تحديد الفراغ الثابت العام (int[] data) {
int minIndex = 0;
درجة الحرارة المؤقتة = 0؛
لـ (int i = 0; i < data. length; i++) {
minIndex = i; // الحد الأدنى لفهرس صفيف البيانات للمنطقة غير المرتبة
for (int j = i + 1; j < data. length; j++) { // ابحث عن أصغر البيانات في المنطقة غير المرتبة واحفظ صفيفها منخفضًا
إذا (البيانات[ي] < البيانات[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) { // إذا لم يكن الحد الأدنى لموضع المنطقة غير المرتبة هو البيانات الأولى الافتراضية، فاستبدلها.
درجة الحرارة = البيانات[i];
data[i] = data[minIndex];
data[minIndex] = temp;
}
}
}
6. دمج الفرز
يعد فرز الدمج خوارزمية فرز فعالة تعتمد على عمليات الدمج. هذه الخوارزمية هي تطبيق نموذجي للغاية يستخدم طريقة فرق تسد (فرق تسد).
عملية عملية الدمج هي كما يلي:
تقدم بطلب للحصول على مساحة بحيث يكون حجمها هو مجموع التسلسلين المفرزين. يتم استخدام هذه المساحة لتخزين التسلسل المدمج.
قم بتعيين مؤشرين، المواضع الأولية هي مواضع البداية للتسلسلين المصنفين.
قارن العناصر المشار إليها بالمؤشرين، وحدد العنصر الصغير نسبيًا وضعه في مساحة الدمج، وحرك المؤشر إلى الموضع التالي.
كرر الخطوة 3 حتى يصل المؤشر إلى نهاية التسلسل.
نسخ كافة العناصر المتبقية من التسلسل الآخر مباشرة إلى نهاية التسلسل المدمج.
انسخ رمز الكود كما يلي:
public static int[] mergeSort(int[] arr) {// دمج الفرز - العودية
إذا (arr. length == 1) {
العودة آر؛
}
int half = arr.length / 2;
int[] arr1 = new int[half];
int[] arr2 = new int[arr.length - half];
System.arraycopy(arr, 0, arr1, 0, arr1.length);
System.arraycopy(arr, half, arr2, 0, arr2.length);
arr1 = mergeSort(arr1);
arr2 = mergeSort(arr2);
إرجاع mergeSortSub(arr1, arr2);
}
خاص ثابت int[] mergeSortSub(int[] arr1, int[] arr2) {// دمج الروتين الفرعي
int[] result = new int[arr1.length + arr2.length];
كثافة العمليات ط = 0؛
كثافة العمليات ي = 0;
كثافة العمليات ك = 0؛
بينما (صحيح) {
إذا (arr1[i] < arr2[j]) {
النتيجة[ك] = arr1[i];
إذا (++i > arr1.length - 1) {
استراحة؛
}
} آخر {
النتيجة[ك] = arr2[j];
إذا (++j > arr2.length - 1) {
استراحة؛
}
}
ك++;
}
لـ (؛ i < arr1.length؛ i++) {
النتيجة[++k] = arr1[i];
}
لـ (; j < arr2.length; j++) {
النتيجة[++k] = arr2[j];
}
نتيجة الإرجاع؛
}
الرمز الكامل (باستثناء الفرز السريع)
انسخ رمز الكود كما يلي:
package com.clzhang.sample.thinking;
import java.util.*;
/**
* تنفيذ Java للعديد من خوارزميات الفرز الشائعة
* @المؤلف أيسر
*
*/
الطبقة العامة CommonSort {
/**
* يتم وصف الخوارزمية المحددة لفرز الإدراج على النحو التالي:
* 1. بدءاً من العنصر الأول، يمكن اعتبار العنصر قد تم فرزه
* 2. أخرج العنصر التالي وامسحه ضوئيًا من الخلف إلى الأمام في تسلسل العناصر التي تم فرزها
* 3. إذا كان العنصر (المفرز) أكبر من العنصر الجديد، انقل العنصر إلى الموضع التالي
* 4. كرر الخطوة 3 حتى تجد الموضع الذي يكون فيه العنصر المفرز أقل من أو يساوي العنصر الجديد
* 5. بعد إدخال العنصر الجديد في هذا الموضع
* 6. كرر الخطوات من 2 إلى 5
*/
إدراج الفراغ الثابت العام (int [] data) {
for (int Index = 1; Index < data. length; Index++) {
مفتاح int = البيانات[الفهرس];
موضع كثافة العمليات = الفهرس؛
// انقل القيم الأكبر إلى اليمين
بينما (الموضع > 0 && البيانات[الموضع - 1] > المفتاح) {
البيانات[الموضع] = البيانات[الموضع - 1]؛
موضع--؛
}
البيانات [الموضع] = المفتاح؛
}
}
/**
* فرز التل، يرجى الرجوع إلى ويكيبيديا للحصول على أفكار تنفيذ الخوارزمية المناسبة لعدد كبير من عمليات الفرز.
*/
ثابت <E يمتد للمقارنة<؟ سوبر E>> void shellSort(List<E> a) {
كثافة العمليات ح = 1؛
while (h < a.size()/3) h = h*3 + 1; // <O(n^(3/2)) بواسطة Knuth,1973>: 1, 4, 13, 40, 121, . ..
لـ (؛ ح >= 1؛ ح /= 3)
لـ (int i = h; i < a.size(); i++)
for (int j = i; j >= h && a.get(j).compareTo(a.get(jh)) < 0; j-=h)
Collections.swap(a, j, jh);
}
/**
*عملية خوارزمية فرز الفقاعة هي كما يلي:
* 1. قارن العناصر المتجاورة. إذا كان الأول أكبر من الثاني، قم بتبديلهما معًا.
* 2. قم بنفس العمل لكل زوج من العناصر المتجاورة، من الزوج الأول في البداية إلى الزوج الأخير في النهاية. عند هذه النقطة، يجب أن يكون العنصر الأخير هو أكبر عدد.
* 3. كرر الخطوات المذكورة أعلاه لجميع العناصر باستثناء العنصر الأخير.
* 4. استمر في تكرار الخطوات المذكورة أعلاه لعدد أقل وأقل من العناصر في كل مرة حتى لا يكون هناك أزواج من الأرقام للمقارنة. [1]
*/
فقاعات باطلة ثابتة عامة (int [] data) {
درجة الحرارة المؤقتة = 0؛
من أجل (int i = data.length - 1; i > 0; --i) {
boolean isSort = false;
لـ (int j = 0; j < i; ++j) {
إذا (البيانات[ي + 1] < البيانات[ي]) {
درجة الحرارة = البيانات[ي]؛
data[j] = data[j + 1];
البيانات[ي + 1] = درجة الحرارة؛
isSort = true;
}
}
// إذا حدث تبادل في حلقة داخلية، فاستمر في المقارنة، وإذا لم يحدث أي تبادل في حلقة داخلية، فسيتم اعتباره قد تم فرزه.
إذا (! فرز)
استراحة؛
}
}
/**
*الفكرة الأساسية للفرز بالاختيار هي:
* 1. أثناء عملية اجتياز المصفوفة، إذا كنت تمثل رقم التسلسل الحالي الذي يحتاج إلى الفرز، فأنت بحاجة إلى العثور على الحد الأدنى للقيمة بين [i+1...n-1] المتبقية.
* 2. ثم استبدل الحد الأدنى للقيمة الموجودة بالقيمة المشار إليها بـ i.
* نظرًا لأن كل عملية تحديد العناصر سيكون لها عملية فرعية لاختيار الحد الأدنى من القيمة، فإن الناس يطلقون عليها بوضوح فرز الاختيار.
* @param data
*/
تحديد الفراغ الثابت العام (int[] data) {
int minIndex = 0;
درجة الحرارة المؤقتة = 0؛
لـ (int i = 0; i < data. length; i++) {
minIndex = i; // الحد الأدنى من فهرس صفيف البيانات للمنطقة غير المرتبة
for (int j = i + 1; j < data. length; j++) { // ابحث عن أصغر البيانات في المنطقة غير المرتبة واحفظ صفيفها منخفضًا
إذا (البيانات[ي] < البيانات[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) { // إذا لم يكن الحد الأدنى لموضع المنطقة غير المرتبة هو البيانات الأولى الافتراضية، فاستبدلها.
درجة الحرارة = البيانات[i];
data[i] = data[minIndex];
data[minIndex] = temp;
}
}
}
/**
* تتم عملية الدمج كما يلي:
* 1. قم بالتقدم للحصول على مساحة بحيث يكون حجمها هو مجموع التسلسلين المفرزين. يتم استخدام هذه المساحة لتخزين التسلسل المدمج.
* 2. قم بتعيين مؤشرين، المواضع الأولية هي مواضع البداية للتسلسلين المصنفين.
* 3. قارن بين العناصر المشار إليها بالمؤشرين، وحدد العنصر الصغير نسبيًا وضعه في مساحة الدمج، وحرك المؤشر إلى الموضع التالي
* 4. كرر الخطوة 3 حتى يصل المؤشر إلى نهاية التسلسل
* 5. انسخ جميع العناصر المتبقية من التسلسل الآخر مباشرة إلى نهاية التسلسل المدمج
*/
public static int[] mergeSort(int[] arr) {// دمج الفرز - العودية
إذا (arr. length == 1) {
العودة آر؛
}
int half = arr.length / 2;
int[] arr1 = new int[half];
int[] arr2 = new int[arr.length - half];
System.arraycopy(arr, 0, arr1, 0, arr1.length);
System.arraycopy(arr, half, arr2, 0, arr2.length);
arr1 = mergeSort(arr1);
arr2 = mergeSort(arr2);
إرجاع mergeSortSub(arr1, arr2);
}
خاص ثابت int[] mergeSortSub(int[] arr1, int[] arr2) {// دمج الروتين الفرعي
int[] result = new int[arr1.length + arr2.length];
كثافة العمليات ط = 0؛
كثافة العمليات ي = 0;
كثافة العمليات ك = 0؛
بينما (صحيح) {
إذا (arr1[i] < arr2[j]) {
النتيجة[ك] = arr1[i];
إذا (++i > arr1.length - 1) {
استراحة؛
}
} آخر {
النتيجة[ك] = arr2[j];
إذا (++j > arr2.length - 1) {
استراحة؛
}
}
ك++;
}
لـ (؛ i < arr1.length؛ i++) {
النتيجة[++k] = arr1[i];
}
لـ (; j < arr2.length; j++) {
النتيجة[++k] = arr2[j];
}
نتيجة الإرجاع؛
}
طباعة باطلة ثابتة خاصة (int[] c) {
لـ (int i = 0; i < c.length; i++)
System.out.print(c[i] + ""،");
System.out.println();
}
الفراغ الثابت العام الرئيسي (String []args) {
بيانات int[] = {10,4,9,23,1,45,27,5,2};
System.out.println("فقاعة الفرز...");
int[] a = data.clone();
printArray(a);
bubbleSort(a);
printArray(a);
System.out.println("selectSort...");
int[] b = data.clone();
printArray(b);
حدد فرز (ب)؛
printArray(b);
System.out.println("insertionSort...");
int[] c = data.clone();
printArray(c);
InsertionSort(c);
printArray(c);
System.out.println("shellSort...");
List<Integer> list = new ArrayList<Integer>();
ل(int i=0;i<data.length;i++)
list.add(data[i]);
System.out.println(list);
shellSort(list);
System.out.println(list);
System.out.println("mergeSort...");
int[] d = data.clone();
printArray(d);
printArray(mergeSort(d));
}
}