数据结构和算法--常见排序

数据结构和算法--常见排序

排序算法

在选择排序算法的时候,通常会根据以下几个维度来考虑

时间复杂度
空间复杂度(对内存空间的消耗)
算法的稳定性(如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变)

冒泡排序(只会操作相邻的两个数据)

冒泡排序只会操作相邻的两个数据。

每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求,如果不满足就让它俩互换。由于在排序过程中总是小数往前放,大数往后放,相当于气泡往上升,所以称作冒泡排序。

但其实在实际过程中也可以根据自己需要反过来用,大树往前放,小数往后放。

$numbers = [4, 5, 6, 3, 2, 1];
$cnt = count($numbers);
for ($i = 0; $i < $cnt; $i++) {
for ($j = 0; $j < $cnt - $i - 1; $j++) {
if ($numbers[$j] > $numbers[$j + 1]) {
$temp = $numbers[$j];
$numbers[$j] = $numbers[$j + 1];
$numbers[$j + 1] = $temp;
}
}
}
var_dump($numbers);

冒泡排序的性能和稳定性

时间复杂度: O(n^2) (n的平方)
空间复杂度:只涉及相邻元素的交换,是原地排序算法
算法稳定性:元素相等不会交换,是稳定的排序算法

总结:时间复杂度是 O(n^2),看起来性能并不是很好,所以我们在实践中基本不会选用冒泡算法。

插入排序

将数组中的数据分为两个区间,已排序区间和未排序区间。

初始已排序区间只有一个元素,就是数组的第一个元素。

插入算法的核心思想是取未排序区间中的元素,在已排序区间中找到合适的插入位置将其插入,并保证已排序区间数据一直有序。重复这个过程,直到未排序区间中元素为空,算法结束。

其实就是:将插入的数据保存在变量中,与数组中的每个数比较 找到合适的位置 进行插入

$nums = [4, 5, 6, 3, 2, 1];

for ($i = 0; $i < count($nums); $i++) {

$value = $nums[$i]; //在这里把值赋值给一个变量

$j = $i - 1;
for (;$j >= 0; $j--) {

if ($nums[$j] > $value) {
#通过这些注释掉的代码,可以知道运行原理.
#echo '<pre>';
#var_dump($nums[$j+1],$nums[$j]);
#echo '<pre>';
$nums[$j+1] = $nums[$j];
#echo '<pre>';
#var_dump($nums);
#echo '<pre>';
} else {
break;
}
}
$nums[$j+1] = $value;
}

var_dump($nums);

插入排序的性能和稳定性

时间复杂度: O(n^2) (n的平方)

空间复杂度:只涉及相邻元素的交换,是原地排序算法

算法稳定性:元素相等不会交换,是稳定的排序算法

插入排序的时间复杂度和冒泡排序一样,也不是很理想,但是插入排序不涉及数据交换,从更细粒度来区分,性能要略优于冒泡排序。

选择排序

选择排序主要是将假设数组中的第一个是最小的,循环与数组中的第一个进行比较 如果比其还小 则记录下标 进行数值交换 效率相对冒泡来说比较高

function selection_sort($nums)
{
if (count($nums) <= 1) {
return $nums;
}

for ($i = 0; $i < count($nums); $i++) {
$min= $i;
for ($j = $i + 1; $j < count($nums); $j++) {
if ($nums[$j] < $nums[$min]) {
$min = $j;
}
}
if ($min != $i) {
$temp = $nums[$i];
$nums[$i] = $nums[$min];
$nums[$min] = $temp;
}
}

return $nums;
}

$nums = [4, 5, 6, 3, 2, 1];
$nums = selection_sort($nums);
print_r($nums);

插入排序的性能和稳定性

选择排序的时间复杂度也是 O(n^2);
由于不涉及额外的存储空间,所以是原地排序;
由于涉及非相邻元素的位置交换,所以是不稳定的排序算法。

总结

综合比较上面介绍的三个排序算法,时间复杂度都是一样的,也都是原地排序,但是选择排序是不稳定的排序算法,此外,插入排序和冒泡排序相比较,插入排序只需要一条语句,而冒泡排序需要三条,在同等条件下,或者数据量很大的情况下,插入排序性能是要优于冒泡排序的.

