GVKun编程网logo

php实现希尔排序算法的方法分析（php实现希尔排序算法的方法分析）

11

在本文中，我们将带你了解php实现希尔排序算法的方法分析在这篇文章中，我们将为您详细介绍php实现希尔排序算法的方法分析的方方面面，并解答php实现希尔排序算法的方法分析常见的疑惑，同时我们还将给您一

在本文中，我们将带你了解php实现希尔排序算法的方法分析在这篇文章中，我们将为您详细介绍php实现希尔排序算法的方法分析的方方面面，并解答php实现希尔排序算法的方法分析常见的疑惑，同时我们还将给您一些技巧，以帮助您实现更有效的C#实现希尔排序、C++实现希尔排序算法实例、c++实现排序算法之希尔排序方式、C++深入浅出讲解希尔排序算法的实现。

本文目录一览：

php实现希尔排序算法的方法分析（php实现希尔排序算法的方法分析）

php实现希尔排序算法的方法分析（php实现希尔排序算法的方法分析）

本文实例讲述了php实现希尔排序算法的方法。分享给大家供大家参考，具体如下：

虽然现在各种程序语言都有其各自强大的排序库函数，但是这些底层实现也都是利用这些基础或高级的排序算法。

理解这些复杂的排序算法还是很有意思的，体会这些排序算法的精妙~

希尔排序（shell sort）：希尔排序是基于插入排序的，区别在于插入排序是相邻的一个个比较（类似于希尔中h=1的情形），而希尔排序是距离h的比较和替换。

希尔排序中一个常数因子n，原数组被分成各个小组，每个小组由h个元素组成，很可能会有多余的元素。当然每次循环的时候，h也是递减的（h=h/n）。第一次循环就是从下标为h开始。希尔排序的一个思想就是，分成小组去排序。

理解这些算法，最好是有个图示。就先来代码吧。

<?php
/**
 * 希尔排序
 */
function shell_sort(array $arr){
  // 将$arr按升序排列
  $len = count($arr);
  $f = 3;// 定义因子
  $h = 1;// 最小为1
  while ($h < $len/$f){
    $h = $f*$h + 1; // 1, 4, 13, 40, 121, 364, 1093, ...
  }
  while ($h >= 1){ // 将数组变为h有序
    for ($i = $h; $i < $len; $i++){ // 将a[i]插入到a[i-h], a[i-2*h], a[i-3*h]... 之中 （算法的关键
      for ($j = $i; $j >= $h; $j -= $h){
        if ($arr[$j] < $arr[$j-$h]){
          $temp = $arr[$j];
          $arr[$j] = $arr[$j-$h];
          $arr[$j-$h] = $temp;
        }
        //print_r($arr);echo ''<br/>''; // 打开这行注释，可以看到每一步被替换的情形
      }
    }
    $h = intval($h/$f);
  }
  return $arr;
}
$arr = array(14, 9, 1, 4, 6, -3, 2, 99, 13, 20, 17, 15, 3);
$shell = shell_sort($arr);
echo ''<pre>'';
print_r($shell);
/**
*
Array
(
[0] => -3
[1] => 1
[2] => 2
[3] => 3
[4] => 4
[5] => 6
[6] => 9
[7] => 13
[8] => 14
[9] => 15
[10] => 17
[11] => 20
[12] => 99
)
)
*
*/

PS：这里再为大家推荐一款关于排序的演示工具供大家参考：

在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具：
http://tools.jb51.net/aideddesign/paixu_ys

更多关于PHP相关内容感兴趣的读者可查看本站专题：《php排序算法总结》、《PHP数据结构与算法教程》、《php程序设计算法总结》、《PHP数组(Array)操作技巧大全》、《php字符串(string)用法总结》、《PHP常用遍历算法与技巧总结》及《PHP数学运算技巧总结》

希望本文所述对大家PHP程序设计有所帮助。

您可能感兴趣的文章:
  • PHP排序算法之直接插入排序(Straight Insertion Sort)实例分析
  • PHP排序算法之简单选择排序(Simple Selection Sort)实例分析
  • PHP排序算法之冒泡排序(Bubble Sort)实现方法详解
  • PHP 快速排序算法详解
  • PHP 冒泡排序算法的实现代码
  • PHP 冒泡排序 二分查找 顺序查找 二维数组排序算法函数的详解
  • php实现的常见排序算法汇总
  • PHP 各种排序算法实现代码
  • PHP简单选择排序算法实例
  • PHP排序算法之希尔排序(Shell Sort)实例分析

