52、PHP 实现选择排序

题目： PHP 实现选择排序

描述：

• 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。
• 所有距离为dl的倍数的记录放在同一个组中。
• 先在各组内进行直接插人排序；
• 然后，取第二个增量d2<d1重复上述的分组和排序，
• 直至所取的增量dt=1(dt<dt-l<…<d2<d1)，
• 即所有记录放在同一组中进行直接插入排序为止。
• 该方法实质上是一种分组插入方法。
• 希尔排序是不稳定的

function shellSort(array $list)
{
	$length = count($list);
	$step = 2;
	$gap = intval($length/$step);
	while($gap > 0){
		for($gap_i = 0; $gap_i < $gap; $gap_i++){
			for($i = $gap_i; $i < $length; $i+=$gap){
				$temp = $list[$i];
				for($j = $i - $gap; $j >= 0; $j-=$gap){
					if($temp < $list[$j]){
						$list[$j+$gap] = $list[$j];
						$list[$j] = $temp;
					}else{
						break;
					}
				}
			}
		}
	}
	return $list;
}

$list = array(3, 6, 2, 4, 10, 1 ,9, 8, 5, 7);
var_dump(shellSort($list));
/**
 * 第1趟, gap = 5
 * 分成了两个数组：(对应下标元素进行比较)
 * (3, 6, 2, 4, 10) (1, 9, 8, 5, 7)
 * 交换后的过程：
 * (1, ...) (3, ...)
 * (1, 6, ...) (3, 9, ...)
 * (1, 6, 2, ...) (3, 9, 8, ...)
 * (1, 6, 2, 4, ...) (3, 9, 8, 5, ...)
 * (1, 6, 2, 4, 7) (3, 9, 8, 5, 10)
 * 第2趟，gap = 2
 * 分成了五个数组
 * (1, 6) (2, 4) (7, 3) (9, 8) (5, 10)
 * 交换过程
 * (1, ...) (2, ...) (5, ...) (7, ...) (9, ...)
 * (1, 3) (2, 4) (5, 6) (7, 8) (9, 10)
 * 第3趟， gap = 1
 * 元素比较
 * 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45