Я подвергался воздействию различных оснований алгоритма с тех пор, как я изучал структуру данных, но я никогда не практиковал ее с тех пор, как закончил экзамен. Когда я развивался, я также проверил, когда использовал его. Теперь я изучаю JavaScript. Я возьму это время, чтобы организовать различные основные алгоритмы и записать код в JS и PHP -синтаксисе соответственно.
1. Сортировка пузырьков
Принцип: Сравните смежные числа в парах и обменяйте их по порядку от малого до крупного или большего до маленького. После поездки наибольшее или наименьшее число обменивается до последней цифры, а затем сравните и обменяйте их с самого начала до окончания второй до последней цифры.
Сложность времени: Средний случай: O (N2) Лучший случай: O (n) Худший случай: O (N2)
Сложность пространства: O (1)
Стабильность: стабильная
// javaScript syntax var array = [23,0,32,45,56,75,43,0,34]; for (var i = 0; i <array.length; i ++) {var issort = true; for (var j = 0; j <array.length - 1 - i; j ++) {if (array [j]> array [j+1]) {issort = false; var temp = массив [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) Th Records. Производительность простой сортировки выбора немного лучше, чем сортировка пузырьков.
Сложность времени: Средний случай: O (N2) Лучший случай: O (n) Худший случай: O (N2)
Сложность пространства: O (1)
Стабильность: нестабильная
// javascript var array = [23,0,32,45,56,75,43,0,34]; for (var i = 0; i <array.length - 1; i ++) {var pos = i; for (var j = i+1; j <array.length; j ++) {if (array [j] <array [pos]) {pos = j; }} var temp = array [i]; массив [i] = массив [pos]; массив [pos] = temp; } console.log (массив); <? 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. напрямую вставьте сортировку
Принцип: вставьте запись в отсортированную таблицу, получая тем самым новую упорядоченную таблицу с 1 приращением записей. То есть сначала обратите внимание на первую запись последовательности как упорядоченную последующую последовательность, а затем вставьте ее по одному со второй записи, пока вся последовательность не будет упорядочена. Лучшая производительность, чем метод пузыря и сортировка выбора
Сложность времени: Средний случай: O (N2) Лучший случай: O (n) Худший случай: O (N2)
Сложность пространства: O (1)
Стабильность: стабильная
// javascript var array = [23,0,32,45,56,75,43,0,34]; for (var j = 0; j <array.length; j ++) {var key = array [j]; var i = j - 1; while (i> -1 && array [i]> key) {array [i + 1] = array [i]; i = i - 1; } массив [i + 1] = key; } console.log (массив); <? PHP // непосредственно вставьте сортировку $ array = [23,0,32,45,56,75,43,0,34]; для ($ i = 0; $ i <count ($ array); $ i ++) {$ key = $ array [$ i]; $ j = $ i - 1; while ($ 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]; // Выберите «контрольный показатель» (pivot) и отделить его от исходного массива, var left = []; // определить два пустых массива для хранения двух подмножеств с одной левой и одной правой var = []; Для (var i = 0; i <arr.length; i ++) // трансвип массив, поместите элементы, меньшие, чем «контрольный показатель» в подмножество слева, и элементы больше, чем эталон в подмножество справа. {if (arr [i] <pivot) {left.push (arr [i]); } else {right.push (arr [i]); }} return QuickSort (слева) .concat ([pivot], QuickSort (справа)); // Повторите этот процесс непрерывно, чтобы получить отсортированный массив. }; var newarray = QuickSort (массив); console.log (newarray); <? Php $ Array = [23,0,32,45,56,75,43,0,34]; function Quick_sort ($ arr) {// сначала определить, нужно ли вам продолжить $ length = count ($ arr); if ($ length <= 1) {return $ arr; } $ base_num = $ arr [0]; // Выберите правитель, чтобы выбрать первый элемент // инициализировать два массива $ lead_array = array (); // $ right_array меньше, чем правитель = array (); // для ($ i = 1; $ i <$ длина; $ i ++) {// Передача всех элементов, за исключением Ruler, и вставьте их в ARRAPE в зависимости от размера $. $ arr [$ i]) {// помещать в левый массив $ left_array [] = $ arr [$ i]; } else {// положить в правую $ right_array [] = $ arr [$ i]; }} // Затем тот же метод сортировки для левых и правых массивов соответственно // вызов этой функции рекурсивно и записывать результат $ left_array = Quick_sort ($ lealth_array); $ right_array = Quick_sort ($ right_array); // объединить левую линейку с правой return array_merge ($ LEATE_ARRAY, ARRAY ($ BASE_NUM), $ right_array); } $ newarray = Quick_sort ($ array); var_dump ($ newarray);?>5. Hill Sort
Принцип: Во-первых, разделите всю последовательность записей, которая будет сортирована на несколько подпоследований для прямой вставки и сортировки. Когда записи во всей последовательности «в основном упорядочены», затем вставьте и сортируют все записи в последовательности. Полем
Сложность времени: Средний случай: O (n√n) Лучший случай: 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; while (h <length/3) {h = 3*h+1; // установить интервал} while (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; } return arr; } var newarray = shellSort (массив); 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; // Установить интервал} while ($ h> = 1) {для ($ i = $ h; $ i <$ length; $ i ++) {для ($ j = $ i; $ j> = $ h && $ arr [$ j] <$ ar [$ h]; $ arr [$ j- $ h] = $ arr [$ j]; $ arr [$ j] = $ temp; }} $ h = ($ h-1)/3; } return $ arr; } $ newarray = shellsort ($ array); var_dump ($ newarray)?>6. Заказ
Принцип: предполагая, что начальная последовательность содержит n записи, ее можно рассматривать как n упорядоченных последующих, каждая последующая длина 1, а затем объединена в парах, чтобы получить (наименьшее целое число не менее чем N/2) упорядоченные последующие последствия с длиной 2 или 1, и объединены в парах ... повторяйте этот путь, пока не будет получена упорядоченная последовательность с длиной N.
Сложность времени: Средний случай: O (nlog2n) Лучший случай: O (nlog2n) Худший случай: O (nlog2n)
Сложность пространства: O (1)
Стабильность: стабильная
// javaScript слияние функция сортировки isarray1 (arr) {if (object.prototype.tostring.call (arr) == '[object array]') {return true; } else {return false; }} функция Merge (слева, справа) {var result = []; if (! isarray1 (слева)) {слева = [слева]; } if (! isarray1 (справа)) {right = [right]; } while (left.length> 0 && right.length> 0) {if (left [0] <right [0]) {result.push (left.shift ()); } else {result.push (right.shift ()); }} return result.concat (left) .concat (справа); } функция mergesort (arr) {var len = arr.length; var lim, kory = []; var i, j, k; if (len == 1) {return arr; } for (i = 0; i <len; i ++) {work.push (arr [i]); } Work.push ([]); for (lim = len; lim> 1;) {// lim - это длина группировки для (j = 0, k = 0; k <lim; j ++, k = k+2) {work [j] = merge (work [k], работа [k+1]); } work [j] = []; lim = math.floor ((lim+1)/2); } возвращать работу [0]; } var array = [23,0,32,45,56,75,43,0,34]; console.log (mergesort (массив)); <? php // Понимание функции сортировки Mergesort (& $ arr) {$ len = count ($ arr); // поиск MSORT длины массива ($ arr, 0, $ len-1); } // Программа, которая фактически реализует функцию сортировки слияния MSORT (& $ arr, $ left, $ right) {if ($ left <$ right) {// Укажите, что в последующем есть 1 дополнительный элемент, то необходимо разделить, отсортировать отдельно, слияние // расчета позицию разделения, длина /2 идите во все $ center = floor ($ left+$ right) /2); // снова рекурсивный вызов сортирует левую сторону: MSORT ($ arr, $ left, $ center); // рекурсивно вызов, чтобы снова сортировать правую сторону MSORT ($ arr, $ center+1, $ right); // слияние результатов сортировки Mergearray ($ arr, $ left, $ center, $ right); }} // Объедините два заказанные номера в упорядоченную функцию массива MergeArray (& $ arr, $ left, $ center, $ rugh) {// Установить две оценки исходной позиции $ a_i = $ left; $ b_i = $ center+1; while ($ a_i <= $ center && $ b_i <= $ right) {// Когда ни массив, ни массив B не пересекает границу, если ($ arr [$ a_i] <$ arr [$ b_i]) {$ temp [] = $ arr [$ a_i ++]; } else {$ temp [] = $ arr [$ b_i ++]; }} // Судите, используются ли все элементы в массиве А. Если нет, вставьте все элементы в массив C: while ($ a_i <= $ center) {$ temp [] = $ arr [$ a_i ++]; } // Судите, используются ли все элементы в массиве B. Если нет, вставьте все элементы в массив C: while ($ b_i <= $ правильно) {$ temp [] = $ arr [$ b_i ++]; } // Напишите отсортированную часть в $ arrc в $ arr: for ($ 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 в кучу, чтобы быть получено субмаксимум 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> = 0; i--) {heapadjust (array, i, array.length-1); // массив массивов построить в большую верхнюю кучу} для (i = array.length-1; i> = 0; i--) {/*Обмен корневой узел*/var temp = array [i]; массив [i] = массив [0]; массив [0] = темп; /*Оставшийся массив продолжает встроен в большую верхнюю кучу*/ heapadjust (массив, 0, I - 1); } return Array; } function heapAdjust (массив, старт, max) {var temp = array [start]; // температура - это значение корневого узла для (var j = 2 * start; j <max; j * = 2) {if (j <max && array [j] <array [j+1]) {// Получить экзамен старших детей ++ j; } if (temp> = array [j]) break; Array [Start] = Array [j]; start = j; } array [start] = temp; } var newarray = heapsort (массив); console.log (newarray); <? PHP // HEAP SORD FUNCTION HEAPSORT (& $ ARR) {#InitheAp ($ arr, 0, count ($ arr) - 1); #Старете обмениваться головными и хвостовыми узлами и уменьшите один конечный узел за раз и отрегулируйте кучу, пока не останется элемент для ($ 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); }}#Routationnodes#@param $ arr Array для корректировки#@param $ запустить координаты родительского узла для корректировки#@@param $ end Координаты конечного узла, чтобы скорректировать функцию ajustnodes (& $ arr, $ start, $ end) {$ maxinx = $ start; $ len = $ end + 1; #Длина детали, которая должна быть скорректирована $ LealthChildInx = ($ start + 1) * 2 - 1; #Left Child Координата $ rightchildinx = ($ start + 1) * 2; #Right Child Comportinate #Если для корректировки детали есть левый ребенок, если ($ LealthChildInx + 1 <= $ len) {#GET Минимальная координата узла, если ($ arr [$ maxinx] <$ arr [$ LeatshildInx]) {$ maxinx = $ leftChildInx; } #Если корректировка детали имеет правильный дочерний узел, если ($ rightchildinx + 1 <= $ len) {if ($ arr [$ maxinx] <$ arr [$ rightchildinx])) {$ maxinx = $ rusthildinx; }}} #SWAP родительский узел и максимальный узел if ($ start! = $ Maxinx) {$ temp = $ arr [$ start]; $ arr [$ start] = $ arr [$ maxinx]; $ arr [$ maxinx] = $ temp; #, Если у детского узела после обмена есть дочерние узлы, продолжайте корректировать if (($ 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 Sorting
Принцип: Разрежьте целые числа в разные цифры с помощью цифр, а затем сравните их отдельно с каждой цифрой. Поскольку целые числа могут также выражать строки (например, имена или даты) и числа с плавающим запятой в определенных форматах, сортировка Radix используется не только для целых чисел.
Сложность времени: Средний случай: o (d (r+n)).
Сложность пространства: O (RD+N)
Стабильность: стабильная
<? Php #blassorting, здесь отсортированы только положительные целые числа. Что касается отрицательных чисел и номеров с плавающей запятой, необходим дополнение. Вы заинтересованы в изучении #Counting Sort #@@param ar arr Array для сортировки #@@param $ digit_num sort в соответствии с количеством функций цифр counting_sort (& $ arr, $ digit_num = false) {if ($ digit_num! == false) {#if параметр $ digit_num не является пустым, сортируйте в соответствии с $ digits $ digits. count ($ arr); }} else {$ arr_temp = $ arr; } $ max = max ($ arr); $ time_arr = array (); #Storage a Marray of Elements Accuratences#инициализируйте массив событий для ($ i = 0; $ i <= $ max; $ i ++) {$ time_arr [$ i] = 0; } #Статизируйте входы каждого элемента для ($ 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]; } #Сортируйте массив, используя количество случаев для ($ 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 Потеря эффективности сортировки ключей на этот раз} #calculate количество бит определенного числа функции get_digit ($ number) {$ i = 1; while ($ number> = pow (10, $ i)) {$ i ++; } return $ i; } #ЗАКОНОДАТЬ НОМЕР ДИРАЦИИ НОМЕРА Числа из функции одного цифр get_specific_digit ($ num, $ i) {if ($ num <power (10, $ i - 1)) {return 0; } возвратный этаж ($ num % pow (10, $ i) / pow (10, $ i - 1)); } #Black Sorting, Сортировка счета в качестве функции процесса подсадрирования Radix_SORT (& $ arr) {#first Найдите самую большую цифру в массиве $ max = max ($ arr); $ max_digit = get_digit ($ max); для ($ i = 1; $ i <= $ max_digit; $ i ++) {countting_sort ($ arr, $ i); }} $ arr = массив (23,0,32,45,56,75,43,0,34); radix_sort ($ arr); var_dump ($ arr);?>Выше всего содержание этой статьи. Я надеюсь, что это будет полезно для каждого обучения, и я надеюсь, что все будут поддерживать Wulin.com больше.