标签归档：排序

PHP源码阅读笔记二十六：PHP快速排序源码实现的简化版本

3条回复

PHP源码阅读笔记：PHP中的快速排序实现的简化版本
这段时间在复习数据结构，有看到排序及经典的快速排序
于是有了看下PHP中实现排序的方式，在Zend目录下我们可以看到zend_qsort.c文件及zend_qsort.h文件
这是PHP实现快速排序的文件所在
从代码中我们可以看到，也许是为了兼容多种数据类型，所以其在交换及比较位置比较复杂，看起来也比较纠结，于是自己将
其中的类型全部换成int类型，得到简化版本的PHP源码中的快速排序
其代码如下 ：

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

#include <stdio.h>
 
static qsort_swap(int *a, int *b)
{
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}
 
void qsort(int *base, int nmemb)
{
	int *begin_stack[10];
	int *end_stack[10];
	int *begin;
	int *end;
	int *seg1;
	int *seg2;
	int *seg2p;
	int loop;
	unsigned int offset;
 
	/* 使用栈而不是常见的递归实现 */
	begin_stack[0] = base;	//	开始元素位置栈，入栈
	end_stack[0]   = base + (nmemb - 1) ;	//	结束位置栈，入栈
 
	for (loop = 0; loop >= 0; --loop) {
		begin = begin_stack[loop];	//	开始位置出栈
		end   = end_stack[loop];	//	结束位置出栈
 
		while (begin < end) {
			offset = (end - begin) >> 1;	//	取中间位置
 
			qsort_swap(begin, begin + offset);	//	交换开始和中间的位置
 
			seg1 = begin;
			seg2 = end;
 
			while (1) {
				for (; seg1 < seg2 && *begin < *seg1 ; seg1 += 1);
 
				for (; seg2 >= seg1 && *seg2 > *begin; seg2 -= 1);
 
				if (seg1 >= seg2)
					break;
 
				qsort_swap(seg1, seg2);
			}
 
			qsort_swap(begin, seg2);
 
			seg2p = seg2;
 
			if ((seg2p - begin) <= (end - seg2p)) {
				if (seg2p < end) {	//	右侧入栈
					begin_stack[loop] = seg2p + 1;
					end_stack[loop++] = end;
				}
				end = seg2p;
			} else {
				if (seg2p > begin) {	// 左侧入栈
					begin_stack[loop] = begin;
					end_stack[loop++] = seg2p - 1;
				}	//	end if
				begin = seg2p;
			}	//	end if
		}	//	end while
	}	//	end for
 
}
int main(int argc, char *argv[])
{
	int a[10] = {14, 5, 7, 8, 2, 4, 55, 3};
	int i;
	qsort(a, 8);
	for (i = 0; i < 8;i++) 
	{
		printf("%d ", a[i]);
	}
	return 0;
}

看完后，有一个感受：强大的指针，受益非浅！

数据结构复习笔记：使用PHP实现内排序之冒泡排序和简单选择排序

1条回复

数据结构复习笔记：使用PHP实现内排序之冒泡排序和简单选择排序
【基本概念】
排序：排序是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列
内排序：内排序指的是待排序记录在放在计算机随机存储器中进行的排序过程
内排序大致可分为插入排序、交换排序、选择排序、归并排序和计数排序
在排序的过程中需要进行两种基本操作：1、比较两个关键字的大小，2、将记录从一个位置移动到另一个位置
【冒泡排序过程】
首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较批二个记录和第三个记录的关键字，依次类推，直至第n-1个元素和第n个元素进行过比较为止。以上为一次冒泡排序，礤结果是使得关键字最大的记录被安置到最后一个记录的位置上。然后进行第二真趟冒泡排序，对前n-1个记录进行同样操作，其结果是使关键字次大的记录安置到第n-1人的位置上，如此类似
【冒泡排序的PHP实现】

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

<?php
/**
 * 数据结构中冒泡排序PHP实现 2010-07-26 sz
 * @author phppan.p#gmail.com  http://www.phppan.com                                                    
 * 哥学社成员（http://www.blog-brother.com/）
 * @package data struct
 */
 
/**
 * 冒泡排序 将数组从小到排序
 * @param array $array 需要排序的数据
 * @return array
 */
function bubble_sort($array) {
    if (!is_array($array)) {
        return FALSE;
    }
 
    $len = count($array);
    for ($i = 0; $i < $len - 1; $i++) {
        for ($j = 0; $j < $len - $i - 1; $j++) {
            if ($array[$j] > $array[$j + 1]) {
                $temp = $array[$j];
                $array[$j] = $array[$j + 1];
                $array[$j + 1] = $temp;
            }
        }
    }
 
    return $array;
}
 
/* 示例 */
$array = array(3, 2, 1, 4, 6, 7, 8, 0, 55);
var_dump(bubble_sort($array));
?>

【简单选择排序的过程】
选择排序的基本思想是：每一趟在n-i+1(i = 1,2,…,n-1)个记录中选择关键字最小的记录作为有序序列中第i个记录
其中最简单的是简单选择排序，其过程如下：
通过n-i次关键字间的比较，从n-i+1个记录中选择出关键字最小的记录，并各第i个记录交换之。
【简单选择排序的PHP实现】

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

<?php
/**
 * 数据结构中简单选择排序PHP实现 2010-07-26 sz
 * @author phppan.p#gmail.com  http://www.phppan.com                                                 
 * 哥学社成员（http://www.blog-brother.com/）
 * @package data struct
 */
 
/**
 * 简单选择排序，将数组从小到大排序
 * @param array $array 需要进行排序的数组
 * @return array $array
 */
function select_sort($array) {
    if (!is_array($array)) {
        return FALSE;
    }
 
    $len = count($array);
    for ($i = 0; $i < $len - 1; $i++) {
        for ($j = $i + 1; $j < $len; $j++) {
            if ($array[$i] > $array[$j]) {
                $temp = $array[$i];
                $array[$i] = $array[$j];
                $array[$j] = $temp;
            }
        }
    }
 
    return $array;
}
 
/* 示例 */
$array = array(3, 2, 1, 4, 6, 7, 8, 0, 55);
var_dump(select_sort($array));
?>

温故知新，以前对这两种排序方式一直模糊不清，总算了结了