关于程序员:工作多年之后回顾经典排序算法

原文链接

排序都要做的事件是比拟和替换

稳固排序：排序前后，两个相等的元素在其序列中的前后地位程序雷同

这里只有插入排序和归并排序是稳固排序

以下示例均假如咱们要从小到大进行排序

非稳固排序

排序效率和输出无关

抉择排序的根本步骤：先找出最小元素放到 0 号地位，再找出次小元素放到 1 号地位，再找出次次小元素放到 2 号地位，以此类推

#ifndef __SELECTIONSORT_H__
#define __SELECTIONSORT_H__

class Selection
{
public:
    // 抉择排序
  void Sort(char *a, int length)
  {for (int index = 0; index < length - 1; ++index)
    {
      // 找出从以后地位 index 开始到前面所有元素中最小元素的下标
      int indexOfCurMin = index;
      for (int i = index + 1; i < length; ++i)
      {if (a[i] < a[indexOfCurMin])
        indexOfCurMin = i;
      }

      // 将找到的最小元素和 index 地位上的元素进行替换
      int temp = a[index];
      a[index] = a[indexOfCurMin];
      a[indexOfCurMin] = temp;
    }
  }
};

#endif

该算法的长处是对输出数据的挪动次数起码。毛病是运行效率低，无奈解决大规模的数据

应用该算法对 n 个元素进行排序时

工夫复杂度为 O(n^2)，须要对元素进行 n(n-1)/ 2 次比拟以及 n - 1 次替换。值得注意的是，元素替换次数与元素个数成线性关系，这是其它排序算法都没有的

空间复杂度为 0

稳固排序

排序效率和输出无关，当待排序的元素越有序（倒置很少）时，该算法可能比其它任何算法都要快

插入排序的根本步骤：每一次都将一个未排序的元素插入到曾经排好序的数组中

#ifndef __INSERTIONSOER_H__
#define __INSERTIONSOER_H__

// 插入排序
class Insertion
{
public:
  void Sort1_0(char *a, int length)
  {for (int index = 1; index < length; ++index)
    {for (int i = index; i > 0; --i)
      {if (a[i] < a[i - 1])
        {char temp = a[i];
          a[i] = a[i - 1];
          a[i - 1] = temp;
        }
        //else
        //  break;
      }
    }
  }
  
  // 优化版本
  void Sort2_0(char *a, int length)
  {for (int index = 1; index < length; ++index)
    {char needToInsert = a[index];
    
      int i;
      for (i = index - 1; i >= 0 && needToInsert < a[i]; --i)
        a[i + 1] = a[i];  // 右移
    
      a[i + 1] = needToInsert;
    }
  }
};

#endif

这里须要补充两个概念

倒置：两个待排序元素的排列程序与指标程序相同

局部有序：如果元素倒置的数量小于元素个数的某个倍数时，那么就说这些待排序元素是局部有序的

该算法毛病是运行效率低，无奈解决大规模的数据

插入排序和冒泡排序很像，冒泡排序的算法如下：从未排序元素的第一对直到最初一对，如果第一个元素比第二个元素大就替换，反复这个步骤直到所有元素都排序实现

应用该算法对 n 个元素进行排序时

工夫复杂度在最坏的状况下为 O(n^2)，最好的状况为 O(n)，所以均匀为 O(n^2)。元素间的比拟次数大于等于倒置数，小于等于倒置数 + 数组大小 -1，在最坏的状况下为 n(n-1)/ 2 次，最好的状况下为 n - 1 次。元素间进行替换的次数等于倒置数，在最坏的状况下为 n(n-1)/ 2 次，最好的状况下为 0 次

空间复杂度为 0

非稳固排序

排序效率是否输出无关取决于第二步应用的排序算法是否输出无关

希尔排序的根本步骤：

确定 h 的初值
每次循环都使数组中任意距离为 h 的元素都是有序的（这样的数组称为 h 有序数组）
每次循环完结，h 都要递加一次，直到 h 等于 1

ps：h 的递加形式是多种多样的，不同的递加形式决定了希尔排序算法的效率，目前还没有钻研出最好的递加序列

