常见排序算法及PHP7.2实现



第一、冒泡排序(Bubble Sort)

冒泡排序 是一种交换排序,它的基本思想是:对待排序记录从后往前(逆序)进行 多遍扫描,当发现相邻两条记录的次序与排序要求的规则不符时,就将这两个记录 进行交换。这样,值较小的记录将逐渐从后面向前移动,就像气泡在水中向上浮一 样。

算法描述

假设需要排序的记录有 n 个,其值保存在数组 A 中,使用冒泡排序法,需对数组 A进行 n-1 次扫描,完成排序操作。具体过程如下:

1、将 A[n-1] A[n] 进行比较,A[n] < A[n-1] ,则交换两元系的位置。

2、修改数组下标,使需要比较的两个元素为 A[n-1] A[n-2] ,重复步骤(1),对这两个 元素进行比较。重复这个过程,直到对 A[1] A[0] 进行比较完为止。完成第 1 遍扫描。 经过第 1 遍扫描后,最小的元素已经像气泡一样到最上面,即位于元素 A[0] 中了。

3、接下来重复前面的步骤,进行第 2 遍扫描,只是扫描结束位置到 A[2] A[1] 进行比较 完为止(因为 A[0]中已经是最小的数据,不用再进行比较)。

4、通过 n-1 遍扫描,前 n-1 个数都已经排序完成,最后一个元素 A[n] 肯定就是最大的 数了。至此,完成排序操作。

/**
* 冒泡排序
* @param array $arr
*/
function bubbleSort(array &$arr) : void{
    $length = count($arr);
    // 外层循环,从数组首部开始,每完成一次循环,可确定 $arr[$i] 位置的元素
    for ($i = 0; $i < $length; $i++){ // 内层循环,$j 从后往前循环
        for ($j = $length - 1; $j > $i; $j--) {
            // 若前面的值大于后面的值,则互换位置
            if ($arr[$j] < $arr[$j - 1]) {
            // 互换数组两个位置的值
            [$arr[$j], $arr[$j - 1]] = [$arr[$j - 1], $arr[$j]];
            } 
        }
    } 
}



第二、选择排序(Selection Sort)

选择排序是通过 n-i 次关键字间的比较,从 n-i+1 个记录中选出关键字最小的记 录,并和第 i ( 1 <= i <= n ) 个记录交换。

算法描述

1. 维护数组中最小的前 n 个元素的已排序序列。

2. 每次从剩余未排序的元素中选取最小的元素,将其放在已排序序列的后面,作为序列

的第 n+1 个记元素。

3. 以空序列作为排序工作的开始,直到未排序的序列里只剩一个元素时(它必然为最大),

只需直接将其放在已排序的记录之后,整个排序就完成了。

/**
* 选择排序
* @param array $arr
*/
function selectionSort(array &$arr) : void{
	$length = count($arr);
	// 外层循环,从数组首部开始,每完成一次循环,可确定一个元素的位置
	for ($i = 0; $i < $length - 1; $i++) {
		// 选定的最小值的索引
		$minIdx = $i;
		// 从 $i + 1 位开始循环,判断当前选定的元素是否是当次循环的最小值 
		for ($j = $i + 1; $j < $length; $j++) {
		// 若出现比选定的值还小的值,则替换最小值的索引
			if($arr[$minInx]> $arr[$j]) {
				$minInx=$j;
			} 
		}
		// 互换数组两个位置的值
		[$arr[$i], $arr[$minIdx]] = [$arr[$minIdx], $arr[$i]]; 
	}
}
/**
* 选择排序 - 方法2
* @param array $arr
*/
function selectionSort2(array &$arr) : void{
	$length = count($arr);
	// 外层循环,从数组首部开始,每完成一次循环,依次确定数组元素的位置
	for ($i = 0; $i < $length; $i++) {
		// 从 $i + 1 位开始循环,依次判定 $arr[$i] 与 $arr[$j] 的大小 
		for ($j = $i + 1; $j < $length; $j++) {
			// 若 $arr[$i] 比 $arr[$j] 大,则互换两个元素的位置
			if ($arr[$i] > $arr[$j]) {
				// 互换数组两个位置的值
				[$arr[$j], $arr[$i]] = [$arr[$i], $arr[$j]];
			} 
		}
	} 
}


第三、插入排序(Insertion Sort)

