أفضل عشر خوارزميات فرز كلاسيكية

#أفضل عشر خوارزميات فرز كلاسيكية (عرض توضيحي بالرسوم المتحركة) من: مدونة داموناري الشخصية

النص الأصلي: http://blog.damonare.cn/2016/12/20/十大经典排序算法总结（javascript描述）/

##0. نظرة عامة على الخوارزمية

##0.1 تصنيف الخوارزمية

يمكن تقسيم عشر خوارزميات فرز شائعة إلى فئتين عريضتين:

فرز المقارنة الزمنية غير الخطية: تحديد الترتيب النسبي بين العناصر من خلال المقارنة. وبما أن التعقيد الزمني لا يمكن أن يتجاوز O(nlogn)، فإنه يطلق عليه فرز مقارنة الوقت غير الخطي. الفرز الخطي غير المقارن للوقت: لا يحدد الترتيب النسبي بين العناصر من خلال المقارنة. يمكنه اختراق الحد الأدنى للفرز القائم على المقارنة وتشغيله في الوقت الخطي، لذلك يطلق عليه الفرز غير المقارن للوقت الخطي.

0.2 تعقيد الخوارزمية

0.3 المفاهيم ذات الصلة

مستقر: إذا كان a موجودًا في الأصل أمام b، وa=b، فسيظل a موجودًا أمام b بعد الفرز. غير مستقر: إذا كان a موجودًا في الأصل أمام b، وa=b، فقد يظهر a بعد b بعد الفرز. التعقيد الزمني: إجمالي عدد العمليات على البيانات المصنفة. يعكس نمط عدد العمليات عندما يتغير n. تعقيد المساحة: يشير إلى قياس مساحة التخزين المطلوبة عند تنفيذ خوارزمية في جهاز الكمبيوتر. وهي أيضًا دالة لحجم البيانات n.

1. الفرز الفقاعي (الفرز الفقاعي)

فرز الفقاعة هو خوارزمية فرز بسيطة. فهو يتنقل بشكل متكرر عبر التسلسل المطلوب فرزه، ويقارن عنصرين في كل مرة ويتبادلهما إذا كانا في الترتيب الخاطئ. يتم تكرار عمل زيارة المصفوفة حتى لا تكون هناك حاجة لمزيد من التبادلات، مما يعني أنه تم فرز المصفوفة. يأتي اسم هذه الخوارزمية من حقيقة أن العناصر الأصغر سوف “تطفو” ببطء إلى أعلى المصفوفة من خلال المبادلة.

1.1 وصف الخوارزمية

1. قارن العناصر المتجاورة. فإن كان الأول أكبر من الثاني بدّل بينهما؛

2. قم بنفس العمل لكل زوج من العناصر المتجاورة، من الزوج الأول في البداية إلى الزوج الأخير في النهاية، بحيث يكون العنصر الأخير هو أكبر عدد؛

3. كرر الخطوات المذكورة أعلاه لجميع العناصر باستثناء العنصر الأخير؛

4. كرر الخطوات من 1 إلى 3 حتى اكتمال الفرز.

1.2 عرض الرسوم المتحركة

1.3 تنفيذ الكود