C#实现希尔排序

C#实现希尔排序

对于大规模乱序的数组，插入排序很慢，因为它只会交换相邻的元素，因此元素只能一点一点地从数组地一段移动到另一端。希尔排序改进了插入排序，交换不相邻地元素以对数组地局部进行排序，最终用插入排序将局部有序的数组排序。

希尔排序的思想是使数组中任意间隔为 h 的元素都是有序的。这样的数组成为 h 有序数组。换句话说，一个 h 有序数组就是 h 个相互独立的有序数组组合在一起的一个数组。

在进行排序时，刚开始 h 很大，就能将元素移动到很远的地方，为实现更小的 h 有序创造方便。h 递减到 1 时，相当于插入排序。这就是希尔排序。下面的代码 h 从 N/3 开始递减，h = h * 3 + 1:

public class Shell: BaseSort
    {
        public static long usedTimes = 0;
        public Shell()
        {
        }

        public static void Sort(IComparable[] a)
        {
            Stopwatch timer = new Stopwatch();
            timer.Start();
            int n = a.Length;
            int h = 1;
            while (h < n / 3)
                h = h * 3 + 1;

            /*
             * 每次循环生成 h有序数组（h 个有序数组） 即 （h 0）, （h+1 1）, （h+2 2）, ....
             *      如果右边的值小于左边的值时，交换；
             *      并退回到左边的位置，重新排序，循环比较（j>=h）。
             *      因为交换可能引起原有序的数组乱序，所以需要退回去重新比较
             * 当 h 递减到 1时，相当于插入排序一个部分有序数组
             * */
            while (h >= 1)
            {
                //Console.WriteLine(h);
                for (int i = h; i < n; i++)
                {
                    //Console.WriteLine(i+","+(i - h));
                    for (int j = i; j >= h && Less(a[j], a[j - h]); j -= h)
                    {
                        Exch(a,j,j-h);
                        //Console.WriteLine("J:" + (j- h));
                    }
                }
                h = h / 3;
            }

            timer.Stop();
            usedTimes = timer.ElapsedMilliseconds;
        }
    }

从另一个角度看希尔排序，插入排序是将每个比元素大的元素向右移动一个，希尔排序是交换到比它大的元素之前，移动距离从 1 改成 h 。

希尔排序更高效的原因是它将数组变成多个部分有序的数组，减少倒置。排序之初，各个子数组都很短，排序之后子数组都是部分有序的，这很适合插入排序。子数组部分有序的程度取决于递增序列的选择。（如何选择？？）

  • 和选择排序以及插入排序对比，希尔排序也可以用于大型数组，即使是随机数字排序也快很多。数组规模越大，对比越明显。
  • 希尔排序的性能分析比较困难。它的运行时间达不到平方级别，在最坏情况下的比较次数和  N ^ 3/2 成正比。
  • 如果中等大小的数组可以使用希尔排序，它代码量少，且不需要额外的内存空间。

百万级别的排序时间不超过十秒：

count:10000 shell use Milliseconds:6
count:100000 shell use Milliseconds:180
count:1000000 shell use Milliseconds:3226

到此这篇关于C#实现希尔排序的文章就介绍到这了。希望对大家的学习有所帮助，也希望大家多多支持。

您可能感兴趣的文章:
  • C#实现平衡查找树
  • C#实现二叉查找树
  • C#使用符号表实现查找算法
  • C#实现优先队列和堆排序
  • C#实现快速排序算法
  • C#实现归并排序
  • C#算法之散列表

C++实现希尔排序算法实例

C++实现希尔排序算法实例

1.代码模板

// 希尔排序（Shell Sort）
void ShellSort(SqList *L)
{
    int i, j;
    int increment = L->length;  // 先让增量初始化为序列的长度
    do {
        increment = increment / 3 + 1;   // 计算增量的值
        for (i = increment + 1; i <= L->length; i ++ ) { 
            if (L->arr[i] < L->arr[i - increment]) {   // 如果L->[i]需要插入有序增量子表
                L->arr[0] = L->arr[i];   // 暂存在哨兵位
                for (j = i - increment; j > 0 && L->arr[0] < L->arr[j]; j -= increment) {  // 遍历增量子表，寻找插入位置
                    L->arr[j + increment] = L->arr[j];
                }
                L->arr[j+increment] = L->arr[0];  // 插入
            }
        }
    } while (increment > 1);
}

