计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
1. 计数排序的特征
当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 Θ(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。
由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。例如：计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序中的算法来排序数据范围很大的数组。
通俗地理解，例如有 10 个年龄不同的人，统计出有 8 个人的年龄比 A 小，那 A 的年龄就排在第 9 位,用这个方法可以得到其他每个人的位置,也就排好了序。当然，年龄有重复时需要特殊处理（保证稳定性），这就是为什么最后要反向填充目标数组，以及将每个数字的统计减去 1 的原因。
?算法的步骤如下：
（1）找出待排序的数组中最大和最小的元素 （2）统计数组中每个值为i的元素出现的次数，存入数组C的第i项 （3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加） （4）反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1 2. 动图演示
代码实现 JavaScript实例function countingSort ( arr , maxValue ) {
var bucket = new Array ( maxValue + 1 ) ,
sortedIndex = 0
arrLen = arr. length ,
bucketLen = maxValue + 1
for ( var i = 0 i0 :
arr [ sortedIndex ] = j
sortedIndex+ = 1
bucket [ j ] - = 1
return arr
Go 实例func countingSort ( arr [] int , maxValue int ) [] int {
bucketLen := maxValue + 1
bucket := make ([] int , bucketLen ) // 初始为0的数组
sortedIndex := 0
length := len ( arr )
for i := 0i <length i ++ {
bucket [ arr [ i ]] += 1
}
for j := 0 j <bucketLen j ++ {
for bucket [ j ] > 0 {
arr [ sortedIndex ] = j
sortedIndex += 1
bucket [ j ] -= 1
}
}
return arr
}
Java 实例public class CountingSort implements IArraySort {
@Override
public int [ ] sort ( int [ ] sourceArray ) throws Exception {
// 对 arr 进行拷贝，不改变参数内容
int [ ] arr = Arrays . copyOf ( sourceArray, sourceArray. length )
int maxValue = getMaxValue ( arr )
return countingSort ( arr, maxValue )
}
private int [ ] countingSort ( int [ ] arr, int maxValue ) {
int bucketLen = maxValue + 1
int [ ] bucket = new int [ bucketLen ]
for ( int value : arr ) {
bucket [ value ] ++
}
int sortedIndex = 0
for ( int j = 0 j 0 ) {
arr [ sortedIndex ++ ] = j
bucket [ j ] --
}
}
return arr
}
private int getMaxValue ( int [ ] arr ) {
int maxValue = arr [ 0 ]
for ( int value : arr ) {
if ( maxValue
排序算法是《数据结构与算法》中最基本的算法之一。
排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括：
点击以下图片查看大图：
关于时间复杂度
平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。
线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；
O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序
线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。
关于稳定性
稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。
不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。
名词解释：
n：数据规模 k："桶"的个数 In-place：占用常数内存，不占用额外内存 Out-place：占用额外内存 稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同包含以下内容：
1、冒泡排序 2、选择排序 3、插入排序 4、希尔排序 5、归并排序 6、快速排序 7、堆排序8、计数排序 9、桶排序 10、基数排序排序算法包含的相关内容具体如下：
冒泡排序算法
冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。
选择排序算法
选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n?) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。
插入排序算法
插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
希尔排序算法
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
归并排序算法
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
快速排序算法
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
堆排序算法
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。
计数排序算法
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
桶排序算法
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。
基数排序算法
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
sort_values(by, axis=0, ascending=True, inplace=False, kind='quicksort', na_position='last')by: 可以填入字符串或者字符串组成的列表。也就是说，如果axis=0，那么by="列名"；如果axis=1，那么by="行名"。
axis: {0 or ‘index’, 1 or ‘columns’}, default 0，意思就是如果axis=0，就按照索引排序，即纵向排序；如果axis=1，则按列排序，即横向排序。默认是axis=0。
ascending: 输入布尔型，True是升序，False是降序，也可以可以是[True,False]，即第一个字段升序，第二个字段降序 。
inplace: 输入布尔型，是否用排序后的数据框替换现有的数据框（这个在之前的文章写过很多次了~）
kind: 排序的方法，{‘quicksort’, ‘mergesort’, ‘heapsort’}，默认是使用‘quicksort’。这个参数用的比较少，大家可以试一试。
na_position : {‘first’, ‘last’}，缺失值的排序，也就说决定将缺失值放在数据的最前面还是最后面。first是排在前面，last是排在后面，默认是用last。
创建数据表：
scores= pd.DataFrame([[87,56,85],[46,87,97],[34,65,86]],columns=['jack', 'rose', 'mike'])
scores
‘rose’这一列进行降序排序：
df_sc=scores.sort_values(by='rose',ascending=False)df_sc
‘mike’这一列进行升序排序：
df_sc=scores.sort_values(by='mike',ascending=True)df_sc
对第0行进行升序排序：
scores.sort_values(by=0,axis=1,ascending=True)我们再尝试对第1行进行升序，第0行进行降序：
scores.sort_values(by=[1,0],axis=1,ascending=[True,False]
![请问python中val[0:-1]是什么意思？](/aiimages/%E8%AF%B7%E9%97%AEpython%E4%B8%ADval%5B0%3A-1%5D%E6%98%AF%E4%BB%80%E4%B9%88%E6%84%8F%E6%80%9D%EF%BC%9F.png)