所以综合比较下来,三者的优先级是 插入排序 > 冒泡排序 >> 选择排序。
但是三者的时间复杂度都是 O(n^2),数据量很大的情况下性能表现并不是很理想.(还有两种好于插入排序)

归并排序

要排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了.

undefined

$nums = [4, 5, 6, 3, 2, 1];
function merge_sort($nums)
{
if (count($nums) <= 1) {
return $nums;
}

merge_sort_c($nums, 0, count($nums) - 1);
return $nums;
}

function merge_sort_c(&$nums, $p, $r)
{
if ($p >= $r) {
return;
}

$q = floor(($p + $r) / 2);
merge_sort_c($nums, $p, $q);
merge_sort_c($nums, $q + 1, $r);

merge($nums, ['start' => $p, 'end' => $q], ['start' => $q + 1, 'end' => $r]);
}
function merge(&$nums, $nums_p, $nums_q)
{
$temp = [];
$i = $nums_p['start'];
$j = $nums_q['start'];
$k = 0;
while ($i <= $nums_p['end'] && $j <= $nums_q['end']) {
if ($nums[$i] <= $nums[$j]) {
$temp[$k++] = $nums[$i++];
} else {
$temp[$k++] = $nums[$j++];
}
}

if ($i <= $nums_p['end']) {
for (; $i <= $nums_p['end']; $i++) {
$temp[$k++] = $nums[$i];
}
}

if ($j <= $nums_q['end']) {
for (; $j <= $nums_q['end']; $j++) {
$temp[$k++] = $nums[$j];
}
}

for ($x = 0; $x < $k; $x++) {
$nums[$nums_p['start'] + $x] = $temp[$x];
}
}


$nums = [4, 5, 6, 3, 2, 1];
$nums = merge_sort($nums);
print_r($nums);

归并排序的性能和稳定性

归并排序不涉及相等元素位置交换,是稳定的排序算法.
时间复杂度是 O(nlogn).
需要额外的空间存放排序数据,不是原地排序.
最多需要和待排序数组同样大小的空间,所以空间复杂度是 O(n)。

快速排序(快排)

如果要排序数组中下标从 p 到 r 之间的一组数据,我们选择 p 到 r 之间的任意一个数据作为 pivot(分区点)。

我们遍历 p 到 r 之间的数据,将小于 pivot 的放到左边,将大于 pivot 的放到右边,将 pivot 放到中间。经过这一步骤之后,数组 p 到 r 之间的数据就被分成了三个部分,前面 p 到 q-1 之间都是小于 pivot 的,中间是 pivot,后面的 q+1 到 r 之间是大于 pivot 的。

undefined

首先要找到分区点 pivot,一般是取第一个或最后一个称为基准,然后就是比基准小的在左边,比基准大的放到右边,如何放做,就是和基准进行交换,这样交换完左边都是比基准小的,右边都是比较基准大的,这样就将一个数组分成了两个子数组,然后再按照同样的方法把子数组再分成更小的子数组,直到不能分解为止。
function quick_sort($nums)
{
if (count($nums) <= 1) {
return $nums;
}

quick_sort_c($nums, 0, count($nums) - 1);
return $nums;
}

function quick_sort_c(&$nums, $p, $r)
{
if ($p >= $r) {
return;
}

$q = partition($nums, $p, $r);
quick_sort_c($nums, $p, $q - 1);
quick_sort_c($nums, $q + 1, $r);
}
function partition(&$nums, $p, $r)
{
$pivot = $nums[$r];
$i = $p;
for ($j = $p; $j < $r; $j++) {
// 原理:将比$pivot小的数丢到[$p...$i-1]中,剩下的[$i..$j]区间都是比$pivot大的
if ($nums[$j] < $pivot) {
$temp = $nums[$i];
$nums[$i] = $nums[$j];
$nums[$j] = $temp;
$i++;
}
}

// 最后将 $pivot 放到中间,并返回 $i
$temp = $nums[$i];
$nums[$i] = $pivot;
$nums[$r] = $temp;

return $i;
}

$a = array(2,13,42,34,56,23,67,365,87665,54,68,3);
var_dump(quick_sort($a));

快速排序的性能和稳定性

时间复杂度是 O(nlogn).
快速排序因为涉及到数据的交换,有可能破坏原来相等元素的位置排序,所以是不稳定的排序算法.
尽管如此,现在各种语言中自带的排序库很多使用的都是快速排序.

还有其他常见排序算法

undefined