2.算法介绍

希尔排序，又叫缩小增量排序，算法属于插入类排序的进阶算法，采取跳跃分割的策略，将关键字较小的元素跳跃式的往前挪，大大减小了交换比较的次数。使得序列整体基本有序 ，即大的元素基本在后面，小的元素基本在前面，不大不小的元素基本在中间。

希尔排序的关键在于将序列中相隔某个“增量”的元素组成一个子序列，且序列的最后一个增量必须为1，这样才能保证最后的结果是有序且正确的。但增量如何选择为最佳，至今仍无定论。且由于元素是跳跃式移动的，所有希尔排序是一个不稳定的排序算法，其时间复杂度受到增量选择的影响，最好为O(n^1.3) , 最坏为O(n*n)。

3.实例

#include <iostream>
using namespace std;

const int N = 100;

typedef struct
{
    int arr[N];    // 存储待排序的序列
    int length;    // 存储序列的长度
} SqList;

void ShellSort(SqList *L)
{
    int i, j;
    int increment = L->length;
    do {
        increment = increment / 3 + 1;
        for (i = increment + 1; i <= L->length; i ++ ) {
            if (L->arr[i] < L->arr[i - increment]) {
                L->arr[0] = L->arr[i];
                for (j = i - increment; j > 0 && L->arr[0] < L->arr[j]; j -= increment)
                    L->arr[j + increment] = L->arr[j];
                L->arr[j + increment] = L->arr[0];
            }
        }
    } while (increment > 1);
}

int main()
{
    SqList L;
    L.arr[1] = 50;
    L.arr[2] = 10;
    L.arr[3] = 90;
    L.arr[4] = 30;
    L.arr[5] = 70;
    L.arr[6] = 40;
    L.arr[7] = 80;
    L.arr[8] = 60;
    L.arr[9] = 20;
    L.length = 9;

    ShellSort(&L);
    for (int i = 1; i <= L.length; i ++ )
        cout << L.arr[i] << " ";

}

到此这篇关于C++实现希尔排序算法实例的文章就介绍到这了,更多相关C++希尔排序算法内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！

您可能感兴趣的文章:
  • C++深入浅出讲解希尔排序算法的实现
  • C++实现八个常用的排序算法 插入排序、冒泡排序、选择排序、希尔排序等
  • c++实现排序算法之希尔排序方式

c++实现排序算法之希尔排序方式

c++实现排序算法之希尔排序方式

排序算法之希尔排序

基本思想

将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序的而不是局部有序。

进一步理解：

先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。

希尔排序算法

#include <iostream>
using namespace std; 
void shellSort(int arr[], int n)
{
    int tmp = 0;
    int step = n / 2;
    while (step)
    {
        for (int i = step; i < n; i++)
        {
            tmp = arr[i];
            int j = i;
            while (j >= step && tmp < arr[j - step])   //采用直接插入排序
            {
                arr[j] = arr[j - step];
                j -= step;
            }
 
            arr[j] = tmp;
        }
 
        step = step / 2;
    }
}
 
int main()
{
    int arr[]{ 3, 14, 25, -22, -3, 87, 126, 34, 64, -70, 15, 17, 78 };
    int n = sizeof(arr) / sizeof(arr[0]);
    shellSort(arr, n);
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
 
    system("pause");
    return 0;
}

复杂度分析

当增量为1（step = 1）时，希尔排序退化成了直接插入排序，此时的时间复杂度为O(N²)；

Hibbard增量的希尔排序的时间复杂度O(n^3/2)；

关于希尔排序的问题分析

排序算法之希尔排序及时间复杂度分析

希尔排序

算法思想：将整个待排序列分割成若干个子序列（由相隔增量个元素组成），分别进行直接插入排序，然后依次缩小增量再进行排序，待整个序列中的元素基本有序时，再对全体元素进行一次直接插入排序。

希尔排序的实现应该由三个循环完成

（1）第一次循环，将增量d依次折半，直到增量d=1

（2）第二三层循环，也就是直接插入排序所需要的两次循环。

算法实现：

