لقد تعرضت لأساسيات الخوارزمية المختلفة منذ أن تعلمت بنية البيانات ، لكنني لم أمارسها أبدًا منذ أن انتهيت من الامتحان. عندما كنت أتطور ، راجعت أيضًا عندما استخدمته. الآن أنا أتعلم جافا سكريبت. سوف آخذ هذا الوقت لتنظيم مختلف الخوارزميات الأساسية وكتابة التعليمات البرمجية في بناء الجملة JS و PHP على التوالي.
1. فرز الفقاعة
المبدأ: قارن الأرقام المجاورة في الأزواج وتبادلها بالترتيب من صغير إلى كبير أو كبير إلى صغير. بعد رحلة ، يتم تبادل أكبر أو أصغر رقم إلى آخر رقم ، ثم قارنها وتبادلها من البداية حتى ينتهي الرقم الثاني إلى الأخير.
تعقيد الوقت: متوسط الحالة: o (n2) أفضل حالة: o (n) أسوأ حالة: o (n2)
تعقيد الفضاء: O (1)
الاستقرار: مستقر
// javaScript Syntax var Array = [23،0،32،45،56،75،43،0،34] ؛ لـ (var i = 0 ؛ i <array.length ؛ i ++) {var issort = true ؛ لـ (var j = 0 ؛ j <array.length - 1 - i ؛ j ++) {if (array [j]> array [j+1]) {issort = false ؛ var temp = array [j] ؛ صفيف [j] = صفيف [j + 1] ؛ صفيف [j + 1] = temp ؛ }} if (issort) {break ؛ }} console.log (صفيف) ؛ <؟ php $ array = [23،0،32،45،56،75،43،0،34] ؛ لـ ($ i = 0 ؛ $ i <count ($ array) ؛ $ i ++) {$ issort = true ؛ لـ ($ j = 0 ؛ $ j <count ($ array) - 1 ؛ $ j ++) {if ($ array [$ j]> $ array [$ j+1]) {$ issort = false ؛ $ temp = $ array [$ j] ؛ $ array [$ j] = $ array [$ j + 1] ؛ $ array [$ j + 1] = $ temp ؛ }} if ($ issort) {break ؛ }} var_dump ($ array) ؛؟>2. فرز الاختيار البسيط
المبدأ: من خلال مقارنة الكلمات الرئيسية NI ، حدد السجل مع أصغر الكلمة الرئيسية من سجلات N-I+1 ، وتبادلها مع سجلات I (1 = i <= n). أداء فرز الاختيار البسيط أفضل قليلاً من فرز الفقاعات.
تعقيد الوقت: متوسط الحالة: o (n2) أفضل حالة: o (n) أسوأ حالة: o (n2)
تعقيد الفضاء: O (1)
الاستقرار: غير مستقر
// javaScript var Array = [23،0،32،45،56،75،43،0،34] ؛ لـ (var i = 0 ؛ i <array.length - 1 ؛ i ++) {var pos = i ؛ لـ (var j = i+1 ؛ j <array.length ؛ j ++) {if (array [j] <array [pos]) {pos = j ؛ }} var temp = array [i] ؛ صفيف [i] = صفيف [pos] ؛ صفيف [pos] = درجة الحرارة ؛ } console.log (Array) ؛ <؟ php $ array = [23،0،32،45،56،75،43،0،34] ؛ لـ ($ i = 0 ؛ $ i <count ($ array) ؛ $ i ++) {$ pos = $ i ؛ لـ ($ j = $ i+1 ؛ $ j <count ($ array) ؛ $ j ++) {if ($ array [$ j] <$ array [$ pos]) {$ pos = $ j ؛ }} $ temp = $ array [$ i] ؛ $ array [$ i] = $ array [$ pos] ؛ $ array [$ pos] = $ temp ؛ } var_dump ($ array) ؛؟>3. إدراج مباشرة
المبدأ: أدخل سجلًا في الجدول المرتبة المرتبة ، وبالتالي الحصول على جدول جديد مرتبة مع زيادات واحدة من السجلات. وهذا يعني ، أولاً ، تعامل مع السجل الأول للتسلسل باعتباره بعد مرتبة ، ثم أدخله واحدًا تلو الآخر من السجل الثاني حتى يتم طلب التسلسل بأكمله. أداء أفضل من طريقة الفقاعة وفرز الاختيار
تعقيد الوقت: متوسط الحالة: o (n2) أفضل حالة: o (n) أسوأ حالة: o (n2)
تعقيد الفضاء: O (1)
الاستقرار: مستقر
// javaScript var Array = [23،0،32،45،56،75،43،0،34] ؛ لـ (var j = 0 ؛ j <array.length ؛ j ++) {var key = array [j] ؛ var i = j - 1 ؛ بينما (i> -1 && array [i]> مفتاح) {Array [i + 1] = Array [i] ؛ أنا = أنا - 1 ؛ } صفيف [i + 1] = المفتاح ؛ } console.log (Array) ؛ <؟ php // insert sort $ arry = [23،0،32،45،56،75،43،0،34] ؛ لـ ($ i = 0 ؛ $ i <count ($ array) ؛ $ i ++) {$ key = $ array [$ i] ؛ $ j = $ i - 1 ؛ بينما ($ j> -1 && $ array [$ j]> $ key) {$ array [$ j +1] = $ array [$ j] ؛ $ j = $ j - 1 ؛ } $ array [$ j + 1] = $ key ؛ } var_dump ($ array) ؛؟>4. نوع سريع
المبدأ: من خلال الفرز ، يتم تقسيم البيانات المراد فرزها إلى جزأين مستقلين ، وجميع البيانات جزئيًا أصغر من جميع البيانات في الجزء الآخر ، ثم يتم فرز الجزءين من البيانات بسرعة وفقًا لهذه الطريقة. يمكن إجراء عملية الفرز بأكملها بشكل متكرر لتحقيق البيانات بأكملها التي تصبح تسلسلًا مرتبة.
تعقيد الوقت: متوسط الحالة: o (nlog2n) أفضل حالة: o (nlog2n) أسوأ حالة: o (n2)
تعقيد الفضاء: O (NLOG2N)
الاستقرار: غير مستقر
// JavaScript Quick Sort var Array = [23،0،32،45،56،75،43،0،34] ؛ var QuickSort = function (arr) {if (arr.length <= 1) {return arr ؛ } // تحقق من عدد العناصر الموجودة في الصفيف ، إذا كان أقل من أو يساوي 1 ، فسيتم إرجاعه. var pivotindex = math.floor (arr.length/2) ؛ // var pivot = arr.splice (PivotIndex ، 1) [0] ؛ لـ (var i = 0 ؛ i <arr.length ؛ i ++) // transweep الصفيف ، وضع عناصر أصغر من "المعيار" في المجموعة الفرعية على اليسار ، والعناصر أكبر من المعيار في المجموعة الفرعية على اليمين. {if (arr [i] <pivot) {left.push (arr [i]) ؛ } آخر {right.push (arr [i]) ؛ }} إرجاع Quicksort (يسار) .concat ([pivot] ، Quicksort (يمين)) ؛ // كرر هذه العملية باستمرار للحصول على الصفيف المرتبة. } ؛ var newarray = QuickSort (Array) ؛ console.log (Newarray) ؛ <؟ php $ array = [23،0،32،45،56،75،43،0،34] ؛ دالة Quick_sort ($ arr) {// أولاً حدد ما إذا كنت بحاجة إلى متابعة $ length = count ($ arr) ؛ if ($ length <= 1) {return $ arr ؛ } $ base_num = $ arr [0] ؛ // حدد مسطرة لتحديد العنصر الأول // تهيئة صفيفتين $ left_array = array () ؛ // $ right_array أقل من المسطرة = array () ؛ $ arr [$ i]) {// وضع في الصفيف الأيسر $ left_array [] = $ arr [$ i] ؛ } آخر {// وضع في اليمين $ right_array [] = $ arr [$ i] ؛ }} // ثم طريقة الفرز نفسها للصفائف اليسرى والأيمن على التوالي // استدعاء هذه الوظيفة بشكل متكرر وتسجيل النتيجة $ left_array = quick_sort ($ left_array) ؛ $ right_array = Quick_sort ($ right_array) ؛ // دمج المسطرة اليسرى إلى retray array_merge ($ left_array ، array ($ base_num) ، $ right_array) ؛ } $ newarray = Quick_sort ($ array) ؛ var_dump ($ newarray) ؛؟>5. تل نوع
المبدأ: أولاً ، قسّم تسلسل السجل بأكمله ليتم فرزه إلى عدة آثار فرعية للإدراج المباشر والفرز. عندما يتم طلب السجلات في التسلسل بأكمله "بشكل أساسي" ، ثم أدخل وفرز السجلات بأكملها بالتسلسل. .
تعقيد الوقت: المتوسط: o (nl) أفضل حالة: o (nlog2n) أسوأ حالة: o (n2)
تعقيد الفضاء: O (1)
الاستقرار: غير مستقر
// JavaScript Hill Sort Var Array = [23،0،32،45،56،75،43،0،34] ؛ var shellsort = function (arr) {var length = arr.length ؛ var H = 1 ؛ بينما (h <length/3) {h = 3*h+1 ؛ // set stereal} بينما (h> = 1) {for (var i = h ؛ i <length ؛ i ++) {for (var j = i ؛ j> = h && arr [j] <arr [jh] ؛ j- = h) {var temp = arr [jh] ؛ arr [jh] = arr [j] ؛ arr [j] = temp ؛ }} h = (h-1)/3 ؛ } إرجاع arr ؛ } var newarray = shellsort (Array) ؛ console.log (Newarray) ؛ <؟ php // hill sort $ array = [23،0،32،45،56،75،43،0،34] ؛ وظيفة shellsort ($ arr) {$ length = count ($ arr) ؛ $ H = 1 ؛ بينما ($ h <$ length/3) {$ h = 3*$ h+1 ؛ // set steral} بينما ($ h> = 1) {for ($ i = $ h ؛ $ i <$ length ؛ $ i ++) {for ($ j = $ i ؛ $ j> = $ h && $ arr [$ arr [$ j- $ h] ؛ $ arr [$ j- $ h] = $ arr [$ j] ؛ $ arr [$ j] = $ temp ؛ }} $ h = ($ h-1)/3 ؛ } إرجاع $ arr ؛ } $ newarray = shellsort ($ array) ؛ var_dump ($ newarray)؟>6. الطلب
المبدأ: على افتراض أن التسلسل الأولي يحتوي على سجلات N ، يمكن اعتباره متسلسلًا مرتبة ، كل بعد طوله 1 ، ثم يتم دمجه في أزواج للحصول على (أصغر عدد صحيح لا تقل عن N/2) تم طلبه بعد الطول.
تعقيد الوقت: المتوسط: O (NLOG2N) أفضل حالة: O (NLOG2N) أسوأ حالة: O (NLOG2N)
تعقيد الفضاء: O (1)
الاستقرار: مستقر
// javaScript دمج وظيفة الفرز isArray1 (arr) {if (object.prototype.toString.call (arr) == '[كائن صفيف]') {return true ؛ } آخر {return false ؛ }} دالة دمج (يسار ، يمين) {var result = [] ؛ if (! isarray1 (يسار)) {left = [left] ؛ } if (! isArray1 (يمين)) {right = [right] ؛ } بينما (left.length> 0 && right.length> 0) {if (left [0] <right [0]) {result.push (left.shift ()) ؛ } آخر {result.push (right.shift ()) ؛ }} return result.concat (يسار) .concat (يمين) ؛ } دالة mergesort (arr) {var len = arr.length ؛ var lim ، work = [] ؛ var i ، j ، k ؛ if (len == 1) {return arr ؛ } لـ (i = 0 ؛ i <len ؛ i ++) {work.push (arr [i]) ؛ } work.push ([]) ؛ لـ (lim = len ؛ lim> 1 ؛) {// lim هو طول التجميع لـ (j = 0 ، k = 0 ؛ k <lim ؛ j ++ ، k = k+2) {work [j] = merge (work [k] ، work [k+1]) ؛ } العمل [j] = [] ؛ lim = math.floor ((lim+1)/2) ؛ } عودة العمل [0] ؛ } var array = [23،0،32،45،56،75،43،0،34] ؛ console.log (mergesort (Array)) ؛ <؟ php // فهم وظيفة الفرز دمج (& $ arr) {$ len = count ($ arr) ؛ // العثور على طول الصفيف msort ($ arr ، 0 ، $ len-1) ؛ } // البرنامج الذي ينفذ فعليًا دمج وظيفة الفرز MSORT (& $ arr ، $ يسار ، $ يمينًا) {if ($ left <$ right) {// تشير إلى أن هناك عنصرًا إضافيًا واحد في اللاحق ، ثم يكون من الضروري الانقسام والفرز بشكل منفصل ، ودمج // حساب الموضع المقسم ، الطول /2 ، اذهب إلى مركز $ الكامل = ($ $+$ right) /2) ؛ // المكالمات العودية تقوم بفرز الجانب الأيسر مرة أخرى: msort ($ arr ، $ left ، $ center) ؛ // استدعاء بشكل متكرر لفرز الجانب الأيمن مرة أخرى msort ($ arr ، $ center+1 ، $ right) ؛ // دمج نتائج الفرز mergearray ($ arr ، $ left ، $ center ، $ right) ؛ }} // الجمع بين رقمين تم طلبهما في وظيفة صفيف مطلوبة mergearray (& $ arr ، $ يسار ، مركز $ ، $ right) {// تعيين اثنين من علامتي موضع البداية $ a_i = $ left ؛ $ b_i = $ center+1 ؛ بينما ($ a_i <= $ center && $ b_i <= $ right) {// عندما لا يقوم صفيف أو صفيف B بعبر الحدود إذا ($ arr [$ a_i] <$ arr [$ b_i]) {$ temp [] = $ arr [$ a_i ++] ؛ } آخر {$ temp [] = $ arr [$ b_i ++] ؛ }} // تحكم على ما إذا كانت جميع العناصر الموجودة في المصفوفة A تستخدم. إذا لم يكن الأمر كذلك ، أدخل جميع العناصر الموجودة في Array C: بينما ($ a_i <= $ center) {$ temp [] = $ arr [$ a_i ++] ؛ } // الحكم على ما إذا كانت جميع العناصر الموجودة في المصفوفة B تستخدم. إذا لم يكن الأمر كذلك ، أدخل جميع العناصر الموجودة في Array C: بينما ($ b_i <= $ right) {$ temp [] = $ arr [$ b_i ++] ؛ } // اكتب الجزء المرتبة في $ arrc إلى $ arr: لـ ($ i = 0 ، $ len = count ($ temp) ؛ $ i <$ len ؛ $ i ++) {$ arr [$ left+$ i] = $ temp [$ i] ؛ }} $ arr = صفيف (23،0،32،45،56،75،43،0،34) ؛ Mergesort ($ arr) ؛ var_dump ($ arr) ؛؟>7. فرز كومة
المبدأ: فرز الكومة هو وسيلة للفرز باستخدام الكومة. الفكرة الأساسية هي: بناء التسلسل المراد فرزه في كومة كبيرة كبيرة. في هذا الوقت ، فإن الحد الأقصى لقيمة التسلسل بأكمله هو عقدة الجذر لأعلى الكومة. قم بإزالته (في الواقع ، هو تبادله بالعنصر النهائي لمصفوفة الكومة ، والعنصر النهائي هو الحد الأقصى للقيمة) ، ثم إعادة بناء تسلسل N-1 المتبقي في كومة ، بحيث يتم الحصول على قيمة submaximum لعناصر n. سيؤدي ذلك إلى تنفيذ متكرر ويمكن الحصول على تسلسل مرتبة.
تعقيد الوقت: المتوسط: O (NLOG2N) أفضل حالة: O (NLOG2N) أسوأ حالة: O (NLOG2N)
تعقيد الفضاء: O (1)
الاستقرار: غير مستقر
// JavaScript Heap Sort var Array = [23،0،32،45،56،75،43،0،34] ؛ دالة Heapsort (Array) {for (var i = math.floor (array.length / 2) ؛ // بناء صفيف صفيف في كومة أعلى كبيرة} لـ (i = array.length-1 ؛ i> = 0 ؛ i--) {/*تبديل عقدة الجذر*/var temp = array [i] ؛ صفيف [i] = صفيف [0] ؛ صفيف [0] = درجة الحرارة ؛ /*لا يزال يتم دمج الصفيف المتبقي في كومة قمة كبيرة*/ أكواد (صفيف ، 0 ، i - 1) ؛ } صفيف الإرجاع ؛ } استقلال الوظيفة (صفيف ، ابدأ ، أقصى) {var temp = array [start] ؛ // temp هي قيمة عقدة الجذر لـ (var j = 2 * start ؛ j <max ؛ j * = 2) {if (j <max && array [j] <array [j+1]) {get the children for childs ++ j ؛ } if (temp> = Array [j]) break ؛ صفيف [ابدأ] = صفيف [j] ؛ ابدأ = ي ؛ } صفيف [start] = temp ؛ } var newarray = heapsort (Array) ؛ console.log (Newarray) ؛ <؟ php // heap function function heapsort (& $ arr) {#initheap ($ arr ، 0 ، count ($ arr) - 1) ؛ #start تبديل عقد الرأس والذيل ، وقم بتقليل عقدة نهاية واحدة في وقت واحد وضبط الكومة حتى يتم ترك عنصر لـ ($ end = count ($ arr)-1 ؛ $ end> 0 ؛ $ end--) {$ temp = $ arr [0] ؛ $ arr [0] = $ arr [$ end] ؛ $ arr [$ end] = $ temp ؛ Ajustnodes ($ arr ، 0 ، $ end - 1) ؛ }} #Initialize أقصى كومة ، ابدأ من آخر عقدة غير أوراق ، ويتم ترقيم آخر عقدة غير أوراق على أنها طول المصفوفة/2 وظيفة أسفل دالة Initheap (& $ arr) {$ len = count ($ arr) ؛ لـ ($ start = floor ($ len / 2) - 1 ؛ $ start> = 0 ؛ $ start--) {ajustnodes ($ arr ، $ start ، $ len - 1) ؛ }}#addlenodes#@param $ arr array ليتم تعديلها#@param $ ابدأ إحداثيات العقدة الأصل ليتم تعديلها#@param $ end إحداثيات العقدة النهائية المراد تعديلها ajustnodes (& $ arr ، $ start ، $ end) {$ maxinx = $ start ؛ $ len = $ end + 1 ؛ #طول الجزء المراد تعديله $ leftchildinx = ($ start + 1) * 2 - 1 ؛ #Left Child Coversinate $ rightchildinx = ($ start + 1) * 2 ؛ #Right Child Coversinate #إذا كان الجزء المراد تعديله لديه طفل يسار إذا ($ leftchildinx + 1 <= $ len) {#get تنسيق العقدة الدنيا إذا ($ arr [$ maxinx] <$ arr [$ leftchildinx]) {$ maxinx = $ leftchildinx ؛ } #إذا كان الجزء المراد تعديله لديه عقدة الطفل الصحيحة إذا ($ rightchildinx + 1 <= $ len) {if ($ arr [$ maxinx] <$ arr [$ rightchildinx]) {$ maxinx = $ rightchildinx ؛ }}} #swap node parent and maximum node if ($ start! = $ maxinx) {$ temp = $ arr [$ start] ؛ $ arr [$ start] = $ arr [$ maxinx] ؛ $ arr [$ maxinx] = $ temp ؛ #إذا كانت العقدة الفرعية بعد البورصة لها عقد أطفال ، فاستمر في ضبط إذا (($ maxinx + 1) * 2 <= $ len) {ajustnodes ($ arr ، $ maxinx ، $ end) ؛ }}} $ arr = صفيف (23،0،32،45،56،75،43،0،34) ؛ Heapsort ($ arr) ؛ var_dump ($ arr) ؛؟>8. فرز Cardinality
المبدأ: قطع الأعداد الصحيحة إلى أرقام مختلفة بأرقام ، ثم قارنها بشكل منفصل بواسطة كل رقم. نظرًا لأن الأعداد الصحيحة يمكن أن تعبر عن الأوتار (مثل الأسماء أو التواريخ) وأرقام النقطة العائمة في تنسيقات محددة ، فإن فرز Radix لا يستخدم فقط في الأعداد الصحيحة.
تعقيد الوقت: المتوسط: O (d (r+n)) أفضل حالة: o (d (n+rd)) أسوأ الحالة: o (d (r+n)
تعقيد الفضاء: O (RD+N)
الاستقرار: مستقر
<؟ php #blassorting ، هنا يتم فرز الأعداد الصحيحة الإيجابية فقط. بالنسبة للأرقام السلبية وأرقام النقاط العائمة ، هناك حاجة إلى مكمل. أنت مهتم بدراسة #counting sort #@param $ arr array ليتم فرزه #@param $ digit_num sort وفقًا لعدد أرقام دالة conting_sort (& $ arr ، $ digit_num = false) {if ($ digit_num! == false) { #$ the $ digit_num ليس فارغًا ، فصعيدًا بالرقم count ($ arr) ؛ }} آخر {$ arr_temp = $ arr ؛ } $ max = max ($ arr) ؛ $ time_arr = array () ؛ #STorage Array of Elements Oredences#تهيئة مجموعة الأحداث لـ ($ i = 0 ؛ $ i <= $ max ؛ $ i ++) {$ time_arr [$ i] = 0 ؛ } #statize أحداث كل عنصر لـ ($ i = 0 ؛ $ i <count ($ arr_temp) ؛ $ i ++) {$ time_arr [$ arr_temp) ؛ $ i ++) {$ time_arr [$ arr_temp [$ i]] ++ ؛ } #statify أحداث كل عنصر أصغر أو مساوياً له ($ i = 0 ؛ $ i <count ($ time_arr) - 1 ؛ $ i ++) {$ time_arr [$ i +1] += $ time_arr [$ i] ؛ } #SORT المصفوفة باستخدام عدد الأحداث لـ ($ i = count ($ arr) - 1 ؛ $ i> = 0 ؛ $ i--) {$ sorted_arr [$ time_arr [$ arr_temp [$ i]] - 1] = $ arr [$ i] ؛ $ time_arr [$ arr_temp [$ i]]-؛ } $ arr = $ sorted_arr ؛ Ksort ($ arr) ؛ #ignore فقدان الكفاءة في فرز المفتاح هذه المرة} #calculation عدد أجزاء البتات الخاصة بدالة أرقام معينة get_digit ($ number) {$ i = 1 ؛ بينما (رقم $> = pow (10 ، $ i)) {$ i ++ ؛ } إرجاع $ i ؛ } #get رقم الرقم i -th من الرقم من وظيفة الأرقام الفردية get_specific_digit ($ num ، $ i) {if ($ num <pow (10 ، $ i - 1)) {return 0 ؛ } أرضية الإرجاع ($ num ٪ pow (10 ، $ i) / pow (10 ، $ i - 1)) ؛ } #Black Forting ، عد الفرز كدالة عملية فرعية Radix_sort (& $ arr) {#first ابحث عن أكبر رقم في الصفيف $ max = max ($ arr) ؛ $ max_digit = get_digit ($ max) ؛ لـ ($ i = 1 ؛ $ i <= $ max_digit ؛ $ i ++) {counting_sort ($ arr ، $ i) ؛ }} $ arr = صفيف (23،0،32،45،56،75،43،0،34) ؛ radix_sort ($ arr) ؛ var_dump ($ arr) ؛؟>ما سبق هو كل محتوى هذه المقالة. آمل أن يكون ذلك مفيدًا لتعلم الجميع وآمل أن يدعم الجميع wulin.com أكثر.