:-: 第十四章 排序 * * * * * [第十四章 排序——走进‘经典’算法](https://www.kancloud.cn/book/maliming/leetcode/preview/sort.md) 这章的开始我不准备放算法题，而是总结一下“经典”排序算法（网上虽然有，但是也有假博客，害怕自己以后找到假博客，做个笔记），学过数据结构的可以再配合这些经典算法回顾一下，没学的或正在学的也提前理解。“经典”排序算法素材主要来源会选取数据结构教材，维基百科，GitHub，CSDN，博客园等。 什么是排序算法？什么是稳定的排序算法？什么是不稳定的排序算法？怎么分辨一个排序算法是稳定的还是不稳定的？这些在这里我不多说，简单罗列一下，维基百科（需要翻墙，自行百度方法）比我解释的详细，详细分辨方法网上也有（感谢以下材料的作者）。 **稳定的** 冒泡排序（bubble sort）— O(n2) 鸡尾酒排序（cocktail sort,双向的冒泡排序）—O(n2) 插入排序（insertion sort）—O(n2) 桶排序（bucket sort）—O(n);需要O(k)额外空间 计数排序（counting sort）—O(n+k);需要O(n+k)额外空间 归并排序（merge sort）—O(n log n);需要O(n)额外空间 原地归并排序— O（n2） 二叉排序树排序（binary tree sort）— O(n log n)期望时间; O(n2)最坏时间;需要O(n)额外空间 鸽巢排序（pigeonhole sort）—O(n+k);需要O(k)额外空间 基数排序（radix sort）—O(n·k);需要O(n)额外空间 侏儒排序（gnome sort）— O(n2) 图书馆排序（library sort）— O(n log n) with high probability,需要(1+ε)n额外空间 **不稳定** 选择排序（selection sort）—O(n2) 希尔排序（shell sort）—O(n log n)如果使用最佳的现在版本 组合排序— O(n log n) 堆排序（heap sort）—O(n log n) 平滑排序（smooth sort）— O(n log n) 快速排序（quick sort）—O(n log n)期望时间, O(n2)最坏情况;对于大的、乱数列表一般相信是最快的已知排序 内省排序（introsort）—O(n log n) 耐心排序（patience sort）—O(n log n + k)最坏情况时间，需要额外的O(n + k)空间，也需要找到最长的递增子串行（longest increasing subsequence） **不实用的排序算法** Bogo排序— O(n × n!)，最坏的情况下期望时间为无穷。 Stupid排序—O(n3);递归版本需要O(n2)额外存储器 珠排序（bead sort）— O(n) or O(√n),但需要特别的硬件 Pancake sorting—O(n),但需要特别的硬件 臭皮匠排序（stooge sort）算法简单，但需要约n^2.7的时间 [维基百科——排序算法（以及稳定排序，不稳定排序列表）](https://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95) [如何分辨稳定排序和不稳定排序](https://www.cnblogs.com/codingmylife/archive/2012/10/21/2732980.html)