排序算法

Posted on | In |

概述

应用

  • 排序是使用最多的算法
  • 数据结构设计思想
    • divide and conquer 分治
    • specialised data structures
    • randomised algorithms
    • lower bounds
  • 排序算法是很多其他算法的基础
    • 搜索
    • 最短路径
    • 元素唯一性 Element uniqueness
    • 频率分布 Frequency distribution
    • 选择
    • 计算几何和计算机图形学 Computational Geometry and Computer Graphics(CG)
      Convex hull 扫描法找凸包 根据角度排序构建最外层点的凸多边形

分类

  • 内部排序 Internal Sort
    • 关键字比较法
      • incremental method: Insertion Sort插入排序
      • Divide- and- conquer: Quick Sort 快速排序, Merge Sort 归并排序
      • Heap Sort 堆排序
    • distribution
      • Radix Sort 基数排序
  • 外部排序 External Sort

定义

排序

  • 输入Input: 一串数字
  • 输出Output: 输入序列重排序后的排列

评估方面1-稳定排序 Stable Sorting

相等的数字排序前后相对位置不变

评估方面2-时间复杂度 Time Complexity

基于比较的排序，时间由比较次数决定

评估方面3-in-place sorting algorithm

不借助额外的数据结构

In computer science, an in-place algorithm is an algorithm which transforms input using no auxiliary data structure. However a small amount of extra storage space is allowed for auxiliary variables. The input is usually overwritten by the output as the algorithm executes. In-place algorithm updates input sequence only through replacement or swapping of elements. An algorithm which is not in-place is sometimes called not-in-place or out-of-place.

插入排序 Insertion Sort

快速排序 Quick Sort

归并排序 Merge Sort

堆排序 Heap Sort

桶排序 Bucket Sort

基数排序 Radix Sort