Fork me on GitHub

排序算法

发表于 | 分类于 | 浏览 次

基本概念

  排序(Sorting)是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列。排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

  排序的稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

算法性能比较如下图所示：

排序算法

排序算法归纳

插入排序

直接插入排序(Straight Insertion Sort)

基本思想：将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。
要点：设立哨兵，作为临时存储和判断数组边界之用。
直接插入排序示例：
排序示例

如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，我所以插入排序是稳定的

算法的实现

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
function insertSort($a, $num) {
	for($i= 1; $i<$num; $i++) {  
		if($a[$i] < $a[$i-1]) {               //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入  
			$j= $i-1;   
			$x = $a[$i];        //复制为哨兵，即存储待排序元素  
			$a[$i] = $a[$i-1];           //先后移一个元素  
			while($x < $a[$j]){  //查找在有序表的插入位置  
				$a[$j+1] = $a[$j];  
				$j--;         //元素后移  
			}  
			$a[$j+1] = $x; //插入到正确位置
		}  
		echo $i . ':' . implode($a, ',').PHP_EOL; //打印每趟排序的结果
	}  
}

function insertion_sort(&$arr) { 
	for ($i = 1; $i < count($arr); $i++) {
		$temp = $arr[$i];
		for ($j = $i - 1; $j >= 0 && $arr[$j] > $temp; $j--)
			$arr[$j + 1] = $arr[$j];
	 	$arr[$j + 1] = $temp;
	}
	echo implode($arr, ',').PHP_EOL; 
}
折半插入排序

基本思想
1）计算 0 ~ i-1 的中间点，用 i 索引处的元素与中间值进行比较，如果 i
引处的元素大，说明要插入的这个元素应该在中间值和刚加入i索引之间，反之，就是在刚开始的位置 到中间值的位置，这样很简单的完成了折半；
2）在相应的半个范围里面找插入的位置时，不断的用（1）步骤缩小范围，不停的折半，范围依次缩小为 1/2 1/4 1/8 …….快速的确定出第 i
个元素要插在什么地方；
3）确定位置之后，将整个序列后移，并将元素插入到相应位置。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function BInsertSort($arr, $count)  { /*对作折半插入排序。*/  
	for($i=1; $i<$count; ++$i) 	{  
		$temp = $arr[$i]; /* 将$arr[$i]暂存到$temp */  
		$low=0;  
		$high=$i-1;  
		while($low<=$high)  
		{
			/* 在$arr[low..high]中折半查找有序插入的位置 */  
			$mid= intval(($low+$high)/2); /* 折半 * */  
			if($temp < $arr[$mid])  
				$high = $mid-1; /* 插入点在低半区* */  
			else  
				$low = $mid + 1; /* 插入点在高半区* */  
		}  
		for($j=$i-1;$j>=$mid;$j--)  
			$arr[$j+1]=$arr[$j]; /* 记录后移 * */  
		$arr[$low]=$temp; /* 插入 * */  
	}  
	echo implode($arr,',');
}