// 基于插入排序的希尔排序算法
#ifndef __SHELLSORT_H__
#define __SHELLSORT_H__

// 希尔排序
class Shell
{
public:
  //1.0 版本
  void Sort1_0(char *a, int length)
  {
    // 确定 h 的最大值
    int h = 1;
    while (h < length / 3)
      h = 3 * h + 1;    //1,4,13,40,121,364,1093，...
  
    while (h >= 1)  // 距离管制
    {for (int i = 0; i < h; ++i)  // 每个子数组的头
      {
        // 对每个子数组进行插入排序
        for (int j = i + h; j < length; j += h)
        {char needToInsert = a[j];
          int k;
          for (k = j - h; j >= i&&needToInsert < a[k]; k -= h)
            a[k + h] = a[k];
      
          a[k + h] = needToInsert;
        }
      }
    
      h /= 3;
    }
  }
  
  //2.0 版本
  void Sort2_0(char *a, int length)
  {
    // 确定 h 的最大值
    int h = 1;
    while (h < length / 3)
      h = 3 * h + 1;    //1,4,13,40,121,364,1093，...
  
    while (h >= 1)
    {for (int i = h; i < length; ++i)    // 从所有子数组的第二元素开始到最初的元素，妙
      {
        // 在 i 元素所属的子数组内对 i 元素进行插入排序
        char needToInsert = a[i];
        int j;
        for (j = i - h; j >= 0 && needToInsert < a[j]; j -= h)
          a[j + h] = a[j];
    
        a[j + h] = needToInsert;
      }
    
      h /= 3;
    }
  }
};

#endif

该算法的长处是能够解决大规模的数据，实用于大部分场合，其它更简单优良的排序算法最多比该算法快 2 倍。毛病是无奈解决超大规模的数据

应用该算法对 n 个元素进行排序时

工夫复杂度目前在数学上是未知的

空间复杂度为 0

稳固排序

排序效率与输出无关

#ifndef __MERGESORT_H__
#define __MERGESORT_H__

#include <iostream>  /* NULL */
#include <algorithm>  /* min */

using namespace std;

class Merge
{
private:
  // 原数组的正本, 辅助空间
  char *aux;
public:
  Merge(){ aux = NULL;}
  
  // 单次归并，将 a 数组的两局部已排好的子数组合并起来
  //mid 代表右边子数组的最初一个元素下标
  void merge(char *a, int left, int mid, int right)
  {for (int i = left; i <= right; ++i)
      aux[i] = a[i];
  
    int idxOfLeft = left;
    int idxOfRight = mid + 1;
    // 开始归并
    for (int i = left; i <= right; ++i)
    {if (idxOfLeft > mid&&idxOfRight <= right)
        a[i] = aux[idxOfRight++];
      else if (idxOfLeft <= mid&&idxOfRight > right)
        a[i] = aux[idxOfLeft++];
      else if (aux[idxOfLeft] < aux[idxOfRight])
        a[i] = aux[idxOfLeft++];
      else
        a[i] = aux[idxOfRight++];
    }
  }
  
  // 自顶向下的递归归并排序
  // 这个函数还能够优化，如果 left 和 right 之间的插值小到肯定的水平，就不必再递归了；间接用插入排序、希尔排序或者抉择排序，速度能够晋升；其中插入排序能够缩短 10%~15%
  void SortCore(char *a, int left, int right)
  {if (left >= right)        // 能够改成 ==
      return;
    else
    {int mid = (left + right) / 2;
      SortCore(a, left, mid);
      SortCore(a, mid + 1, right);
      merge(a, left, mid, right);    // 这条语句在执行前还能够做一个判断：如果 a[mid]<=a[mid+1]，这条语句能够不执行；}
  }
  
  // 启动函数
  void Sort(char *a, int length)
  {
    // 避免内存透露
    if (aux != NULL)
    {delete[] aux;
      aux = NULL;
    }
  
    aux = new char[length];
    SortCore(a, 0, length - 1);
  }
  
};

class MergeBu
{
private:
  // a 数组的正本, 辅助空间
  char *aux;

public:
  MergeBu(){ aux = NULL;}
  
