您现在的位置是：技术博客 > PHPPHP

常见的排序算法

Lucas2019-12-15 13:16【代码】623人已围观

简介php的相关排序算法

#### 一、冒泡排序

1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2、对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3、针对所有的元素重复以上的步骤，除了最后一个。
4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
```
/**
 * 冒泡排序
 * 数据结构----------------数组
 * 最差时间复杂度-----------O(n^2)
 * 最优时间复杂度-----------O(n)
 * 平均时间复杂度-----------O(n^2)
 * 空间复杂度---------------O(1)
 * 稳定性------------------稳定
 */
 
$arr = [1, 3, 34, 2, 32, 2, 78, -43, 53, -35, 0];
 
function BubbleSort($arr)
{
	$length = count($arr);
	for ($i = 0; $i < $length - 1; $i++) { 			// 每次最大元素移到数组最后
		for ($j = 0; $j < $length - 1 - $i; $j++) {     // 内部循环次数=数组长度-已经排序好的个数-1
			if ($arr[$j] > $arr[$j + 1]) {	        // 比较相邻两个元素，较大的后移
				$t = $arr[$j];
				$arr[$j] = $arr[$j + 1];
				$arr[$j + 1] = $t; 
			}
		}
	}
	return $arr;
}
print_r(BubbleSort($arr));
```

#### 二、插入排序
1、从第一个元素开始，该元素可以认为已经被排序。
2、取出下一个元素，在已经排序的元素序列中从后向前扫描。
3、如果该元素（已排序）大于新元素，将该元素移到下一位置。
4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
5、将新元素插入到该位置后。
6、重复步骤2~5。
```
/**
 * 直接插入排序
 * 数据结构----------------数组
 * 最差时间复杂度-----------O(n^2)：输入序列是降序排列的
 * 最优时间复杂度-----------O(n)：输入序列是升序排列的
 * 平均时间复杂度-----------O(n^2)
 * 空间复杂度--------------O(1)
 * 稳定性-----------------稳定
 */
 
$arr = [1, 3, 34, 2, 32, 2, 78, -43, 53, -35, 0];
 
function StraightInsertionSort($arr)
{						     // 数组第一个元素默认已被排序
	for ($i = 1; $i < count($arr); $i++) {	      // 未排序序列从数组第二个元素开始
		$get = $arr[$i];		       // 获取未排列序列第一个元素为要比较的元素
		$j = $i - 1;				// 指针指向已排序序列最后一个元素
		while ($j >= 0 && $arr[$j] > $get) {  // 当指针指向的元素比要比较的元素大
			$arr[$j + 1] = $arr[$j];	// 则将指针指向的元素向后移动一位
			$j--;				// 指针前移
		}
		$arr[$j + 1] = $get;			// 直到指针指向的元素与要比较元素小或者相等，则要比较元素插入到指针指向元素后
	}
	return $arr;
}

print_r(StraightInsertionSort($arr));
```

#### 三、二分查找排序
原理：首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
```
/**
 * 二分查找排序
 * 数据结构----------------数组
 * 最差时间复杂度-----------O(n^2)
 * 最优时间复杂度-----------O(nlogn)
 * 平均时间复杂度-----------O(n^2)
 * 空间复杂度--------------O(1)
 * 稳定性-----------------稳定
 */
 
$arr = [1, 3, 34, 2, 32, 2, 78, -43, 53, -35, 0];
 
function BinarySearchSort($arr)
{							    // 数组第一个元素默认已被排序
	for ($i = 1; $i < count($arr); $i++) {		        // 未排列序列从数组第二个元素开始
		$get = $arr[$i];			       // 获取未排列序列第一个元素为要比较元素
		$left = 0;				     // 定义已排列序列左边界
		$right = $i -1;					// 右边界
		while ($left <= $right) {					
			$mid = floor(($left + $right) / 2);	// 定义中间数，将已排列序列一分为二
			if ($arr[$mid] > $get) {		// 如果中间数大于比较元素，则比较元素属于前半段
				$right = $mid -1;		// 右边界左移
			} else {				// 否则比较元素属于后半段
				$left = $mid + 1;		// 左边界右移
			}
		}
		for ($j = $i -1; $j >= $left; $j--) {	       // 最后的$left就是待插入位置
			$arr[$j + 1] = $arr[$j];		// 将待插入位置的右边整体向右移动一个单位
		}		
		$arr[$left] = $get;				// 将比较元素插入该空位
	}
	return $arr;
}
 
print_r(BinarySearchSort($arr));
```

#### 四、希尔排序

希尔排序，也叫递减增量排序，是插入排序的一种更高效的改进版本。希尔排序是不稳定的排序算法。

原理：希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。

增量序列：由Knuth提出，递归表达式为：h = 3 * h + 1；减小增量：h = (h - 1) / 3；此公式产生的逆置序列为：..., 314, 121, 40, 13, 4, 1。
```
/**
 * 希尔排序
 * 数据结构----------------数组
 * 最差时间复杂度-----------O(n^2)
 * 最优时间复杂度-----------O(n^1.3)
 * 平均时间复杂度-----------O(nlogn)
 * 空间复杂度--------------O(1)
 * 稳定性-----------------不稳定
 */
 
$arr = [1, 3, 34, 2, 32, 2, 78, -43, 53, -35, 0];
 
function ShellSort($arr)
{												
	$length = count($arr);
	$h = 0;							
	while ($h <= $length) {					// 定义增量序列
		$h = 3 * $h + 1;
	}
	while ($h >= 1) {
		for ($i = $h; $i < $length; $i++) {			
			$j = $i - $h;
			$get = $arr[$i];			// 暂存要比较的元素
			while ($j >= 0 && $arr[$j] > $get) {	// 组内判断，若组内元素大于该元素
				$arr[$j + $h] = $arr[$j];	// 则两者位置互换
				$j = $j - $h;			// 指针继续向前移动增量的距离，继续比较
			}
			$arr[$j + $h] = $get;
		}
		$h = ($h - 1) / 3;				// 递减增量
	}
	return $arr;
}
 
print_r(ShellSort($arr));
```

很赞哦！ ( 0 )

上一篇：PHPExcel导出遇到的编码坑

下一篇：POSTMAN模拟登录