function bubbleSort(arr) {
var len = arr.length;
for (var i = 0; i < len - 1; i++) {
for (var j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j+1]) { // 相邻元素两两对比
var temp = arr[j+1]; // 元素交换
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
return arr;

2. فرز التحديد

فرز التحديد هو خوارزمية فرز بسيطة وبديهية. كيف يعمل: ابحث أولاً عن العنصر الأصغر (الكبير) في التسلسل غير المصنف، وقم بتخزينه في بداية التسلسل المفرز، ثم تابع العثور على العنصر الأصغر (الكبير) من العناصر المتبقية غير المصنفة، ثم ضعه في نهاية التسلسل المفرز. وهكذا حتى يتم فرز جميع العناصر.

2.1 وصف الخوارزمية

يمكن لفرز الاختيار المباشر لسجلات n الحصول على النتائج المطلوبة من خلال تمريرات فرز الاختيار المباشر n-1. يتم وصف الخوارزمية المحددة على النحو التالي:

• الحالة الأولية: المنطقة غير المرتبة هي R[1…n]، والمنطقة المرتبة فارغة؛
• عندما يبدأ الفرز i-th (i=1,2,3…n-1)، تكون المساحة المرتبة الحالية والمنطقة غير المرتبة هي R[1…i-1] وR(i…n) على التوالي. تحدد عملية الفرز هذه السجل R[k] بأصغر كلمة رئيسية من المنطقة غير المرتبة الحالية، وتتبادله مع السجل الأول R في المنطقة غير المرتبة، بحيث تصبح R[1…i] وR[i+1…n) منطقة مرتبة جديدة مع زيادة عدد السجلات بمقدار 1 ومنطقة جديدة غير مرتبة مع تقليل عدد السجلات بمقدار 1 على التوالي؛
• في نهاية تمريرات n-1، يتم فرز المصفوفة.

2.2 عرض الرسوم المتحركة

2.3 تنفيذ الكود

function selectionSort(arr) {
var len = arr.length;
var minIndex, temp;
for (var i = 0; i < len - 1; i++) {
minIndex = i;
for (var j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) { // 寻找最小的数
minIndex = j; // 将最小数的索引保存
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}

2.4 تحليل الخوارزمية

واحدة من أكثر خوارزميات الفرز استقرارًا، لأنه بغض النظر عن البيانات التي يتم إدخالها، فإن التعقيد الزمني هو O(n2)، لذلك عند استخدامها، كلما كان حجم البيانات أصغر، كان ذلك أفضل. قد تكون الميزة الوحيدة هي أنها لا تشغل مساحة إضافية على الذاكرة. من الناحية النظرية، قد يكون الفرز بالاختيار أيضًا هو أسلوب الفرز الأكثر شيوعًا الذي يفكر فيه معظم الناس عند الفرز.

3. فرز الإدراج

وصف الخوارزمية لفرز الإدراج (فرز الإدراج) هو خوارزمية فرز بسيطة وبديهية. إنه يعمل عن طريق بناء تسلسل مرتب. بالنسبة للبيانات غير المصنفة، فإنه يقوم بالمسح من الخلف إلى الأمام بالتسلسل المفرز، ويجد الموضع المقابل ويدرجه.

3.1 وصف الخوارزمية

بشكل عام، يتم تنفيذ فرز الإدراج على المصفوفات باستخدام موضعي. يتم وصف الخوارزمية المحددة على النحو التالي:

1. بدءًا من العنصر الأول، يمكن اعتبار العنصر قد تم فرزه؛
2. أخرج العنصر التالي وامسحه ضوئيًا من الخلف إلى الأمام في تسلسل العناصر التي تم فرزها؛
3. إذا كان العنصر (المفرز) أكبر من العنصر الجديد، انقل العنصر إلى الموضع التالي؛
4. كرر الخطوة 3 حتى تجد الموضع الذي يكون فيه العنصر المفرز أقل من أو يساوي العنصر الجديد؛
5. بعد إدخال العنصر الجديد في هذا الموضع؛
6. كرر الخطوات من 2 إلى 5.

3.2 عرض GIF

3.3 تنفيذ التعليمات البرمجية

function insertionSort(arr) {
var len = arr.length;
var preIndex, current;
for (var i = 1; i < len; i++) {
preIndex = i - 1;
current = arr[i];
while (preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current;
}
return arr;
}

3.4 تحليل الخوارزمية

في تنفيذ فرز الإدراج، يتم عادةً استخدام الفرز الموضعي (أي الفرز الذي يستخدم مساحة إضافية O(1) فقط). لذلك، أثناء عملية المسح من الخلف إلى الأمام، يجب نقل العناصر التي تم فرزها بشكل متكرر وتدريجي إلى الخلف لتوفير مساحة لإدراج أحدث العناصر.

4. نوع الصدفة

اخترعتها شركة شل في عام 1959، وكانت أول خوارزمية فرز تخترق O(n2) وكانت نسخة محسنة من فرز الإدراج البسيط. وهو يختلف عن الفرز بالإدراج لأنه يقارن العناصر الأبعد أولاً. يُطلق على فرز التل أيضًا اسم تقليل الزيادة.

4.1 وصف الخوارزمية

أولاً، يتم تقسيم تسلسل السجل بأكمله المراد فرزه إلى عدة تسلسلات فرعية لفرز الإدراج المباشر. تم وصف الخوارزمية المحددة:

حدد تسلسلاً تزايديًا t1, t2,…,tk، حيث ti>tj, tk=1;

قم بفرز التسلسل k مرات وفقًا لعدد التسلسلات الإضافية k؛

في كل تمريرة فرز، يتم تقسيم العمود المراد فرزه إلى عدة متتابعات بطول m وفقًا للزيادة المقابلة ti، ويتم إجراء فرز الإدراج المباشر على كل جدول فرعي. فقط عندما يكون عامل الزيادة 1، تتم معالجة التسلسل بأكمله كجدول، ويكون طول الجدول هو طول التسلسل بأكمله.

4.2 عرض GIF

4.3 تنفيذ التعليمات البرمجية

function shellSort(arr) {
var len = arr.length,
temp,
gap = 1;
while (gap < len / 3) { // 动态定义间隔序列
gap = gap * 3 + 1;
}
for (gap; gap > 0; gap = Math.floor(gap / 3)) {
for (var i = gap; i < len; i++) {
temp = arr[i];
for (var j = i-gap; j > 0 && arr[j]> temp; j-=gap) {
arr[j + gap] = arr[j];
}
arr[j + gap] = temp;
}
}
return arr;
}

4.4 تحليل الخوارزمية

يكمن جوهر فرز التل في تحديد التسلسل الزمني. يمكن ضبط التسلسل الزمني مسبقًا أو تعريفه ديناميكيًا. تم اقتراح خوارزمية التحديد الديناميكي للتسلسلات الفاصلة بواسطة روبرت سيدجويك، المؤلف المشارك لكتاب “الخوارزميات (الإصدار الرابع)”.

5. دمج الفرز

يعد فرز الدمج خوارزمية فرز فعالة تعتمد على عمليات الدمج. هذه الخوارزمية هي تطبيق نموذجي للغاية يستخدم طريقة فرق تسد (فرق تسد). دمج التتابعات المطلوبة بالفعل للحصول على تسلسل مرتب بالكامل؛ أي، قم أولاً بإجراء كل سلسلة لاحقة بشكل منظم، ثم قم بإجراء الأجزاء اللاحقة بشكل منظم. إذا تم دمج قائمتين مرتبة في قائمة مرتبة واحدة، يسمى ذلك دمجًا ثنائي الاتجاه.

5.1 وصف الخوارزمية

قسّم تسلسل الإدخال بالطول n إلى تسلسلين فرعيين بالطول n/2؛

استخدم فرز الدمج على هاتين النتيجتين الفرعيتين؛

دمج تسلسلين فرعيين تم فرزهما في تسلسل فرز نهائي.

5.2 عرض GIF

5.3 تنفيذ التعليمات البرمجية

function mergeSort(arr) { // 采用自上而下的递归方法
var len = arr.length;
if (len < 2) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
var result = [];
while (left.length>0 && right.length>0) {
if (left[0] <= right[0])="" {<="" span="">
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
}

5.4 تحليل الخوارزمية

يعد فرز الدمج طريقة فرز مستقرة. مثل فرز التحديد، لا يتأثر أداء فرز الدمج بالبيانات المدخلة، ولكن أدائه أفضل بكثير من فرز التحديد لأن التعقيد الزمني يكون دائمًا O(nlogn). السعر هو مساحة ذاكرة إضافية.

6. الفرز السريع

الفكرة الأساسية للفرز السريع هي فصل السجلات المراد فرزها إلى جزأين مستقلين من خلال فرز واحد. إذا كانت الكلمات الأساسية لجزء واحد من السجل أصغر من الكلمات الأساسية للجزء الآخر، فيمكن فرز جزأين السجلات بشكل منفصل لتحقيق ترتيب التسلسل بأكمله.

6.1 وصف الخوارزمية

يستخدم الفرز السريع طريقة فرق تسد لتقسيم القائمة إلى قائمتين فرعيتين. يتم وصف الخوارزمية المحددة على النحو التالي:

انتقاء عنصر من التسلسل يسمى “المحور”؛

أعد ترتيب المصفوفة بحيث يتم وضع جميع العناصر الأصغر من القيمة الأساسية أمام القاعدة، ويتم وضع جميع العناصر الأكبر من القيمة الأساسية خلف القاعدة (يمكن أن يذهب نفس الرقم إلى أي من الجانبين). بعد خروج هذا القسم، تكون القاعدة في منتصف التسلسل. وهذا ما يسمى عملية التقسيم.

قم بفرز المصفوفة الفرعية للعناصر الأقل من القيمة الأساسية بشكل متكرر والمصفوفة الفرعية للعناصر الأكبر من القيمة الأساسية.

6.2 عرض GIF

6.3 تنفيذ التعليمات البرمجية

function quickSort(arr, left, right) {
var len = arr.length,
partitionIndex,
left = typeof left != 'number' ? 0 : left,
right = typeof right != 'number' ? len - 1 : right;
if (left < right) {
partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex-1);
quickSort(arr, partitionIndex+1, right);
}
return arr;
}
function partition(arr, left ,right) { // 分区操作
var pivot = left, // 设定基准值（pivot）
index = pivot + 1;
for (var i = index; i <= right;="" i++)="" {<="" span="">
if (arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index-1;
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

7. فرز الكومة

يشير Heapsort إلى خوارزمية فرز مصممة باستخدام بنية بيانات الكومة. التراص عبارة عن بنية تقارب شجرة ثنائية كاملة وتفي بخصائص التراص: أي أن القيمة الرئيسية أو فهرس العقدة الفرعية يكون دائمًا أصغر (أو أكبر) من العقدة الأصلية.

7.1 وصف الخوارزمية

أنشئ التسلسل الأولي للكلمات الأساسية التي سيتم فرزها (R1، R2…Rn) في كومة علوية كبيرة، وهي المنطقة الأولية غير المرتبة؛

استبدل العنصر العلوي R[1] بالعنصر الأخير R[n]، ثم احصل على منطقة غير مرتبة جديدة (R1, R2,…Rn-1) ومنطقة مرتبة جديدة (Rn)، واستيفاء R[1,2…n-1]<=r[n];<span=“”></=r[n];<>

نظرًا لأن الجزء العلوي الجديد R[1] من الكومة بعد التبادل قد ينتهك خصائص الكومة، فمن الضروري ضبط المنطقة المضطربة الحالية (R1، R2،…Rn-1) إلى كومة جديدة، ثم تبادل R[1] مع العنصر الأخير من المنطقة المضطربة مرة أخرى للحصول على منطقة مضطربة جديدة (R1، R2…Rn-2) ومنطقة مرتبة جديدة (Rn-1، Rn). يتم تكرار هذه العملية حتى يصبح عدد العناصر في المنطقة المطلوبة n-1، ثم تكتمل عملية الفرز بأكملها.

7.2 عرض GIF

7.3 تنفيذ التعليمات البرمجية

var len; // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量

function buildMaxHeap(arr) { // 建立大顶堆

len = arr.length;

for (var i = Math.floor(len/2); i >= 0; i--) {

heapify(arr, i);

}

}

function heapify(arr, i) { // 堆调整

var left = 2 * i + 1,

right = 2 * i + 2,

largest = i;

if (left < len && arr[left] > arr[largest]) {

largest = left;

}

if (right < len && arr[right] > arr[largest]) {

largest = right;

}

if (largest != i) {

swap(arr, i, largest);

heapify(arr, largest);

}

}

function swap(arr, i, j) {

var temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

function heapSort(arr) {

buildMaxHeap(arr);

for (var i = arr.length - 1; i > 0; i--) {

swap(arr, 0, i);

len--;

heapify(arr, 0);

}

return arr;

}

8. فرز العد

فرز العد ليس خوارزمية فرز قائمة على المقارنة. يكمن جوهرها في تحويل قيم بيانات الإدخال إلى مفاتيح وتخزينها في مساحة مصفوفة مفتوحة بشكل إضافي. كفرز التعقيد الزمني الخطي، يتطلب فرز العد أن تكون بيانات الإدخال أعدادًا صحيحة ضمن نطاق معين.

8.1 وصف الخوارزمية

ابحث عن العناصر الأكبر والأصغر في المصفوفة المراد فرزها؛

حساب عدد مرات ظهور كل عنصر بالقيمة i في المصفوفة وتخزينه في العنصر i في المصفوفة C؛

تجميع كافة الأعداد (بدءًا من العنصر الأول في لغة C، تتم إضافة كل عنصر إلى العنصر السابق)؛

املأ المصفوفة المستهدفة في الاتجاه المعاكس: ضع كل عنصر i في العنصر C(i) من المصفوفة الجديدة، واطرح 1 من C(i) لكل عنصر تم وضعه.

8.2 عرض GIF

8.3 تنفيذ التعليمات البرمجية

function countingSort(arr, maxValue) {
var bucket = new Array(maxValue + 1),
sortedIndex = 0;
arrLen = arr.length,
bucketLen = maxValue + 1;
for (var i = 0; i < arrLen; i++) {
if (!bucket[arr[i]]) {
bucket[arr[i]] = 0;
}
bucket[arr[i]]++;
}
for (var j = 0; j < bucketLen; j++) {
while(bucket[j] > 0) {
arr[sortedIndex++] = j;
bucket[j]--;
}
}
return arr;
}

8.4 تحليل الخوارزمية

فرز العد هو خوارزمية فرز مستقرة. عندما تكون عناصر الإدخال عبارة عن أعداد صحيحة بين 0 و k، يكون التعقيد الزمني هو O(n+k) ويكون التعقيد المكاني أيضًا O(n+k). سرعة الفرز أسرع من أي خوارزمية فرز مقارنة. يعد فرز العد خوارزمية فرز فعالة للغاية عندما لا تكون k كبيرة جدًا وتكون التسلسلات مركزة نسبيًا.

9. فرز الجرافة

يعتبر فرز الجرافة بمثابة نسخة مطورة من فرز العد. إنه يستخدم علاقة رسم الخرائط للوظائف. يكمن مفتاح الكفاءة في تحديد وظيفة رسم الخرائط هذه. مبدأ عمل فرز الجرافة: افترض أن البيانات المدخلة تخضع لتوزيع موحد، وقسم البيانات إلى عدد محدود من المجموعات، ثم قم بفرز كل مجموعة على حدة (من الممكن استخدام خوارزميات فرز أخرى أو الاستمرار في استخدام فرز الجرافة بطريقة متكررة).

9.1 وصف الخوارزمية

قم بتعيين مصفوفة كمية كدلو فارغ؛

اجتياز بيانات الإدخال ووضع البيانات في المجموعات المقابلة واحدة تلو الأخرى؛

قم بفرز كل دلو غير فارغ؛

قم بتسلسل البيانات المصنفة من المجموعات غير الفارغة.9.2 عرض الصورة

9.3 تنفيذ التعليمات البرمجية

function bucketSort(arr, bucketSize) {
if (arr.length === 0) {
return arr;
}
var i;
var minValue = arr[0];
var maxValue = arr[0];
for (i = 1; i < arr.length; i++) {
if (arr[i] < minValue) {
minValue = arr[i]; // 输入数据的最小值
} else if (arr[i] > maxValue) {
maxValue = arr[i]; // 输入数据的最大值
}
}
// 桶的初始化
var DEFAULT_BUCKET_SIZE = 5; // 设置桶的默认数量为5
bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
var buckets = new Array(bucketCount);
for (i = 0; i < buckets.length; i++) {
buckets[i] = [];
}
// 利用映射函数将数据分配到各个桶中
for (i = 0; i < arr.length; i++) {
buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
}
arr.length = 0;
for (i = 0; i < buckets.length; i++) {
insertionSort(buckets[i]); // 对每个桶进行排序，这里使用了插入排序
for (var j = 0; j < buckets[i].length; j++) {
arr.push(buckets[i][j]);
}
}
return arr;
}

9.4 تحليل الخوارزمية

يستخدم فرز الجرافة الوقت الخطي O(n) في أفضل الأحوال. يعتمد التعقيد الزمني لفرز الجرافة على التعقيد الزمني لفرز البيانات بين الدلاء، لأن التعقيد الزمني للأجزاء الأخرى هو O(n). من الواضح أنه كلما كانت المجموعات المقسمة أصغر، قلت البيانات الموجودة بين كل مجموعة، وقل الوقت الذي يستغرقه الفرز. لكن استهلاك المساحة المقابل سيزداد.

10. فرز الجذر

الفرز الجذري هو الفرز حسب الترتيب المنخفض أولاً، ثم التجميع؛ ثم قم بالفرز حسب الترتيب العالي، ثم قم بالتجميع؛ وهكذا حتى الدرجة الأعلى. في بعض الأحيان، يكون لبعض السمات ترتيب أولوية، ويتم فرزه حسب الأولوية المنخفضة أولاً، ثم حسب الأولوية العالية. الترتيب النهائي هو أن أولئك الذين لديهم أولوية أعلى يأتون أولاً، وأولئك الذين لديهم نفس الأولوية العالية والأولوية الأقل يأتون أولاً.

10.1 وصف الخوارزمية

الحصول على الحد الأقصى لعدد في المصفوفة والحصول على عدد الأرقام؛

arr هو المصفوفة الأصلية، وكل بتة مأخوذة من أدنى بتة لتكوين مصفوفة الجذر؛

إجراء فرز العد على الجذر (باستخدام ميزة فرز العد المناسبة لأرقام النطاق الصغير)؛

10.2 عرض GIF

10.3 تنفيذ الكود

// LSD Radix Sort
var counter = [];
function radixSort(arr, maxDigit) {
var mod = 10;
var dev = 1;
for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
for(var j = 0; j < arr.length; j++) {
var bucket = parseInt((arr[j] % mod) / dev);
if(counter[bucket]==null) {
counter[bucket] = [];
}
counter[bucket].push(arr[j]);
}
var pos = 0;
for(var j = 0; j < counter.length; j++) {
var value = null;
if(counter[j]!=null) {
while ((value = counter[j].shift()) != null) {
arr[pos++] = value;
}
}
}
}
return arr;
}

10.4 تحليل الخوارزمية

يعتمد الفرز الجذري على الفرز المنفصل والجمع المنفصل، لذلك فهو مستقر. ومع ذلك، فإن أداء الفرز الجذري أسوأ قليلاً من فرز الجرافة. يتطلب كل تخصيص لمجموعة من الكلمات الرئيسية تعقيدًا زمنيًا O(n)، ويتطلب الحصول على تسلسل كلمات رئيسية جديدة بعد التخصيص تعقيدًا زمنيًا O(n). إذا كان من الممكن تقسيم البيانات المراد فرزها إلى كلمات رئيسية d، فسيكون التعقيد الزمني لفرز الجذر هو O(d*2n). بالطبع، d أصغر بكثير من n، لذا فهو خطي بشكل أساسي.

التعقيد المكاني لفرز الجذر هو O(n+k)، حيث k هو عدد الجرافات. بشكل عام n >> k، لذا فإن المساحة الإضافية تحتاج إلى n تقريبًا.