算法06-排序及搜索

简介

排序算法(sorting algorithm)是一种能将一串数据依照特性的顺序进行排列的一种算法

排序算法的稳定性

稳定排序算法会让原本相等的键值(key)的记录维持相对秩序。

1、 如果一个排序算法是稳定的,当有两个相等键值的记录R和S,且在原本的列表中R出现在S之前,在排序过的列表中R也将会在S之前。

2、当相等的元素是无法分辨的,比如像是证书,稳定性并不是一个问题。然而,假设一下的数对将要以他们的第一个数字来做排序(下述为举例)

(2,4)  (1,2)  (3,6)  (1,1)

这个情况下,有可能产生两种不同的结果,一个是让相等键值的记录维持相对的秩序,而另外一个则没有

(1,1) (1,2) (2,4) (3,6)   #正确秩序的排序

(1,2)  (1,1)  (2,4) (3,6)  # 秩序变更的排序

不稳定的排序算法可能会在相等的键值中改变记录的相对秩序,但是稳定的排序算法从来不会出现这样的情况。不稳定算法可以被特定的实现为稳定。做着件事情的一个方式就是人工扩充键值的比较,如此在其他方面相同键值的两个对象之间作比较,当做一个同分决赛。然而,要记住这种秩序通常牵涉到额外的空间负担

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部...
    蚁前阅读 5,235评论 0 52
  • 1.插入排序—直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到已排序好...
    依依玖玥阅读 1,287评论 0 2
  • 总结一下常见的排序算法。 排序分内排序和外排序。内排序:指在排序期间数据对象全部存放在内存的排序。外排序:指在排序...
    jiangliang阅读 1,410评论 0 1
  • 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部...
    闲云清烟阅读 771评论 0 6
  • 漫谈文言文与白话文 有人看了我的一些文章后私下对我说:“我仔细想了一下你那复兴古文的想法,觉得还是行不通,现在的人...
    断翼孤鸿阅读 1,338评论 0 1