PHP中希尔排序详解

Mar 22, 2018 am 09:09 AM
php menyusun Penjelasan terperinci

希尔排序是先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高的,因此希尔排序在时间效率上比前两种方法有较大提高。

以n=10的一个数组49, 38, 65, 97, 26, 13, 27, 49, 55, 4为例

第一次 gap = 10 / 2 = 5

49   38   65   97   26   13   27   49   55   4

1A                                        1B

        2A                                         2B

                 3A                                         3B

                         4A                                          4B

                                  5A                                         5B

1A,1B,2A,2B等为分组标记,数字相同的表示在同一组,大写字母表示是该组的第几个元素, 每次对同一组的数据进行直接插入排序。即分成了五组(49, 13) (38, 27) (65, 49)  (97, 55)  (26, 4)这样每组排序后就变成了(13, 49)  (27, 38)  (49, 65)  (55, 97)  (4, 26),下同。

第二次 gap = 5 / 2 = 2

排序后

13   27   49   55   4    49   38   65   97   26

1A             1B             1C              1D            1E

        2A               2B             2C             2D              2E

第三次 gap = 2 / 2 = 1

4   26   13   27   38    49   49   55   97   65

1A   1B     1C    1D    1E      1F     1G    1H     1I     1J

第四次 gap = 1 / 2 = 0 排序完成得到数组:

4   13   26   27   38    49   49   55   65   97

例子:

<?php
/**
 * 希尔排序
 */
function shell_sort(array $arr){
    // 将$arr按升序排列
    $len = count($arr);
    $f = 3;// 定义因子
    $h = 1;// 最小为1
    while ($h < intval($len/$f)){
        $h = $f*$h + 1; // 1, 4, 13, 40, 121, 364, 1093, ...
    }
    while ($h >= 1){  // 将数组变为h有序
    	echo &#39;<br>&#39;.&#39;h:&#39;.$h.&#39;<br>&#39;.&#39;<br>&#39;;
        for ($i = $h; $i < $len; $i++){  // 将a[i]插入到a[i-h], a[i-2*h], a[i-3*h]... 之中 (算法的关键
        	echo &#39;i:&#39;.$i.&#39;<br>&#39;;
            for ($j = $i; $j >= $h && $arr[$j] < $arr[$j-$h];  $j -= $h){
                $temp = $arr[$j];
                $arr[$j] = $arr[$j-$h];
                $arr[$j-$h] = $temp;
                dump($arr);
            }
        }
        $h = intval($h/$f);
    }
    return $arr;
}
$arr = array(14, 9, 1, 4, 6, -3, 2, 99, 13, 20, 17, 15, 3);
dump($arr);
$shell = shell_sort($arr);
echo &#39;<pre class="brush:php;toolbar:false">&#39;;
print_r($shell);
function dump($arr)
{
	foreach ($arr as $value) {
		echo $value.&#39; &#39;;
	}
	echo &#39;<br>&#39;;
}
Salin selepas log masuk

结果:

14 9 1 4 6 -3 2 99 13 20 17 15 3
h:4
i:4
6 9 1 4 14 -3 2 99 13 20 17 15 3
i:5
6 -3 1 4 14 9 2 99 13 20 17 15 3
i:6
i:7
i:8
6 -3 1 4 13 9 2 99 14 20 17 15 3
i:9
i:10
i:11
6 -3 1 4 13 9 2 15 14 20 17 99 3
i:12
6 -3 1 4 13 9 2 15 3 20 17 99 14
6 -3 1 4 3 9 2 15 13 20 17 99 14
3 -3 1 4 6 9 2 15 13 20 17 99 14
h:1
i:1
-3 3 1 4 6 9 2 15 13 20 17 99 14
i:2
-3 1 3 4 6 9 2 15 13 20 17 99 14
i:3
i:4
i:5
i:6
-3 1 3 4 6 2 9 15 13 20 17 99 14
-3 1 3 4 2 6 9 15 13 20 17 99 14
-3 1 3 2 4 6 9 15 13 20 17 99 14
-3 1 2 3 4 6 9 15 13 20 17 99 14
i:7
i:8
-3 1 2 3 4 6 9 13 15 20 17 99 14
i:9
i:10
-3 1 2 3 4 6 9 13 15 17 20 99 14
i:11
i:12
-3 1 2 3 4 6 9 13 15 17 20 14 99
-3 1 2 3 4 6 9 13 15 17 14 20 99
-3 1 2 3 4 6 9 13 15 14 17 20 99
-3 1 2 3 4 6 9 13 14 15 17 20 99

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
)
Salin selepas log masuk