希尔排序（Shell`s Sort）

希尔排序是1959 年由D.L.Shell 提出来的，相对直接排序有较大的改进。希尔排序又叫缩小增量排序

基本思想
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。操作方法：
1、选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2、按增量序列个数k，对序列进行k 趟排序；
3、每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m
的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。
希尔排序的示例：
希尔排序

算法实现

简单处理增量序列：增量序列d = {n/2 ,n/4, n/8 …..1} n为要排序数的个数
即：先将要排序的一组记录按某个增量d（n/2,n为要排序数的个数）分成若干组子序列，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。继续不断缩小增量直至为1，最后使用直接插入排序完成排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function shellSort($a) {
	$l = count($a);
	$d = floor($l/2);
	while($d>=1) {
		for($i=$d; $i<$l; $i++) {
			$t = $a[$i];
			$j = $i-$d;// 获取组内上一个数据 , 然后不断往前与当前数据比较
			while($j>=0 && $a[$j]>$t){
				$a[$j+$d] = $a[$j];
				$j -= $d;
			}
			$a[$j+$d] = $t;
		}
		$d = floor($d/2);
	}
	return $a;
}

选择排序

简单选择排序（Simple Selection Sort）

基本思想：在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。
第一趟，从n 个记录中找出关键码最小的记录与第一个记录交换；
第二趟，从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换；
以此类推…..
第i 趟，则从第i个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换，直到整个序列按关键码有序。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function selectSort($arr) {
	//双重循环完成，外层控制轮数，内层控制比较次数
	$len=count($arr);
    for($i=0; $i<$len-1; $i++) {
        //先假设最小的值的位置
        $p = $i;
        for($j=$i+1; $j<$len; $j++) {
            //$arr[$p] 是当前已知的最小值
            if($arr[$p] > $arr[$j]) {
				//比较，发现更小的,记录下最小值的位置；并且在下次比较时采用已知的最小值进行比较。
                $p = $j;
            }
        }
        //已经确定了当前的最小值的位置，保存到$p中。如果发现最小值的位置与当前假设的位置$i不同，
		//则位置互换即可。
        if($p != $i) {
            $tmp = $arr[$p];
            $arr[$p] = $arr[$i];
            $arr[$i] = $tmp;
        }
    }
    //返回最终结果
    return $arr;
}
二元选择排序(简单选择排序的改进)

简单选择排序，每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可。具体实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function improve_selectSort(&$arr, $n) {
	for($i=1; $i <= $n/2; $i++) {    
		// 做不超过n/2趟选择排序   
		$min = $i; 
		$max = $i ; //分别记录最大和最小关键字记录位置  
		for ($j= $i+1; $j<= $n-$i; $j++) {  
			if ($arr[$j] > $arr[$max]) {   
				$max = $j ; continue ;   
			}    
			if ($arr[$j]< $arr[$min]) {   
				$min = $j ;   
			}     
		}    
		//该交换操作还可分情况讨论以提高效率  
		$tmp = $arr[$i-1]; $arr[$i-1] = $arr[$min]; $arr[$min] = $tmp;  
		$tmp = $arr[$n-$i]; $arr[$n-$i] = $arr[$max]; $arr[$max] = $tmp;   
	}
}
堆排序（Heap Sort）

堆排序是一种树形选择排序，是对直接选择排序的有效改进

基本思想：堆的定义如下：具有n个元素的序列（k1,k2,…,kn),当且仅当满足
堆排序

时称之为堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最小项（小顶堆）。
若以一维数组存储一个堆，则堆对应一棵完全二叉树，且所有非叶结点的值均不大于(或不小于)其子女的值，根结点（堆顶元素）的值是最小(或最大)的。如：

a)大顶堆序列：(96, 83,27,38,11,09)
b)小顶堆序列：(12，36，24，85，47，30，53，91)
堆排序

初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树（一维数组存储二叉树），调整它们的存储序，使之成为一个堆，将堆顶元素输出，得到n
个元素中最小(或最大)的元素，这时堆的根节点的数最小（或者最大）。然后对前面(n-1)个元素重新调整使之成为堆，输出堆顶元素，得到n
个元素中次小(或次大)的元素。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。称这个过程为堆排序。

因此，实现堆排序需解决两个问题：

  1. 如何将n 个待排序的数建成堆；
  2. 输出堆顶元素后，怎样调整剩余n-1 个元素，使其成为一个新堆。

首先讨论第二个问题：输出堆顶元素后，对剩余n-1元素重新建成堆的调整过程。
调整小顶堆的方法：

1）设有m 个元素的堆，输出堆顶元素后，剩下m-1
个元素。将堆底元素送入堆顶（（最后一个元素与堆顶进行交换），堆被破坏，其原因仅是根结点不满足堆的性质。

2）将根结点与左、右子树中较小元素的进行交换。

3）若与左子树交换：如果左子树堆被破坏，即左子树的根结点不满足堆的性质，则重复方法 （2）.

4）若与右子树交换，如果右子树堆被破坏，即右子树的根结点不满足堆的性质。则重复方法 （2）.

5）继续对不满足堆性质的子树进行上述交换操作，直到叶子结点，堆被建成。

称这个自根结点到叶子结点的调整过程为筛选。如图：
堆排序

再讨论对n 个元素初始建堆的过程。
建堆方法：对初始序列建堆的过程，就是一个反复进行筛选的过程。

1）n 个结点的完全二叉树，则最后一个结点是第个结点的子树。

2）筛选从第个结点为根的子树开始，该子树成为堆。

3）之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。

如图建堆初始过程：无序序列：（49，38，65，97，76，13，27，49）
堆排序

算法的实现
从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。

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
/** 
 *   已知$arr[s…m]除了$arr[s] 外均满足堆的定义 
 *   调整$arr[s],使其成为大顶堆.即将对第s个结点为根的子树筛选,  
 *   
 *   @param $arr是待调整的堆数组 
 *   @param $s是待调整的数组元素的位置 
 *   @param $length是数组的长度 
 *  */  
function heapAdjust(&$arr, $s, $length)  
{  
	$tmp  = $arr[$s];  
	$child = 2*$s+1; //左孩子结点的位置。($i+1 为当前调整结点的右孩子结点的位置)  
	while ($child < $length) {  
		if($child+1 < $length && $arr[$child] < $arr[$child+1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)  
			++$child ;  
		}  
		if($arr[$s]<$arr[$child]) {  // 如果较大的子结点大于父结点  
			$arr[$s] = $arr[$child]; // 那么把较大的子结点往上移动，替换它的父结点  
			$s = $child;       // 重新设置$s ,即待调整的下一个结点的位置 $i 
			$child = 2*$s+1;  
		}  else {            // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出  
			break;  
		}  
		$arr[$s] = $tmp;         // 当前待调整的结点放到比其大的孩子结点位置上  
	}  
	echo implode(',', $arr).PHP_EOL;
}  

/** 
 *  * 初始堆进行调整 
 *   * 将$arr[0..length-1]建成堆 
 *    * 调整完之后第一个元素是序列的最小的元素 
 *     */  
function  buildingHeap( &$arr , $length)  
{   
	//最后一个有孩子的节点的位置 $i=  ($length -1) / 2  
	for ($i = ($length -1) / 2 ; $i >= 0; --$i)  
		heapAdjust($arr, $i, $length);  
}  
/** 
 * 堆排序算法 
 */  
function heapSort( &$arr, $length)  
{  
	//初始堆  
	buildingHeap($arr, $length);  
	//从最后一个元素开始对序列进行调整  
	for ($i = $length - 1; $i > 0; --$i)  
	{  
		//交换堆顶元素H[0]和堆中最后一个元素  
		$temp = $arr[$i]; $arr[$i] = $arr[0]; $arr[0] = $temp;  
		//每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整  
		heapAdjust($arr,0,$i);  
	}  
}

交换排序

冒泡排序（Bubble Sort）

基本思想：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。
冒泡排序的示例：
冒泡排序

算法的实现

1
2
3
4
5
6
7
8
9
10
11
12
function bubbleSort(&$arr, $n){  
	for($i =0 ; $i< $n-1; ++$i) {  
		for($j = 0; $j < $n-$i-1; ++$j) {  
			if($arr[$j] > $arr[$j+1])  
			{  
				$tmp = $arr[$j]; 
				$arr[$j] = $arr[$j+1] ;
				$arr[$j+1] = $tmp;  
			}  
		}  
	}  
}

冒泡排序算法的改进
对冒泡排序常见的改进方法是加入一标志性变量exchange，用于标志某一趟排序过程中是否有数据交换，如果进行某一趟排序时并没有进行数据交换，则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程。本文再提供以下两种改进算法：
1．设置一标志性变量$bFlag ,用于记录每趟排序中是否有位置交换，如果没有则直接结束外层循环，否则进行交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function bubbleSort($arr){//$arr(1...n)是待排序的文件，采用自下向上扫描，对$arr做冒泡排序
    $bFlag = true; //交换标志
    for($i=0; $i<count($arr); $i++){ //最多做n-1趟排序
        $bFlag = false; //本趟排序开始前，交换标志应为假
        for($j = count($arr)-2; $j >= $i; $j--){ //对当前无序区$arr[i..n]自下向上扫描
            if( $arr[$j+1] < $arr[$j] ){//交换记录
                $temp = $arr[$j+1]; //$temp不是哨兵，仅做暂存单元
                $arr[$j+1] = $arr[$j];
                $arr[$j] = $temp;
                $bFlag = true; //发生了交换，故将交换标志置为真
            }
        }
        if(!$bFlag){ //本趟排序未发生交换，提前终止算法
             break;
        }
    } //endfor(外循环)
    print_r($arr);
} //BubbleSort

2.传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者), 从而使排序趟数几乎减少了一半。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function bubble ( $arr, $n){  
	$low = 0;   
	$high = $n -1; //设置变量的初始值  
	while ($low < $high) {  
		for ($j = $low; $j< $high; ++$j) //正向冒泡,找到最大者  
			if ($arr[$j]> $arr[$j+1]) {  
				$tmp = $arr[$j]; 
				$arr[$j]=$arr[$j+1];
				$arr[$j+1]=$tmp;  
			}   
		--$high;                 //修改high值, 前移一位  
		for ( $j=$high; $j>$low; --$j) //反向冒泡,找到最小者  
			if ($arr[$j]<$arr[$j-1]) {  
				$tmp = $arr[$j]; 
				$arr[$j]=$arr[$j-1];
				$arr[$j-1]=$tmp;  
			}  
		++$low;                  //修改low值,后移一位  
	}   
	echo implode(',', $arr);
}

交换排序

快速排序（Quick Sort）

基本思想：
1）选择一个基准元素,通常选择第一个元素或者最后一个元素,
2）通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的
元素值比基准值大。
3）此时基准元素在其排好序后的正确位置
4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

快速排序的示例：
（a）一趟排序的过程：
first quick sort
（b）排序的全过程：
quick sort

算法的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function quick_sort($array) {
    if (count( $array ) <= 1) return $array;
    $key = $array [0];
    $left_arr = array ();
    $right_arr = array ();
    
    for($i = 1; $i < count( $array ); $i ++) {
        if ($array [$i] <= $key)
            $left_arr [] = $array [$i];
        else
            $right_arr [] = $array [$i];
    }
    $left_arr = quick_sort ( $left_arr );
    $right_arr = quick_sort ( $right_arr );
    return array_merge ( $left_arr, array ($key ), $right_arr );
}

附：相关资料
八大排序算法

轻轻的我走了，正如我轻轻的来