排序学习笔记(未完待续)

杂记 2017-09-10 1,497

概述

排序的方法有偶很多种,因此就多了对比。对排序的对比可以从时间复杂度空间复杂度来对比,还可以从稳定性和不稳定性来对比。

排序对比(引用维基

排序算法图.png

排序代码实现

1、冒泡排序
  • 原理:

    • 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
    • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
    • 针对所有的元素重复以上的步骤,除了最后一个。
    • 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
- **php代码实现**
$arr = array(101 , 22 , 435 ,99 , 30 , 90 , 31 , 66);
// 冒泡排序
function bubble_sort (&$arr)
{
    for ($i=0; $i <count($arr) ; $i++) {
        for ($j=0; $j < count($arr)-1; $j++) {
            if ($arr[$j] > $arr[$j+1] ) {
                list($arr[$j],$arr[$j+1]) = [$arr[$j+1],$arr[$j]];
            }
        }
    }
}
bubble_sort($arr);
print_r($arr);
2、选择排序
  • 原理
    首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
  • 代码
$arr = array(101 , 22 , 435 ,99 , 30 , 90 , 31 , 66);

//插入排序
function selection_sort(&$arr)
{
    for ($i = 0; $i < count($arr); $i++)
    {
        $min = $i;
        for ($j = $i+1 ; $j < count($arr); $j++){
            if ($arr[$j] <= $arr[$min]) {
               $min = $j;
        }
        }
        list($arr[$i] ,$arr[$min]) = [$arr[$min],$arr[$i]];
    }
}

selection_sort($arr);

print_r($arr);
3、插入排序
  • 原理
    它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入

    1. 从第一个元素开始,该元素可以认为已经被排序
    2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
    3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
    4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
    5. 将新元素插入到该位置后
    6. 重复步骤2~5
  • 代码

$arr = array(101 , 22 , 435 ,99 , 30 , 90 , 31 , 66);

//插入排序
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;
    }
}

 insertion_sort($arr);

 print_r($arr);
4、堆排序

堆排序Heap sort

要理解堆排序,首先要理解什么是堆。其次什么是最大堆。

堆排序的堆指的是2叉堆,指得不是堆栈的那个堆,而是一种数据结构。

堆可以视为一棵完全的二叉树,完全二叉树的一个“优秀”的性质是,除了最底层之外,每一层都是满的,这使得堆可以利用数组来表示,每一个结点对应数组中的一个元素.

二叉堆有两种 最大堆最小堆
最大堆
堆中每个父节点的元素值都大于等于其孩子结点(如果存在),这样的堆就是一个最大堆

因此,最大堆中的最大元素值出现在根结点(堆顶)
最小堆
堆中每个父节点的元素值都小于等于其孩子结点(如果存在),这样的堆就是一个最小堆

因此,最小堆中的最小元素值出现在根结点(堆顶)

原理
堆排序就是把最大堆堆顶的最大数取出,将剩余的堆继续调整为最大堆,再次将堆顶的最大数取出,这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作:

  1. 最大堆调整(Max-Heapify):将堆的末端子节点作调整,使得子节点永远小于父节点
  2. 创建最大堆(Build-Max-Heap):将堆所有数据重新排序,使其成为最大堆
  3. 堆排序(Heap-Sort):移除位在第一个数据的根节点,并做最大堆调整的递归运算

代码

5、归并排序
  • 原理

    原理如下(假设序列共有n个元素):

    1. 将序列每相邻两个数字进行归并操作,形成 floor(n/2)个序列,排序后每个序列包含两个元素
    2. 将上述序列再次归并,形成 floor(n/4)个序列,每个序列包含四个元素
    3. 重复步骤2,直到所有元素排序完毕
  • 代码

    // 递归的法
    function merge_sort($arr) {

      $len = count($arr);
      if ($len <= 1) {
          return $arr;
      }
      $half = ($len>>1) + ($len&1);
    
      $arr_split = array_chunk($arr, $half);
      $left = merge_sort($arr_split[0]);
      $right = merge_sort($arr_split[1]);
    
      while ($left && $right) {
          if ($left[0] < $right[0]) {
              $reg[] = array_unshift($left);
          }
          else
          {
              $reg[] = array_unshift($right);
          }
      }
    
      return array_merge($reg , $left , $right);
    

    }
    $arr = array(101 , 22 , 435 ,99 , 30 , 90 , 31 , 66);
    print_r(merge_sort($arr));

6、快速排序
递归快速排序
  • 原理
    快速排序(Quicksort)是一种不稳定的排序,通常简单的理解,我认为快速排序就是将要排序的数列取出一个作为标准,然后将数列分为两部分,大的在一边,小的在一边。然后被分好的两个大小数列在作为要排序的数列,不断重复前面的操作。

    1. 从数列中挑出一个元素,称为"基准"(pivot),
    2. 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任何一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
    3. 递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。
  • 代码