相关推荐:

JavaScript中的希尔排序详解

JS希尔排序与快速排序的实现方法

JavaScript排序算法之希尔排序的2个实例_基础知识

Atas ialah kandungan terperinci PHP中希尔排序详解. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Alat AI Hot

Undresser.AI Undress

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool

Undress AI Tool

Gambar buka pakaian secara percuma

Clothoff.io

Clothoff.io

Penyingkiran pakaian AI

AI Hentai Generator

AI Hentai Generator

Menjana ai hentai secara percuma.

Artikel Panas

R.E.P.O. Kristal tenaga dijelaskan dan apa yang mereka lakukan (kristal kuning)
2 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌
Repo: Cara menghidupkan semula rakan sepasukan
1 bulan yang lalu By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: Cara mendapatkan biji gergasi
4 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌

Alat panas

Notepad++7.3.1

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Dreamweaver CS6

Alat pembangunan web visual

SublimeText3 versi Mac

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Konfigurasi Projek CakePHP Konfigurasi Projek CakePHP Sep 10, 2024 pm 05:25 PM

Dalam bab ini, kita akan memahami Pembolehubah Persekitaran, Konfigurasi Umum, Konfigurasi Pangkalan Data dan Konfigurasi E-mel dalam CakePHP.

Panduan Pemasangan dan Naik Taraf PHP 8.4 untuk Ubuntu dan Debian Panduan Pemasangan dan Naik Taraf PHP 8.4 untuk Ubuntu dan Debian Dec 24, 2024 pm 04:42 PM

PHP 8.4 membawa beberapa ciri baharu, peningkatan keselamatan dan peningkatan prestasi dengan jumlah penamatan dan penyingkiran ciri yang sihat. Panduan ini menerangkan cara memasang PHP 8.4 atau naik taraf kepada PHP 8.4 pada Ubuntu, Debian, atau terbitan mereka

Tarikh dan Masa CakePHP Tarikh dan Masa CakePHP Sep 10, 2024 pm 05:27 PM

Untuk bekerja dengan tarikh dan masa dalam cakephp4, kami akan menggunakan kelas FrozenTime yang tersedia.

Muat naik Fail CakePHP Muat naik Fail CakePHP Sep 10, 2024 pm 05:27 PM

Untuk mengusahakan muat naik fail, kami akan menggunakan pembantu borang. Di sini, adalah contoh untuk muat naik fail.

Penghalaan CakePHP Penghalaan CakePHP Sep 10, 2024 pm 05:25 PM

Dalam bab ini, kita akan mempelajari topik berikut yang berkaitan dengan penghalaan ?

Bincangkan CakePHP Bincangkan CakePHP Sep 10, 2024 pm 05:28 PM

CakePHP ialah rangka kerja sumber terbuka untuk PHP. Ia bertujuan untuk menjadikan pembangunan, penggunaan dan penyelenggaraan aplikasi lebih mudah. CakePHP adalah berdasarkan seni bina seperti MVC yang berkuasa dan mudah difahami. Model, Pandangan dan Pengawal gu

Cara Menyediakan Kod Visual Studio (Kod VS) untuk Pembangunan PHP Cara Menyediakan Kod Visual Studio (Kod VS) untuk Pembangunan PHP Dec 20, 2024 am 11:31 AM

Kod Visual Studio, juga dikenali sebagai Kod VS, ialah editor kod sumber percuma — atau persekitaran pembangunan bersepadu (IDE) — tersedia untuk semua sistem pengendalian utama. Dengan koleksi sambungan yang besar untuk banyak bahasa pengaturcaraan, Kod VS boleh menjadi c

Pengesah Mencipta CakePHP Pengesah Mencipta CakePHP Sep 10, 2024 pm 05:26 PM

Pengesah boleh dibuat dengan menambah dua baris berikut dalam pengawal.

See all articles