  // 单次归并，将 a 数组的两局部已排好的子数组合并起来
  //mid 代表右边子数组的最初一个元素下标
  void merge(char *a, int left, int mid, int right)
  {for (int i = left; i <= right; ++i)
      aux[i] = a[i];
  
    int idxOfLeft = left;
    int idxOfRight = mid + 1;
    // 开始归并
    for (int i = left; i <= right; ++i)
    {if (idxOfLeft > mid&&idxOfRight <= right)
        a[i] = aux[idxOfRight++];
      else if (idxOfLeft <= mid&&idxOfRight > right)
        a[i] = aux[idxOfLeft++];
      else if (aux[idxOfLeft] < aux[idxOfRight])
        a[i] = aux[idxOfLeft++];
      else
        a[i] = aux[idxOfRight++];
    }
  }
  
  // 自底向上的归并排序
  // 能够给链表进行排序，而不必辅助数组
  void Sort(char *a, int length)
  {
    // 保险
    if (aux)
    {delete[] aux;
      aux = NULL;
    }
  
    aux = new char[length];
  
    for (int subArraySize = 1; subArraySize < length; subArraySize <<= 1)
    {for (int left = 0; left + subArraySize < length; left += (subArraySize << 1))    // 留神这里的终止条件
        merge(a, left, left + subArraySize - 1, min(left + (subArraySize << 1) - 1, length - 1));
    }
  }
};

#endif

该算法的长处是可能解决超大规模的数据，毛病是须要 O(n)大小的辅助空间

应用该算法对 n 个元素进行排序时

工夫复杂度为 O(nlgn)，元素间的比拟次数在最坏的状况下为 nlgn 次，在最好的状况下为 (nlgn/2) 次，均匀为 (nlgn)(3/4) 次。

空间复杂度为 O(n)+ 递归辅助栈大小

非稳固排序

在介绍算法之前须要先理解一个操作 – 切分

切分的指标是通过调整数组将首元素 (或尾元素) 放到正确的地位。该地位右边的元素都小于该地位的元素，左边的元素都大于该地位的元素。切分的一个经典利用是查找数组中第 k 大的元素。须要留神的是，切分要在一个数组上进行各种替换操作，如果不想扭转原数组的话，则须要多创立一个数组来进行辅助

疾速排序函数的根本步骤：对数组进行切分，再对通过切分失去的两个子数组别离调用疾速排序函数

#ifndef __QUICKSORT_H__
#define __QUICKSORT_H__

class Quick
{
public:
  void Sort(char *a, int length)
  {// 在开始递归排序前最好先打乱一下数组，避免不合理的切分；这样就不容易呈现 O(N^2)这种状况
    SortCore(a, 0, length - 1);
  }
  
  // 能够优化：在数组被宰割得小于某个数值的时候，改用插入排序
  void SortCore(char *a, int left, int right)
  {if (left >= right)
    {return;}
    else
    {int j = Partition(a, left, right);
      SortCore(a, left, j - 1);
      SortCore(a, j + 1, right);
    }
  }
  
  // 能够优化：选取局部元素来找出这部分元素的中位数当作基准
  // 能够优化（代码看 quick3way）int Partition(char *a, int left, int right)
  {
    // 宰割规范，取了首元素来当规范
    char standard = a[left];

    int i = left+1;
    int j = right;
    while(true)
    {
      // 特地留神 ++i 和 --j 的地位
      // 留神 a[i] <= standard 和 standard <= a[j]的等于号
      while (i <= right && a[i] <= standard){++i;}      //i <= right 能够改成 i < right
      while (j >= left + 1 && standard <= a[j]){--j;}    //j >= left+ 1 不能够更改 j > left+1
     
      if (i < j)
      {char temp = a[i];
        a[i] = a[j];
        a[j] = temp;
      }
      else
        break;
     
    }

    a[left] = a[j];
    a[j] = standard;
  
    return j;
  }
};

// 三向切分的疾速排序：在一个数组中，不会屡次抉择主键值同样的元素作为基准；能够改成三向切分，就是比基准值小的元素放在右边，与基准值相等的元素放在两头，比基准值大的元素放在左边；对于蕴含大量反复元素的数组，能够将工夫复杂度有 NlgN 降到 N
class Quick3way
{
public:
  void Sort(char *a, int length)
  {// 在开始递归排序前最好先打乱一下数组，避免不合理的切分；这样就不容易呈现 O(N^2)这种状况
    SortCore(a, 0, length - 1);
  }
  
