常见经典排序算法过程分析
文章简介
本文针对插入、选择、冒泡、归并、希尔和快速排序六大算法进行演示，主要分析算法过程的具体实现与实际demo，demo采用PHP编程语言实现。文末介绍算法过程分析工具。由于一篇公众号只能插入三个视频，因此快速排序和归并排序的视频，是通过回复关键字才可以查看(表示很无奈)。快速排序直接发送选择、归并直接发送归并。
插入排序
算法分析:在一组需要排序的数列中，假设前面的数据是已经排好序，将后面需要排序的数与前面已经排好序的数据从后往前依次进行比较，使其插入到排好序的序列中。按照此种方式依次循环。最终得到的就是排好序的数列。
算法步骤
- 从第一个元素开始，该元素可以认为已经被排序。
- 取出后面的一个数，在已经排序的元素序列中从后向前扫描。
- 如果发现前面的数据大于选择的数据，则前面的数据依次往后移动一位。
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
- 将新元素插入到该位置中。
- 此时再重复第2步，依次往复。
代码示例
function insertSort($arr) {
$len=count($arr);
if ($len < 2) {
return $arr;
}
for($i=1, $i<$len; $i++)
$tmp = $arr[$i];
for($j=$i-1;$j>=0;$j--) {
if($tmp < $arr[$j]) {
$arr[$j+1] = $arr[$j];
$arr[$j] = $tmp;
} else {
break;
}
}
}
return $arr;
}冒泡排序
算法分析:在一组需要排序的数列中,将前后相邻的一对数进行比较，如果发现两者数据大小不同，则相互交换位置，让大的数据往后移，直到第一轮对比完成，此时再重头开始按照相同的方式进行排序。
算法步骤
- 从第一个数开始与后面的一个数进行比较。发现两者大小不同则交换位置。
- 依次在从第三个数和第四个数进行比较，发现两者大小不同则交换位置，依次重复，直到第n-1个数和n进行完大小比较。
- 从头开始，重复第1中的步骤，然后接着执行第2中的步骤，循环往复。
代码示例
function bubbleSort($arr)
{
$len=count($arr);
if ($len < 2) {
return $arr;
}
for($i=1;$i<$len;$i++)
{
for($k=0;$k<$len-$i;$k++)
{
if($arr[$k]>$arr[$k+1])
{
$tmp=$arr[$k+1];
$arr[$k+1]=$arr[$k];
$arr[$k]=$tmp;
}
}
}
return $arr;
}快速排序
算法分析:在一组需要排序的数列中,选择一个基准元素，通常选择第一个元素或者最后一个元素。通过一趟扫描，将待排序列分成两部分，一部分比基准元素小，一部分大于等于基准元素。此时基准元素在其排好序后的正确位置，然后再用同样的方法递归地排序划分的两部分。
算法步骤
- 选择一个基数。
- 对基准元素之外的数据进行扫描，根据基准元素大小，扫描到大的数，归类到基准元素的右侧，扫描到小的元素，归类到基准元素的左侧。
- 此时，基准元素的位置就是一个正确的位置，同时形成了左右的两列数据。
- 根据同样的方法重复1中的操作，接着进行第2步操作。这样循环操作就形成了多个小的列，这样的列就是已经排好序的列，合并列即可。
代码示例
function quickSort($arr) {
$len = count($arr);
if ($len < 2) {
return $arr;
}
$base_num = $arr[0];
$left_array = array();
$right_array = array();
for($i=1; $i<$len; $i++) {
if($base_num > $arr[$i]) {
$left_array[] = $arr[$i];
} else {
$right_array[] = $arr[$i];
}
}
$left_array = quickSort($left_array);
$right_array = quickSort($right_array);
return array_merge($left_array, array($base_num), $right_array);
}选择排序
算法分析:在一组需要排序的数列中,选出数列中最小的数与第一个数进行交换位置，接着再从剩下的数中选择一个最小的数与第二个位置进行交换位置。依次往复，直到第n个数为止。
算法步骤
- 选择出数列中最小的那个数。
- 与第一个数交换位置。
- 接着从剩下的数列中找出最小的数。
- 与第二个数进行交换位置。
- 依次循环
代码示例
function selectSort($arr) {
$len=count($arr);
if ($len < 2) {
return $arr;
}
for($i=0; $i<$len-1; $i++) {
$p = $i;
for($j=$i+1; $j<$len; $j++) {
if($arr[$p] > $arr[$j]) {
$p = $j;
}
}
if($p != $i) {
$tmp = $arr[$p];
$arr[$p] = $arr[$i];
$arr[$i] = $tmp;
}
}
return $arr;
}归并排序
算法分析:在一组需要排序的数列中，将数列分为多个小的数列，先对小的数列进行排序，然后再合并这些已经排好序的小数列。
算法步骤
- 先对第一个数和第二个数进行比较。接着对第三个数和第四个数进行比较。
- 然后对这两对数据进行比较。
- 接着对第五个数和第六个数进行比较，同样的对后面的数进行比较。这样形成不同的区块数据。
- 再对小的区块数据进行比较。
代码示例
function merge_sort($arr)
{
$len = count($arr);
if ($len < 2) {
return $arr;
}
$left = merge_sort(array_slice($arr, 0, floor($len / 2)));
$right = merge_sort(array_slice($arr, floor($len / 2)));
$newArr = merge($left, $right);
return $newArr;
}
function merge($left, $right)
{
$arr = [];
$i = $j = 0;
while ($i < count($left) && $j < count($right)) {
if ($left[$i] < $right[$j]) {
$arr[] = $left[$i];
$i++;
} else {
$arr[] = $right[$j];
$j++;
}
}
$arr = array_merge($arr, array_slice($left, $i));
$arr = array_merge($arr, array_slice($right, $j));
return $arr;
}工具推荐
- https://algorithm-visualizer.org/
- 2.https://visualgo.net/en
几大算法的复杂度
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-12-03，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录