插入排序 是通过构建有序序列,从未排序数据中选择一个元素,在已排序序列中从 后向前扫描,找到相应位置并插入。插入排序在从后向前扫描过程中,需要把已排 序元素逐个向后移动,为最新元素提供插入空间。


算法描述

1、对于第 1 个元素,因为没有比较,将其作为已经有序的序列。 

2、从数组中获取下一个元素,在已经排序的元素序列中从后向前扫描,并进行判断。 

3、若排序序列的元素大于新元素,则将该元素向后移动一位。 重复步骤(3),直到在已排序的元素中找到小于或者等于新元素的元素,将新元素插入

4、重复步骤(2) ~ (4),直到完成排序。

/**
* 插入排序
* @param array $arr
*/
function insertionSort(array &$arr) : void{
	$length = count($arr);
	// 从数组首部开始排序,每完成一次循环,可确定一个元素的位置
	for ($i = 0; $i < $length - 1; $i++) {
		// 内层循环从 $i + 1 个元素开始,一位一位向前比较
		// 若前面的值比自己大,则替换,直到前面的值比自己小了,停止循环 
		for ($j = $i + 1; $j > 0; $j--) {
			if ($arr[$j] >= $arr[$j - 1]) { 
				break;
			}
			[[$arr[$j], $arr[$j - 1]]] = [[$arr[$j - 1], $arr[$j]]]; 
		}
	} 
}



/**
* 插入排序 - 方法2
* @param array $arr
*/
function insertionSort2(array &$arr) : void{
	$length = count($arr);
	// 从数组首部开始排序,每完成一次循环,可确定一个元素的位置
	for ($i = 0; $i < $length - 1; $i++) {
		// 从第二个元素开始,选择固定位置的值作为基准值 
		$currentVal = $arr[$i + 1];
		// 初始键位于选定值的前一个位置
		$preIdx = $i;
		while($preIdx>=0 && $currentVal<$arr[$preIdx]){
			$arr[$preIdx+1]=$arr[$preIdx];
			$arr[$preIdx]=$currentVal;
			$preIdx--;
		}
	 }
}


第四、快速排序(Quick Sort)

快速排序是通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键 字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到 整个序列有序的目的。

算法描述 快速排序使用分治策略来把待排序数据序列分为两个子序列,具体步骤如下:

1. 从数列中挑出一个元素,以该元素为“基准”。

2. 扫描一遍数列,将所有比“基准”小的元素排在基准前面,所有比“基准”大的元素排在基

准后面。

3. 通过递归,将各子序列划分为更小的序列,直到把小于基准值元素的子数列和大于基

谁值元素的子数列排序。

* 快速排序
* @param $arr
*/
function quickSort(& $arr) : void{
	$length = count($arr);
	// 若数组为空,则不需要运行
	if ($length <= 1) { 
		return;
	}
	$middle = $arr[0]; // 选定一个中间值
	$left = []; // 接收小于中间值 
	$right = [];// 接收大于中间值
	// 循环比较
	for ($i = 1; $i < $length; $i++) {
		if ($middle < $arr[$i]) { // 大于中间值
			$right[] = $arr[$i]; 
		} else {
			// 小于或等于中间值
			$left[] = $arr[$i]; 
		}
	}
	// 递归排序划分好的左右两边
	quickSort($left);
 	quickSort($right);
	$arr = array_merge($left, [$middle], $right); 
}


第五、归并排序(Merge Sort)

算法描述

归并是一种典型的序列操作,其工作是把两个或更多有序序列合并为一个有序序列。 基于归并的思想也可以实现排序,称为归并排序。基本方法如下:

quickSort($left);

quickSort($right);

 

每天进步一点点,让优秀成为习惯!--六星教育

1. 初始时,把待排序序列中的 n 个元素看成 n 个有序子序列(因为只有 1 个元素的序 列总是排好序的),每个子序列的长度均为 1。

2. 把序列组里的有序子序列两两归并,每完成一论归并,序列组里的序列个数减半,每 个子序列的长度加倍。

3. 对加长的有序子序列重复上面的操作,最终得到一个长度为 n 的有序序列。 这种归并方法也称为简单的二路归并排序,其中每次操作都是把两个有序序列合并

为一个有序序列。也可考虑三路归并或更多路的归并。



本文永久地址:http://www.huanghaiping.com/article/91.html
本文出自 黄海平博客 ,转载时请注明出处及相应链接。

发表我的评论
  

网友最新评论 (0)

暂无评论
返回顶部