苏州快速建设网站公司,儿童个人网站源码,网站友情链接建设,建设网站收费明细1、希尔排序
希尔排序#xff0c;也称递减增量排序算法#xff0c;是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的#xff1a;
插入排序在对几乎已经排好序的数据操作时#xff0c;效率高…1、希尔排序
希尔排序也称递减增量排序算法是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的
插入排序在对几乎已经排好序的数据操作时效率高即可以达到线性排序的效率但插入排序一般来说是低效的因为插入排序每次只能将数据移动一位
希尔排序的基本思想是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序待整个序列中的记录基本有序时再对全体记录进行依次直接插入排序。
1. 算法步骤
选择一个增量序列 t1t2……tk其中 ti tj, tk 1
按增量序列个数 k对序列进行 k 趟排序
每趟排序根据对应的增量 ti将待排序列分割成若干长度为 m 的子序列分别对各子表进行直接插入排序。仅增量因子为 1 时整个序列作为一个表来处理表长度即为整个序列的长度。
2. 示意图 代码实现
JavaScript
实例
function shellSort(arr) {
var len arr.length,temp,gap 1;
while(gap len/3) { *//动态定义间隔序列*
gap gap*31;
}
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[jgap] arr[j]; } arr[jgap] temp; } } return arr;}Python
实例
def shellSort(arr):
import math gap1
while(gap len(arr)/3):
gap gap*31
while gap 0:
for i in range(gap,len(arr)):
temp arr[i]
j i-gap
while j 0 and arr[j] temp:
arr[jgap]arr[j]
j-gap
arr[jgap] temp
gap math.floor(gap/3)
return arrGo
实例
func shellSort(arr []int) []int {
length : len(arr)
gap : 1
for gap length/3 {
gap gap*3 1
}
for gap 0 {
for i : gap; i length; i {
temp : arr[i]
j : i - gap
for j 0 arr[j] temp {
arr[jgap] arr[j]
j - gap
}
arr[jgap] temp
} gap gap / 3 } return arr}Java
实例
public static void shellSort(int[] arr) {int length arr.length;int temp;for (int step length / 2; step 1; step / 2) {for (int i step; i length; i) {temp arr[i];int j i - step;while (j 0 arr[j] temp) {arr[j step] arr[j];j - step;}arr[j step] temp;}}
}PHP
实例
function shellSort($arr){$len count($arr);$temp 0;$gap 1;while($gap $len / 3) {$gap $gap * 3 1;}for ($gap; $gap 0; $gap floor($gap / 3)) {for ($i $gap; $i $len; $i) {$temp $arr[$i];for ($j $i - $gap; $j 0 $arr[$j] $temp; $j - $gap) {$arr[$j$gap] $arr[$j];}$arr[$j$gap] $temp;}}return $arr;
}C
实例
void shell_sort(int arr[], int len) {int gap, i, j;int temp;for (gap len 1; gap 0; gap 1)for (i gap; i len; i) {temp arr[i];for (j i - gap; j 0 arr[j] temp; j - gap)arr[j gap] arr[j];arr[j gap] temp;}
}C
实例
templatetypename T
void shell_sort(T array[], int length) {int h 1;while (h length / 3) {h 3 * h 1;}while (h 1) {for (int i h; i length; i) {for (int j i; j h array[j] array[j - h]; j - h) {std::swap(array[j], array[j - h]);}}h h / 3;}
}2、归并排序 归并排序Merge sort是建立在归并操作上的一种有效的排序算法。该算法是采用分治法Divide and Conquer的一个非常典型的应用。
作为一种典型的分而治之思想的算法应用归并排序的实现由两种方法
自上而下的递归所有递归的方法都可以用迭代重写所以就有了第 2 种方法自下而上的迭代
在《数据结构与算法 JavaScript 描述》中作者给出了自下而上的迭代方法。但是对于递归法作者却认为 However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle. 然而在 JavaScript 中这种方式不太可行因为这个算法的递归深度对它来讲太深了。 说实话我不太理解这句话。意思是 JavaScript 编译器内存太小递归太深容易造成内存溢出吗还望有大神能够指教。
和选择排序一样归并排序的性能不受输入数据的影响但表现比选择排序好的多因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。
2. 算法步骤
申请空间使其大小为两个已经排序序列之和该空间用来存放合并后的序列设定两个指针最初位置分别为两个已经排序序列的起始位置比较两个指针所指向的元素选择相对小的元素放入到合并空间并移动指针到下一位置重复步骤 3 直到某一指针达到序列尾将另一序列剩下的所有元素直接复制到合并序列尾。
3. 示意图 代码实现
JavaScript
实例
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 right.length) {if (left[0] right[0]) {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;
}Python
实例
def mergeSort(arr):import mathif(len(arr)2):return arrmiddle math.floor(len(arr)/2)left, right arr[0:middle], arr[middle:]return merge(mergeSort(left), mergeSort(right))def merge(left,right):result []while left and right:if left[0] right[0]:result.append(left.pop(0))else:result.append(right.pop(0));while left:result.append(left.pop(0))while right:result.append(right.pop(0));return resultGo
实例
func mergeSort(arr []int) []int {length : len(arr)if length 2 {return arr}middle : length / 2left : arr[0:middle]right : arr[middle:]return merge(mergeSort(left), mergeSort(right))}func merge(left []int, right []int) []int {var result []intfor len(left) ! 0 len(right) ! 0 {if left[0] right[0] {result append(result, left[0])left left[1:]} else {
result append(result, right[0])right right[1:]}}for len(left) ! 0 {result append(result, left[0])left left[1:]}for len(right) ! 0 {result append(result, right[0])right right[1:]}return result
}Java
实例
public class MergeSort implements IArraySort {Overridepublic int[] sort(int[] sourceArray) throws Exception {// 对 arr 进行拷贝不改变参数内容int[] arr Arrays.copyOf(sourceArray, sourceArray.length);if (arr.length 2) {return arr;}int middle (int) Math.floor(arr.length / 2);int[] left Arrays.copyOfRange(arr, 0, middle);int[] right Arrays.copyOfRange(arr, middle, arr.length);return merge(sort(left), sort(right));}protected int[] merge(int[] left, int[] right) {int[] result new int[left.length right.length];int i 0;while (left.length 0 right.length 0) {if (left[0] right[0]) {result[i] left[0];
left Arrays.copyOfRange(left, 1, left.length);} else {result[i] right[0];right Arrays.copyOfRange(right, 1, right.length);}}while (left.length 0) {result[i] left[0];left Arrays.copyOfRange(left, 1, left.length);}while (right.length 0) {result[i] right[0];right Arrays.copyOfRange(right, 1, right.length);}return result;}
}PHP
实例
function mergeSort($arr){$len count($arr);if ($len 2) {return $arr;}$middle floor($len / 2);$left array_slice($arr, 0, $middle);$right array_slice($arr, $middle);return merge(mergeSort($left), mergeSort($right));}function merge($left, $right){ $result [];while (count($left) 0 count($right) 0) {if ($left[0] $right[0]) {$result[] array_shift($left);} else {$result[] array_shift($right);}}while (count($left))$result[] array_shift($left);while (count($right))$result[] array_shift($right);return $result;
}C
实例
int min(int x, int y) {return x y ? x : y;
}
void merge_sort(int arr[], int len) {int *a arr;int *b (int *) malloc(len * sizeof(int));int seg, start;for (seg 1; seg len; seg seg) {for (start 0; start len; start seg * 2) {int low start, mid min(start seg, len), high min(start seg * 2, len);int k low;int start1 low, end1 mid;int start2 mid, end2 high;while (start1 end1 start2 end2)b[k] a[start1] a[start2] ? a[start1] : a[start2];while (start1 end1)b[k] a[start1];while (start2 end2)b[k] a[start2];}int *temp a;a b;b temp;}if (a ! arr) {int i;for (i 0; i len; i)b[i] a[i];b a;}free(b);
}递归版
实例
void merge_sort_recursive(int arr[], int reg[], int start, int end) {if (start end)return;int len end - start, mid (len 1) start;int start1 start, end1 mid;int start2 mid 1, end2 end;merge_sort_recursive(arr, reg, start1, end1);merge_sort_recursive(arr, reg, start2, end2);int k start;while (start1 end1 start2 end2)reg[k] arr[start1] arr[start2] ? arr[start1] : arr[start2];while (start1 end1)reg[k] arr[start1];while (start2 end2)reg[k] arr[start2];for (k start; k end; k)arr[k] reg[k];
}void merge_sort(int arr[], const int len) {int reg[len];merge_sort_recursive(arr, reg, 0, len - 1);
}C
迭代版
实例
templatetypename T // 整數或浮點數皆可使用,若要使用物件(class)時必須設定小於()的運算子功能
void merge_sort(T arr[], int len) {T *a arr;T *b new T[len];for (int seg 1; seg len; seg seg) {for (int start 0; start len; start seg seg) {int low start, mid min(start seg, len), high min(start seg seg, len);int k low;int start1 low, end1 mid;int start2 mid, end2 high;while (start1 end1 start2 end2)b[k] a[start1] a[start2] ? a[start1] : a[start2];while (start1 end1)b[k] a[start1];while (start2 end2)b[k] a[start2];}T *temp a;a b;b temp;}if (a ! arr) {for (int i 0; i len; i)b[i] a[i];b a;}delete[] b;
}递归版
实例
void Merge(vectorint Array, int front, int mid, int end) {// preconditions:// Array[front...mid] is sorted// Array[mid1 ... end] is sorted// Copy Array[front ... mid] to LeftSubArray// Copy Array[mid1 ... end] to RightSubArrayvectorint LeftSubArray(Array.begin() front, Array.begin() mid 1);vectorint RightSubArray(Array.begin() mid 1, Array.begin() end 1);int idxLeft 0, idxRight 0;LeftSubArray.insert(LeftSubArray.end(), numeric_limitsint::max());RightSubArray.insert(RightSubArray.end(), numeric_limitsint::max());// Pick min of LeftSubArray[idxLeft] and RightSubArray[idxRight], and put into Array[i]for (int i front; i end; i) {if (LeftSubArray[idxLeft] RightSubArray[idxRight]) {Array[i] LeftSubArray[idxLeft];idxLeft;} else {Array[i] RightSubArray[idxRight];idxRight;}}
}void MergeSort(vectorint Array, int front, int end) {if (front end)return;int mid (front end) / 2;MergeSort(Array, front, mid);MergeSort(Array, mid 1, end);Merge(Array, front, mid, end);
}C#
实例
public static Listint sort(Listint lst) {if (lst.Count 1)return lst;int mid lst.Count / 2;Listint left new Listint();// 定义左侧ListListint right new Listint();
// 定义右侧List// 以下兩個循環把 lst 分為左右兩個 Listfor (int i 0; i mid; i)
left.Add(lst[i]);for (int j mid; j lst.Count; j)right.Add(lst[j]);left sort(left);right sort(right);return merge(left, right);}
/// summary
/// 合併兩個已經排好序的List
/// /summary
/// param nameleft左側List/param
///param nameright右側List/paramreturns/returnsstatic Listint merge(Listint left, Listint right) {Listint temp new Listint();while (left.Count 0 right.Count 0) {if (left[0] right[0]) {temp.Add(left[0]);left.RemoveAt(0);} else {temp.Add(right[0]);right.RemoveAt(0);}}if (left.Count 0) {for (int i 0; i left.Count; i)temp.Add(left[i]);} if (right.Count 0) {for (int i 0; i right.Count; i)temp.Add(right[i]);}return temp;}Ruby
实例
def merge listreturn list if list.size 2pivot list.size / 2# Merge lambda { |left, right|final []until left.empty? or right.empty?final if left.first right.first; left.shift else right.shiftendendfinal left right}.call merge(list[0...pivot]), merge(list[pivot..-1])
end
