Shell Sort

希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的:

插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率
但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位

https://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F


//Shell Sort
using System;
class Solution {
static void Main(String[] args) {

//initializing array
int[] arr={10,7,3,1,9,7,4,3};
Console.WriteLine(“Initial Array”);
Console.WriteLine(“[“+String.Join(” “, arr)+”]”);

shellsort(arr);

}
public static void shellsort(int[] arr)
{
int N=arr.Length;
int h=N/3;
int pass=1;
while(h>0)
{
for(int i=h;i<N;i++)
{
int temp=arr[i],j;
for(j=i;j>=h&&arr[j-h]>temp;j-=h)
{
arr[j]=arr[j-h];
}
arr[j]=temp;
}

Console.WriteLine(“After Pass “+pass+” [“+String.Join(” “, arr)+”]”);

pass++;

h/=2;
}
}
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s