  void SortCore(char *a, int left, int right)
  {if (left >= right)
    {return;}
    else
    {
      // 三向切分
#if 0
      // 第一次切分
      char standard = a[left];
      int i = left+1;
      int j = right;
      while(true)
      {while (a[i] < standard && i <= right){++i;}
        while (standard <= a[j] && j >= left+1){--j;}
    
        if (i < j)
        {char temp = a[i];
          a[i] = a[j];
          a[j] = temp;
        }
        else
          break;
      }
      a[left] = a[j];
      a[j] = standard;
    
      int lessRight = j - 1;
    
      // 第二次切分
      j = right;
      while(true)
      {while (a[i] == standard && i <= right){++i;}
        while (standard < a[j] && j >= lessRight + 2){--j;}
    
        if (i < j)
        {char temp = a[i];
          a[i] = a[j];
          a[j] = temp;
        }
        else
          break;
      }
    
      int equelRight = j;
    
      SortCore(a, left, lessRight);
      SortCore(a, equelRight + 1, right);
#endif
#if 1  
      // 如果无奈了解这段代码，请应用样例：6、2、3、7、6、6、9、1，来模仿一下
      char standard = a[left];
      //[left,lt-1]中的元素都小于基准值
      //[lt,i-1]中的元素都等于基准值
      //[gt+1,right]中的元素都大于基准值
      int lt = left;
      int i = left + 1;
      int gt = right;
      while (i <= gt)
      {if (a[i] < standard)
        {char temp = a[i];
          a[i] = a[lt];
          a[lt] = temp;
      
          ++i;
          ++lt;
        }
        else if (a[i] == standard)
        {++i;}
        else if (a[i] > standard)
        {char temp = a[i];
          a[i] = a[gt];
          a[gt] = temp;
      
          --gt;
        }
      }
      
      SortCore(a, left, lt - 1);
      SortCore(a, i, right); 
#endif
    }
  }
};

#endif

该算法的长处是可优化的空间大，通过精心调优的疾速排序在大多数状况下都会比其余基于比拟的排序算法更快，毛病是如果每次切分抉择的元素都不正确，算法运行效率就会大幅度降低。例如第一次选了最小元素，第二次抉择了次小元素作基准 …，这种状况下工夫复杂度就会变成 O(n^2)，然而这种状况呈现的概率比你电脑被雷劈中的概率还要小

应用该算法对 n 个元素进行排序时

工夫复杂度为 O(nlgn)，尽管和归并排序一样，然而比归并要快

空间复杂度为递归辅助栈的大小

在解说堆排序之前须要先介绍一个数据结构 – 优先队列。该数据结构每一次取元素都只能获取最大（或最小）的元素

实现优先队列的形式有很多种

能够通过数组来实现无序或有序的优先队列

还能够通过二叉堆来实现。二叉堆是一棵父节点总是大于（或小于）等于两个子节点的二叉树，这样一棵二叉树又能够说是堆有序的。二叉堆能够应用数组模式的齐全二叉树来存储

树包含堆，堆包含二叉堆。因为个别应用的堆都是二叉堆，所以通常将二叉堆称为堆

为堆增加或移除元素都会先毁坏堆的有序状态，而后再遍历堆来复原有序状态（这个过程称为堆的有序化）

以下二叉堆都是最大堆

// 优先队列的一种实现形式：二叉堆
// 二叉堆：用这个数据结构能够很容易进行排序，然而间接用这个数据结构来排序效率并不高，因为咱们只用很小一部分代码就够了
class MaxPQ
{
private:
  char *pq;    // 节点为 k，父节点为(k-1)/2，左孩子为 2 *k+1，右孩子为 2 *k+2
  int count;   // 记录堆中元素的个数
public:
  MaxPQ(int maxN)
  {pq = new char[maxN];
    count = 0;
  }
  ~MaxPQ()
  {delete[] pq;
  }
  bool isEmpty()
  {return count == 0;}
  int size()
  {return count;}
  void insert(char v)
  {pq[count] = v;
    swim(count);

    ++count;
  }
  char delMax()
  {char max = pq[0];

    char temp = pq[0];
    pq[0] = pq[count - 1];
    pq[count - 1] = temp;

    --count;

    sink(0);

    return max;
  }
  // 外围
  void swim(int k)
  {while (k > 0 && pq[k] > pq[(k - 1) / 2])
    {char temp = pq[k];
      pq[k] = pq[(k - 1) / 2];
      pq[(k - 1) / 2] = temp;

      k = (k - 1) / 2;
    }
  }
  // 外围
  void sink(int k)
  {while (2 * k + 1 < count)
    {
      int maxChild = 2 * k + 1;
      if (maxChild + 1 < count && pq[maxChild + 1] > pq[maxChild])
        ++maxChild;

      if (pq[k] >= pq[maxChild])
        break;
      else
      {char temp = pq[k];
        pq[k] = pq[maxChild];
        pq[maxChild] = temp;

        k = maxChild;
      }

    }
  }
};

数据结构	插入第一个元素	删除最大元素
基于有序数组的优先队列	N	1
基于无序数组的优先队列	1	N
基于二叉堆的优先队列	lgN	lgN
某种现实的优先队列	1	1

从 N 个元素中找到最大的 M 个元素所需的老本：

某种现实的优先队列	工夫复杂度	空间复杂度（用于存储 N 个输出）
其余最快的排序算法	NlgN	N
数组实现的优先队列	NM	M
二叉堆实现的优先队列	NlgM	M

非稳固排序

堆排序的根本步骤：

将一个数组建成堆，建堆的办法有两种：
1. 层序遍历二叉树（从左到右遍历数组），每个节点都进行上浮操作
2. 从非叶子节点开始反向层序遍历二叉树（从右到左遍历数组），每个节点都进行下沉操作。这种形式的效率更高，只须要少于 2N 次比拟以及少于 N 次替换
一直删除堆顶元素

#ifndef __HEAPSORT_H__
#define __HEAPSORT_H__

class Heap
{
public:
  // 留神：count 是待排序数组的长度
  void sink(char *a, int k, int count)
  {while (2 * k + 1 < count)
    {
      int maxChild = 2 * k + 1;
      if (maxChild + 1 < count && a[maxChild + 1] > a[maxChild])
        ++maxChild;

      if (a[k] >= a[maxChild])
        break;
      else
      {char temp = a[k];
        a[k] = a[maxChild];
        a[maxChild] = temp;

        k = maxChild;
      }
    }
  }
  // 能够优化：先下沉后上浮，可将比拟次数缩小一半；这个办法须要额定的空间来辅助，只有当比拟须要很高的代价时才采纳
  void sort(char *a,int count)
  {for (int i = (count - 1) / 2; i >= 0; --i)
      sink(a, i, count);

    for (int i = count - 1; i > 0; --i)
    {char temp = a[i];
      a[i] = a[0];
      a[0] = temp;

      sink(a, 0, i);
    }
  }
};

#endif

小弟才浅，如果本篇文章有任何谬误和倡议，欢送大家留言

感激大家的点赞、珍藏

微信搜「三年游戏人」第一工夫浏览最新内容，获取一份收集多年的书籍包以及优质工作内推

关于程序员:工作多年之后回顾经典排序算法

抉择排序

代码实现

个性

性能剖析

插入排序

代码实现

个性

性能剖析

希尔排序

代码实现

个性

性能剖析

归并排序

代码实现

个性

性能剖析

疾速排序

代码实现

个性

性能剖析

优先队列

基于二叉堆实现的优先队列

代码实现

性能剖析

堆排序

代码实现