المقابلات المكتوبة غالبًا ما تتضمن خوارزميات مختلفة. تقدم هذه المقالة باختصار بعض الخوارزميات الشائعة الاستخدام وتنفيذها في JavaScript.
1. أدخل الفرز
1) مقدمة في الخوارزمية
وصف الخوارزمية لعلم الإدراج هو خوارزمية فرز بسيطة وبديهية. إنه يعمل عن طريق إنشاء تسلسل مرتبة ، للبيانات غير المصنفة ، ومسح الضوئي للخلف وللأمام في التسلسل المرتبة ، ابحث عن الموضع المقابل وأدخله. في تنفيذ فرز الإدراج ، عادة ما يتم استخدام الفرز في مكان (أي ، المساحة الإضافية لـ O (1) مطلوبة) ، لذلك أثناء عملية المسح من الخلف إلى الأمام ، يجب نقل العناصر المرتبة بشكل متكرر إلى الوراء لتوفير مساحة للإدراج لأحدث العناصر.
2) وصف الخوارزمية والتنفيذ
بشكل عام ، يتم تنفيذ فرز الإدراج على صفيف باستخدام مكانه. يوصف الخوارزمية المحددة على النحو التالي:
بدءا من العنصر الأول ، يمكن اعتبار العنصر قد تم فرزه ؛
قم بإخراج العنصر التالي وقم بالمسح الضوئي للخلف وللأمام في تسلسل العناصر المصنفة بالفعل ؛
إذا كان العنصر (المرتبة) أكبر من العنصر الجديد ، فانتقل العنصر إلى الموضع التالي ؛
كرر الخطوة 3 حتى يتم العثور على العنصر المرتبة حيث يكون العنصر الجديد أقل من أو متساوٍ ؛
بعد إدخال عنصر جديد في هذا الموقف ؛
كرر الخطوات 2 إلى 5.
تنفيذ رمز JavaScript:
دالة insertionsort (Array) {if (object.prototype.toString.call (Array) .slice (8 ، -1) === 'Array') {for (var i = 1 ؛ i <array.length ؛ i ++) {var key = array [i] ؛ var j = i - 1 ؛ بينما (j> = 0 && array [j]> مفتاح) {array [j + 1] = Array [j] ؛ ي-؛ } صفيف [j + 1] = المفتاح ؛ } صفيف الإرجاع ؛ } آخر {return 'Array ليس صفيفًا!' ؛ }}3) تحليل الخوارزمية
أفضل حالة: يتم فرز صفائف الإدخال بترتيب تصاعدي. t (n) = o (n)
أسوأ حالة: يتم فرز صفيف الإدخال بترتيب تنازلي. t (n) = o (n2)
المتوسط: t (n) = o (n2)
اثنان ، نوع الإدراج الثنائي
1) مقدمة في الخوارزمية
فرز الفرز الثنائي-إيناس هو خوارزمية فرز تقوم بإجراء تغييرات طفيفة على خوارزمية فرز الإدراج المباشر. الفرق الأكبر بينها وبين خوارزمية فرز الإدراج المباشر هو أنه عند البحث عن مواقع الإدراج ، يتم استخدام طريقة البحث الثنائي ، والتي لديها تحسن معين في السرعة.
2) وصف الخوارزمية والتنفيذ
بشكل عام ، يتم تنفيذ فرز الإدراج على صفيف باستخدام مكانه. يوصف الخوارزمية المحددة على النحو التالي:
بدءا من العنصر الأول ، يمكن اعتبار العنصر قد تم فرزه ؛
أخرج العنصر التالي وابحث عن موضع الرقم الأول أكبر منه في تسلسل العناصر المصنفة بالفعل ؛
بعد إدخال عنصر جديد في هذا الموقف ؛
كرر الخطوتين أعلاه.
تنفيذ رمز JavaScript:
الوظيفة binaryinSertionSort (Array) {if (object.prototype.toString.call (Array) .Slice (8 ، -1) === 'Array') {for (var i = 1 ؛ i <array.length ؛ i ++) {var key = array ، left = 0 ، reight = i - 1 ؛ بينما (يسار <= يمين) {var middle = parseint ((يسار + يمين) / 2) ؛ if (key <array [middle]) {right = middle - 1 ؛ } آخر {left = middle + 1 ؛ }} لـ (var j = i-1 ؛ j> = left ؛ j--) {array [j + 1] = array [j] ؛ } صفيف [يسار] = المفتاح ؛ } صفيف الإرجاع ؛ } آخر {return 'Array ليس صفيفًا!' ؛ }}3) تحليل الخوارزمية
أفضل حالة: t (n) = o (nlogn)
أسوأ حالة: t (n) = o (n2)
المتوسط: t (n) = o (n2)
3. حدد الفرز
1) مقدمة في الخوارزمية
Selection-Sort هو خوارزمية فرز بسيطة وبديهية. كيفية عمله: أولاً ، ابحث عن أصغر عنصر (كبير) في التسلسل غير الموضح ، وقم بتخزينه في موضع البداية للتسلسل المرتبة ، ثم استمر في البحث عن أصغر عنصر (كبير) من العناصر المتبقية غير المصنفة ، ثم ضعه في نهاية التسلسل المرتبة. وهكذا حتى يتم فرز جميع العناصر.
2) وصف الخوارزمية والتنفيذ
يمكن الحصول على الاختيار المباشر لسجلات 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) منطقة جديدة مرتبة مع زيادة واحدة في عدد السجلات والمساحة الجديدة غير المرتبة مع انخفاض واحد في السجلات ؛
تنتهي رحلة N-1 ويتم طلب الصفيف.
تنفيذ رمز JavaScript:
SelectionSort (Array) {if (object.prototype.toString.call (Array) .slice (8 ، -1) === 'Array') {var len = array.length ، temp ؛ لـ (var i = 0 ؛ i <len - 1 ؛ i ++) {var min = array [i] ؛ لـ (var j = i+1 ؛ j <len ؛ j ++) {if (array [j] <min) {temp = min ؛ min = array [j] ؛ صفيف [j] = temp ؛ }} صفيف [i] = min ؛ } صفيف الإرجاع ؛ } آخر {return 'Array ليس صفيفًا!' ؛ }}3) تحليل الخوارزمية
أفضل حالة: t (n) = o (n2)
أسوأ حالة: t (n) = o (n2)
المتوسط: t (n) = o (n2)
4. فرز الفقاعات
1) مقدمة في الخوارزمية
فرز الفقاعات هو خوارزمية فرز بسيطة. يزور مرارًا وتكرارًا التسلسل المراد فرزه ، ويقارن عنصرين في وقت واحد ، ويقايذهما إذا كانت غير صحيحة. يتم تكرار عمل زيارة التسلسل حتى لا يلزم أي تبادل ، أي أنه تم فرز التسلسل. أصل هذه الخوارزمية هو أنه كلما كان العنصر الأصغر "يطفو" ببطء إلى أعلى التسلسل عبر التبادل.
2) وصف الخوارزمية والتنفيذ
يوصف الخوارزمية المحددة على النحو التالي:
قارن العناصر المجاورة. إذا كان الأول أكبر من الثانية ، فتبادل اثنين منهم ؛
قم بنفس العمل لكل زوج من العناصر المجاورة ، من بداية الزوج الأول إلى نهاية الزوج الأخير ، بحيث يكون العنصر الأخير هو الرقم الأكبر ؛
كرر الخطوات المذكورة أعلاه لجميع العناصر باستثناء آخر واحد ؛
كرر الخطوات من 1 إلى 3 حتى يكتمل الفرز.
تنفيذ رمز JavaScript:
وظيفة publesort (صفيف) {if (object.prototype.toString.call (صفيف) .slice (8 ، -1) === 'array') {var len = array.length ، temp ؛ لـ (var i = 0 ؛ i <len - 1 ؛ i ++) {for (var j = len - 1 ؛ j> = i ؛ j--) {if (array [j] <array [j - 1]) {temp = j] ؛ صفيف [j] = صفيف [j - 1] ؛ صفيف [j - 1] = temp ؛ }}} مجموعة الإرجاع ؛ } آخر {return 'Array ليس صفيفًا!' ؛ }}3) تحليل الخوارزمية
أفضل حالة: t (n) = o (n)
أسوأ حالة: t (n) = o (n2)
المتوسط: t (n) = o (n2)
5. نوع سريع
1) مقدمة في الخوارزمية
الفكرة الأساسية للفرز السريع: قسّم السجلات المراد فرزها إلى جزأين مستقلين من خلال ترتيب واحد ، والكلمات الرئيسية لبعض السجلات أصغر من تلك الموجودة في الجزء الآخر. ثم يمكن الاستمرار في فرز السجلين بشكل منفصل لتحقيق ترتيب التسلسل بأكمله.
2) وصف الخوارزمية والتنفيذ
يستخدم الفرز السريع طريقة التقسيم لتقسيم السلسلة إلى قائمتين فرعيتين. يوصف الخوارزمية المحددة على النحو التالي:
يسمى اختيار عنصر من التسلسل "مبدأ" (PIVOT) ؛
أعد ترتيب التسلسل ، يتم وضع جميع العناصر ذات القيمة المرجعية أمام المرجع ، ويتم وضع جميع العناصر ذات القيمة المرجعية أكبر من المرجع (يمكن وضع نفس الرقم على كلا الجانبين). بعد خروج هذا القسم ، تكون المرجع في منتصف التسلسل. وهذا ما يسمى عملية التقسيم.
فرز التسلسل الفرعي بشكل متكرر أصغر من العنصر المرجعي والتسلسلات الفرعية أكبر من العنصر المرجعي.
تنفيذ رمز JavaScript:
// الطريقة واحدة وظيفة QuickSort (صفيف ، يسار ، يمين) {if (object.prototype.toString.call (صفيف) .slice (8 ، -1) ==== 'Array' && typeof left === 'number' && typeof right === 'number') {if (left <right) {var x = array] لـ (var j = left ؛ j <= right ؛ j ++) {if (array [j] <= x) {i ++ ؛ temp = صفيف [i] ؛ صفيف [i] = صفيف [j] ؛ صفيف [j] = temp ؛ }} QuickSort (صفيف ، يسار ، i - 1) ؛ QuickSort (صفيف ، i + 1 ، يمين) ؛ } ؛ } آخر {return 'صفيف ليس صفيفًا أو يسارًا أو يمينًا ليس رقمًا! "؛ }} var aaa = [3 ، 5 ، 2 ، 9 ، 1] ؛ Quicksort (aaa ، 0 ، aaa.length - 1) ؛ console.log (AAA) ؛ // method 2 var QuickSort = function (arr) {if (arr.length <= 1) {return arr ؛ } var pivotindex = math.floor (arr.length / 2) ؛ var pivot = arr.splice (pivotindex ، 1) [0] ؛ var left = [] ؛ var right = [] ؛ لـ (var i = 0 ؛ i <arr.length ؛ i ++) {if (arr [i] <pivot) {left.push (arr [i]) ؛ } آخر {right.push (arr [i]) ؛ }} إرجاع Quicksort (يسار) .concat ([pivot] ، Quicksort (يمين)) ؛ } ؛3) تحليل الخوارزمية
أفضل حالة: t (n) = o (nlogn)
أسوأ حالة: t (n) = o (n2)
المتوسط: t (n) = o (nlogn)
6. فرز كومة
1) مقدمة في الخوارزمية
يشير فرز الكومة إلى خوارزمية فرز مصممة باستخدام بنية بيانات الكومة. التراص عبارة عن بنية عبارة عن شجرة ثنائية تمامًا تقريبًا وتفي بخصائص التراص: أي أن القيمة الرئيسية أو فهرس العقدة الفرعية أصغر دائمًا من (أو أكبر من) العقدة الأم.
2) وصف الخوارزمية والتنفيذ
يوصف الخوارزمية المحددة على النحو التالي:
يتم إنشاء التسلسل الأولي للكلمات الرئيسية المراد فرزها (R1 ، R2 ... RN) في كومة أعلى كبيرة ، وهي المنطقة الأولية غير المرتبة ؛
تبادل العنصر العلوي للكومة R [1] مع العنصر الأخير R [n] ، وفي هذا الوقت ، يتم الحصول على منطقة جديدة غير مرتبة (R1 ، R2 ، ... RN-1) ومنطقة جديدة مرتبة (RN) ، و R [1،2 ... N-1] <= r [n] ؛
نظرًا لأن الكومة الجديدة من أعلى R [1] بعد التبادل قد تنتهك خصائص الكومة ، فمن الضروري ضبط المنطقة الحالية غير المرتبة (R1 ، R2 ، ... RN-1) إلى الكومة الجديدة ، ثم تبادل R [1] مع العنصر الأخير من المنطقة غير المرتبة مرة أخرى). كرر هذه العملية حتى يكون عدد العناصر في المنطقة المطلوبة N-1 ، ويتم الانتهاء من عملية الفرز بأكملها.
تنفيذ رمز JavaScript:
/*الطريقة الوصف: مجموعة صفيف sorte @parram ليتم فرزها*/وظيفة Heapsort (Array) {if (object.prototype.toString.call (Array) .slice (8 ، -1) === 'Array') {// build heap var heapsize = array.length ، temp ؛ لـ (var i = math.floor (Heapsize / 2) ؛ i> = 0 ؛ i--) {Heapify (Array ، i ، heapsize) ؛ } // fort for (var j = heapsize-1 ؛ j> = 1 ؛ j--) {temp = array [0] ؛ صفيف [0] = صفيف [j] ؛ صفيف [j] = temp ؛ كومة (صفيف ، 0 ، -heapsize) ؛ }} else {return 'array ليس صفيفًا!' ؛ }}/ * الطريقة الوصف: الحفاظ على خصائص Heap @param arr Array @param x array corpriving @param len size */function heepify (arr ، x ، len) {if (object.prototype.toString.call (arr) .slice (8 ، -1) === 'array' 1 ، أكبر = x ، درجة الحرارة ؛ if (l <len && arr [l]> arr [الأكبر]) {الأكبر = l ؛ } if (r <len && arr [r]> arr [الكبرى]) {الكبير = r ؛ } if (الأكبر! = x) {temp = arr [x] ؛ arr [x] = arr [الأكبر] ؛ arr [الأكبر] = درجة الحرارة ؛ كومة (arr ، كبيرة ، لين) ؛ }} آخر {return 'arr ليس صفيفًا أو x ليس رقمًا!' ؛ }}3) تحليل الخوارزمية
أفضل حالة: t (n) = o (nlogn)
أسوأ حالة: t (n) = o (nlogn)
المتوسط: t (n) = o (nlogn)
7. الطلب
1) مقدمة في الخوارزمية
دمج الفرز هو خوارزمية فرز فعالة تستند إلى عملية دمج. هذه الخوارزمية هي تطبيق نموذجي للغاية للانقسام والقهر. دمج الفرز هو طريقة فرز مستقرة. دمج المتسلسلات المطلوبة للحصول على تسلسل تم ترتيبها بالكامل ؛ وهذا هو ، اجعل كل من الدرجة الأولى من الدرجة الأولى ، ثم قم بتوفير طلب شرائح اللاحقة. إذا تم دمج جدولين تم طلبهما في جدول واحد مرتبة ، يسمى دمج ثنائي الاتجاه.
2) وصف الخوارزمية والتنفيذ
يوصف الخوارزمية المحددة على النحو التالي:
قسّم تسلسل الإدخال للطول N إلى اثنين من الطول N/2 ؛
يتم فرز هذين اللارتين معًا بشكل منفصل ؛
دمج اثنين من المتسلسلات المرتبة في تسلسل مصنف نهائي.
تنفيذ رمز JavaScript:
دالة mergesort (Array ، p ، r) {if (p <r) {var q = math.floor ((p + r) / 2) ؛ Mergesort (Array ، P ، Q) ؛ Mergesort (Array ، Q + 1 ، r) ؛ دمج (Array ، P ، Q ، R) ؛ }} دمج الدالة (صفيف ، p ، q ، r) {var n1 = q - p + 1 ، n2 = r - q ، left = [] ، right = [] ، m = n = 0 ؛ لـ (var i = 0 ؛ i <n1 ؛ i ++) {left [i] = array [p+i] ؛ } لـ (var j = 0 ؛ j <n2 ؛ j ++) {right [j] = array [q + 1 + j] ؛ } اليسار [n1] = يمين [n2] = number.max_value ؛ لـ (var k = p ؛ k <= r ؛ k ++) {if (left [m] <= right [n]) {array [k] = left [m] ؛ M ++ ؛ } آخر {array [k] = right [n] ؛ n ++ ؛ }}}3) تحليل الخوارزمية
أفضل حالة: t (n) = o (n)
أسوأ حالة: t (n) = o (nlogn)
المتوسط: t (n) = o (nlogn)
8. فرز دلو
1) مقدمة في الخوارزمية
مبدأ فرز الجرافة: على افتراض أن بيانات الإدخال موزعة بشكل موحد ، يتم تقسيم البيانات إلى عدد محدود من الدلو ، ويتم فرز كل دلو بشكل منفصل (من الممكن استخدام خوارزميات الفرز الأخرى أو الاستمرار في استخدام فرز الجرافة بطريقة متكررة).
2) وصف الخوارزمية والتنفيذ
يوصف الخوارزمية المحددة على النحو التالي:
تعيين صفيف كمي كدلو فارغ.
تكرار من خلال بيانات الإدخال ووضع البيانات في الجرافة المقابلة واحدة تلو الأخرى ؛
فرز كل دلو غير فارغ ؛
قم بربط البيانات المصنفة من دلو فارغ.
تنفيذ رمز JavaScript:
/*الطريقة الوصف: دلو الفرز @Param Array Array @Param Number Number of Buckets*/ Function BucketSort (Array ، num) {if (Array.Length <= 1) {return array ؛ } var len = array.length ، buckets = [] ، result = [] ، min = max = array [0] ، regex = '/^[1-9]+[0-9]*$/' ، space ، n = 0 ؛ num = num || ((num> 1 && regex.test (num))؟ num: 10) ؛ لـ (var i = 1 ؛ i <len ؛ i ++) {min = min <= array [i]؟ مين: صفيف [i] ؛ max = max> = صفيف [i]؟ ماكس: صفيف [i] ؛ } Space = (Max - Min + 1) / num ؛ لـ (var j = 0 ؛ j <len ؛ j ++) {var index = math.floor ((Array [j] - min) / space) ؛ if (دلاء [index]) {// دلو غير فارغ ، أدخل الفرز var k = الجرافات [index] .length - 1 ؛ بينما (k> = 0 && دلو [index] [k]> array [j]) {buckets [index] [k + 1] = buckets [index] [k] ؛ ك- ؛ } الدلاء [الفهرس] [k + 1] = صفيف [j] ؛ } آخر {// دلو فارغ ، تهيئة الدلاء [الفهرس] = [] ؛ دلاء [فهرس] .push (صفيف [J]) ؛ }} بينما (n <num) {result = result.concat (دلاء [n]) ؛ n ++ ؛ } نتيجة الإرجاع ؛ }3) تحليل الخوارزمية
في أفضل حالة لفرز الجرافة ، الوقت الخطي O (n) ، يعتمد التعقيد الزمني لفرز الجرافة على التعقيد الزمني لفرز البيانات بين الدلاء ، لأن التعقيد الزمني للأجزاء الأخرى هو o (n). من الواضح أنه كلما تم تقسيم الدلو الأصغر ، كلما قلت البيانات التي يقلها الدلو ، كلما قلت الوقت لفرزه. لكن استهلاك المساحة المقابل سيزيد.
9. عد الفرز
1) مقدمة في الخوارزمية
فرز العد هو خوارزمية فرز مستقرة. يستخدم Count Forting صفيفًا إضافيًا C ، حيث يكون العنصر I-Th هو عدد العناصر ذات قيمة مساوية لـ I في الصفيف A ليتم فرزها. ثم ، وفقًا لـ Array C ، يتم ترتيب العناصر الموجودة في A إلى الموضع الصحيح. يمكنه فقط فرز الأعداد الصحيحة.
2) وصف الخوارزمية والتنفيذ
يوصف الخوارزمية المحددة على النحو التالي:
العثور على أكبر وأصغر العناصر في الصفيف ليتم فرزها ؛
عد عدد المرات التي يظهر فيها كل عنصر بقيمة I في الصفيف وقم بتخزينه في العنصر I-Th of Array C ؛
تراكم جميع التهم (بدءًا من العنصر الأول في C ، تتم إضافة كل عنصر والبند السابق) ؛
عكس الصفيف المستهدف: ضع كل عنصر I في العنصر C (I) من الصفيف الجديد ، وطرح C (i) على 1 لكل عنصر.
تنفيذ رمز JavaScript:
الوظيفة countingSort (Array) {var len = array.length ، b = [] ، c = [] ، min = max = array [0] ؛ لـ (var i = 0 ؛ i <len ؛ i ++) {min = min <= array [i]؟ مين: صفيف [i] ؛ max = max> = صفيف [i]؟ ماكس: صفيف [i] ؛ C [Array [i]] = c [صفيف [i]]؟ C [Array [i]] + 1: 1 ؛ } لـ (var j = min ؛ j <max ؛ j ++) {c [j + 1] = (c [j + 1] || 0) + (c [j] || 0) ؛ } لـ (var k = len - 1 ؛ k> = 0 ؛ k--) {b [c [array [k]] - 1] = Array [k] ؛ C [Array [K]]-؛ } العودة ب ؛ }3) تحليل الخوارزمية
عندما يكون عنصر الإدخال أكثر من 0 و K ، يكون وقت التشغيل O (N + K). فرز العد ليس فرز المقارنة ، وسرعة الفرز أسرع من أي خوارزمية فرز المقارنة. نظرًا لأن طول الصفيف C المستخدم للعد يعتمد على نطاق البيانات في الصفيف المراد فرزه (يساوي الفرق بين الحد الأقصى والحد الأدنى لقيم الصفيف المراد فرزه بالإضافة إلى 1) ، فإن هذا يجعل فرز العدد يتطلب الكثير من الوقت والذاكرة للمصفوفات ذات نطاق بيانات كبير.