function quick($arr) {

    $len = count($arr);

    $left = $right = [];

    if ($len <=1) {
        return $arr;
    }

    $basic = $arr[0];

    for ($i=1; $i < $len ; $i++) { 
        if ($arr[$i] < $basic) {
            $left[] = $arr[$i];
        }
        else
        {
                $right[] = $arr[$i];
            }
    }

    return array_merge(quick($left) , [$basic] ,  quick($right));
}
原地快速排序

上面我们我们实现了快速排序,这是一种常见的快速排序方式。还有一种实现方式,也就是原地(in-place)快速排序,原地算法是一种使用小的,固定数量的额外之空间来转换数据的算法。
和前面的算法相比,将使用更少的内存空间。

  • 代码
//分组函数
function partition (&$arr , $left ,$right) {

    // 分组参照值
    $part = $arr[$left];

    // 用来存放小于$part值得 存储位置索引 
    $storeIndex = $left+1;

    for ($i=$storeIndex; $i <= $right; $i++) { 
            // 循环当中,如果当前值,小于参照值, 那么把把 当前值存放到用来存放小于参照值得位置处
        // 也就是说 我们要将 当前值和$arr[$stroeIndex]进行交换
        if ($arr[$i] < $part) {
            list($arr[$i] , $arr[$storeIndex]) = [$arr[$storeIndex] , $arr[$i]];
        $storeIndex++;
        }
    }

    // 将参照值和索引-1处的值进行交换,
    list($arr[$left] , $arr[$storeIndex-1]) = [$arr[$storeIndex-1] , $arr[$left]];
    // 返回参照值得索引
    return $storeIndex-1;
}

// 原地快速排序函数
function quick_sort (&$arr , $left ,$right) {

    // 如果起始索引位置大于结束索引位置,结束调用
    if ($left > $right) {
            return false;
    }

    // partition函数的返回值$storeIndex ,是数组$arr被分组后的分组值位置索引,
    // 索引小于$storeIndex的数组值小于$arr[$storeIndex] 
    // 索引大于$storeIndex的数组值大于$arr[$storeIndex] 
    $storeIndex = partition($arr , $left , $right);

    // 对小于$arr[$storeIndex]的值,再次调用quick_sort进行分组
    quick_sort($arr , $left ,$storeIndex-1);

    // 对大于$arr[$storeIndex]的值,再次调用quick_sort进行分组
    quick_sort($arr ,$storeIndex+1 , $right);

}
7、希尔排序
  • 说明
    希尔排序算法是按其设计者希尔(Donald Shell)的名字命名,该算法由1959年公布,是插入排序的一种更高效的改进版本。它的作法不是每次一个元素挨一个元素的比较。而是初期选用大跨步(增量较大)间隔比较,使记录跳跃式接近它的排序位置;然后增量缩小;最后增量为 1 ,这样记录移动次数大大减少,提高了排序效率。希尔排序对增量序列的选择没有严格规定。

希尔排序是基于插入排序的以下两点性质而提出改进方法的:

  • 插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率
  • 但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位
  • 原理
  1. 先取一个正整数 d1(d1 < n),把全部记录分成 d1 个组,所有距离为 d1 的倍数的记录看成一组,然后在各组内进行插入排序
  2. 然后取 d2(d2 < d1)
  3. 重复上述分组和排序操作;直到取 di = 1(i >= 1) 位置,即所有记录成为一个组,最后对这个组进行插入排序。一般选 d1 约为 n/2,d2 为 d1 /2, d3 为 d2/2 ,…, di = 1。
  • 代码

    // 希尔排序
    function shell_sort (&$arr)
    {
    //获取数组长度
    $step = count($arr);

      while ( $step >= 1) {
          //取步长
          $step = floor($step/2);
    
          //按照步长分组
          for ($i=$step; $i < count($arr); $i++) { 
          
              $temp = $arr[$i];
              for ($j=$i-$step; $j >=0 && $temp < $arr[$j]; $j =$j-$step) { 
                  $arr[$j+$step] = $arr[$j];
              }
    
              $arr[$j+$step] = $temp;
          }       
      }
    

    }

8、计数排序
9、桶排序

我这里没有做详细的说明,关于桶排序,
基础请看:
最快最简单的排序算法:桶排序
进一步了解:
维基桶排序
常见排序算法 - 桶排序 (Bucket Sort)

  • 原理
    桶排序(Bucket sort)或所谓的箱排序的工作原理,是将数组分到有限数量的桶里。每个桶再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。最后将每个桶的数据合并起来。

  • 代码

    //假设排序值的范围0-1000
    function bucket_sort($arr)
    {
    $bucket_arr = [];

      // 桶的范围是0-9,10-19,20-29 ...... 990-999,1000
      foreach ($arr as $v) {
              $key = floor($v/10);
              $bucket[$key][] = $v;
      }
    
          // 对每个桶单独做排序 , 最后将数据合并
      for ($i=0 ; $i<= 100 ;$i++) {
          if (!isset($bucket[$i])) {
              continue;
          }
          quick_sort($bucket[$i] , 0 , count($bucket[$i])-1);
          foreach ($bucket[$i] as $v) {
              $bucket_arr[] = $v;
          }
      }
    
      return $bucket_arr;
    

    }

10、基数排序

本文由 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。

还不快抢沙发

添加新评论