#include <stdio.h>
#define N 9
int main(void)
{
	int arr[N] = {9,1,5,8,3,7,4,6,2};
	int d = N / 2; //增量先取一半
	int i,j,insertVal;
	//希尔排序三层循环
	while(d>=1) //当增量大于等于1,不断进行插入排序
	{
		//一下两层for循环是直接插入排序代码
		for(i=d; i<N; i++)
		{
			insertVal = arr[i];
			j = i - d;
			while(j>=0 && arr[j]>insertVal)
			{
				arr[j+d] = arr[j];
				j = j - d;
			}
			arr[j+d] = insertVal;
		}
		d = d / 2;
	}
	for(i=0; i<N; i++)
	{
		printf("%d ",arr[i]);
	}
	return 0;
}

由如上代码知，希尔排序的关键并不是随便分组后各自排序，而是将相隔某个增量的记录组成一个子序列，实现跳跃式移动，使得排序的效率高。

时间复杂度

时间复杂度为O(n^1.5)，要好于直接排序的O(n ^ 2)，需要注意的是增量序列的最后一个增量值必须是1.另外由于记录跳跃式的移动，希尔排序并不是一种稳定的排序方法。

以上为个人经验，希望能给大家一个参考，也希望大家多多支持。

您可能感兴趣的文章:
  • C++深入浅出讲解希尔排序算法的实现
  • C++实现希尔排序算法实例
  • C++实现八个常用的排序算法 插入排序、冒泡排序、选择排序、希尔排序等

C++深入浅出讲解希尔排序算法的实现

C++深入浅出讲解希尔排序算法的实现

插入排序分为两种：直接插入排序&希尔排序

希尔排序

1.基本思想

希尔排序是在直接插入排序基础上的优化，属于非常牛掰的一个排序。

核心思想：

  • 先进行预排序，让数组接近有序；
  • 直接插入排序

预排序

预排序步骤：

分组排，假设gap==3，间隔为gap的为一组，然后分别使用插入排序的思想对这gap组数据进行排序

多组间隔为gap的预排序，gap由大变小，gap越大，大的数可以越快的到后面，小的数可以越快得到前面，gap越大，预排完越不接近有序，gap越小，预排完越接近有序，gap为1时就是直接插入排序

动图演示：

预排序代码：

		for (int i = 0; i < gap; i++)//有gap组需要排
		{
			for (int j = i; j < n - gap; j += gap)//内层循环，先排红，再排绿，最后排蓝
			//注意内层循环的写法
			{
			//跟直接插入排序很像，不同的是需要使用gap
				int end = j;
				int tmp = a[end + gap];
				while (end >= 0)
				{
					if (a[end] > tmp)
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
					{
						break;
					}
				}
				a[end + gap] = tmp;
			}
		}

这是最初的写法，其实这个代码是可以优化的：

//预排序优化
		for (int i = 0; i < n - gap; i++)
		//把间隔为gap的多组数据同时排
		//当到n-gap-1的位置就终止了
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}

2.算法实现

//希尔排序
void ShellSort(int* a, int n)
{
	//一开始初始化gap为n
	int gap = n;
	while (gap > 1)//gap大于1都是预排序，gap==1时为直接插入排序
	{
		//为保证gap最终结果为1，可以gap/=2，也可以是gap=gap/3+1;
		gap /= 2;
		//预排序优化
		for (int i = 0; i < n - gap; i++)
		//把间隔为gap的多组数据同时排
		//当到n-gap-1的位置就终止了
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

完整代码：

3.时间复杂度

希尔排序的时间复杂度是：O(N*logN)

到此这篇关于C++深入浅出讲解希尔排序算法的实现的文章就介绍到这了,更多相关C++希尔排序内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！

您可能感兴趣的文章:
  • C++实现希尔排序算法实例
  • C++实现八个常用的排序算法 插入排序、冒泡排序、选择排序、希尔排序等
  • c++实现排序算法之希尔排序方式

今天的关于php实现希尔排序算法的方法分析和php实现希尔排序算法的方法分析的分享已经结束，谢谢您的关注，如果想了解更多关于C#实现希尔排序、C++实现希尔排序算法实例、c++实现排序算法之希尔排序方式、C++深入浅出讲解希尔排序算法的实现的相关知识，请在本站进行查询。

本文标签：

上一篇PHP服务端环境搭建的图文教程(分享)（php服务器环境搭建过程）

下一篇PHP使用自定义key实现对数据加密解密的方法（php使用自定义key实现对数据加密解密的方法是）

相关文章