排序算法

12年前

排序算法

所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。

目录

简介

分类

排列算法列表

排序的算法

排序算法源代码及复杂度分析

简介

分类

排列算法列表

排序的算法

排序算法源代码及复杂度分析

展开

编辑本段简介

编辑本段分类

  在计算机科学所使用的排序算法通常被分类为:

  计算的复杂度(最差、平均、和最好表现),依据串列(list)的大小(n)。一般而言,好的表现是O(n log n),且坏的行为是Ω(n2)。对于一个排序理想的表现是O(n)。仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要Ω(n log n)

  记忆体使用量(以及其他电脑资源的使用)

  稳定度:稳定排序算法会依照相等的关键(换言之就是值)维持纪录的相对次序。也就是一个排序算法是稳定的,就是当有两个有相等关键的纪录RS,且在原本的串列中R出现在S之前,在排序过的串列中R也将会是在S之前。

  一般的方法:插入、交换、选择、合并等等。交换排序包含冒泡排序bubble sort)和快速排序quicksort)。选择排序包含shaker排序和堆排序heapsort)。