希尔排序ShellSort

14. November 2017 深度学习 0
PHP实现
<?php
$arr = [1, 4, 3, 2, 7, 9, 33, 23, 6, 77, 44, 99, 12, 5, 6, 3, 1, 91];
function ShellSort(&$arr){
 $N=count($arr);
 $h=1;
 while ($h<floor($N/3)){
 $h=3*$h+1;
 }
 while ($h>=1){
 for ($i=$h;$i<$N;$i++){
 for ($j=$i;$j>=$h&&$arr[$j]<$arr[$j-$h];$j-=$h){
 $temp=$arr[$j];
 $arr[$j]=$arr[$j-$h];
 $arr[$j-$h]=$temp;
 }
 }
 $h=floor($h/3);
 }
}
ShellSort($arr);
echo implode(',',$arr);
Python实现
def ShellSort():
    N=len(arr)
    h=1
    while h<N/3:
        h=3*h+1
    while h>=1:
        for i in range(h,N):
            j=i
            while j>=h and arr[j]<arr[j-h]:
                arr[j],arr[j-h]=arr[j-h],arr[j]
                j=j-h
        h=h/3

if __name__ == '__main__':
    arr = [1, 4, 3, 2, 7, 9, 33, 23, 6, 77, 44, 99, 12, 5, 6, 3, 1, 91]
    ShellSort()
    print arr
JavaScript实现
<script>

var arr = [1, 4, 3, 2, 7, 9, 33, 23, 6, 77, 44, 99, 12, 5, 6, 3, 1, 91];

function ShellSort() {

var N = arr.length;

var h = 1;

while(h < parseInt(N / 3)) {

h = 3 * h + 1;

}

while(h >= 1) {

for(i = h; i < N; i++) {

for(j = i; j >= h && arr[j] < arr[j - h]; j -= h) {

var temp = arr[j];

arr[j] = arr[j - h];

arr[j - h] = temp;

}

}

h = parseInt(h / 3);

}

}

ShellSort();

document.write(arr);

</script>
Java实现
package lijian;

import java.util.Arrays;

public class Lijian {
 
 public static void ShellSort(int[] a){
 int n=a.length;
 int h=1;
 while(h<n/3){
 h=3*h+1;
 }
 while(h>=1){
 for(int i=h;i<n;i++){
 for(int j=i;j>=h&&a[j]<a[j-h];j-=h){
 int temp=a[j];
 a[j]=a[j-h];
 a[j-h]=temp;
 }
 }
 h=h/3;
 } 
 }
public static void main(String[] args) {
 // TODO code application logic here
 int[] arr = { 1, 4, 3, 2, 7, 9, 33, 23, 6, 77, 44, 99, 12, 5, 6, 3, 1, 91 };
 ShellSort(arr);
 System.out.println(Arrays.toString(arr));
 }
}