13 | 线性排序：如何根据年龄给100万用户数据排序？

用两个指针a、b：a指针从头开始往后遍历，遇到大写字母就停下，b从后往前遍历，遇到小写字母就停下，交换a、b指针对应的元素；重复如上过程，直到a、b指针相交。 对于小写字母放前面，数字放中间，大写字母放后面，可以先将数据分为小写字母和非小写字母两大类，进行如上交换后再在非小写字母区间内分为数字和大写字母做同样处理

计数排序中，从数组A中取数，也是可以从头开始取的吧

老师，个人感觉这节没有以往章节的细致了，拿桶排序来举例： 1、自问的三个问题只有了时间复杂度分析，少了是否为稳定排序算法和空间复杂度两个问题。 1.1）稳定性，若单个桶内用归并排序，则可保证桶排序的稳定性；若使用快排则无法保证稳定性。 1.2）空间复杂度，桶都是额外的存储空间，只有确定了单个桶的大小才能确定空间复杂度；n个元素假设分为m个桶，每个桶分配n/m个元素的大小？个人觉得单个桶的大小不好确定，但是范围应该在n/m~n之间 2、没有伪代码实现，自己在代码实现中遇到了一些问题 2.1）桶个数的设置依据什么原则？ 2.2）桶大小的设置，让桶的能动扩容？ 望回复，谢谢！

计数排序中可以从头向后取数据吗？个人感觉似乎是一样的过程。

看了俩小时

老师你好,觉得计数排序可以完全被桶排序取代,由于计数排序对数据的要求是范围不大,不妨设为k,那完全可以分为k个桶,遍历一遍待排序列,将对应元素放入相关桶中,最后在按顺序遍历一次,即可得到顺序序列.在时间复杂度,空间复杂度上与计数排序一样,但是在代码编写上要比计数排序要简单的多.

哈哈，老师，我把你的计数排序的代码关键代码处优化了下，并且加了中文注释，应该可以很好理解了。 public class CountingSort { /** * 计数排序 * * @param arr 要排序的数组大小 * @param n 数组元素个数 */ public static void sort(int[] arr, int n) { if (n <= 1) { return; } //默认数组最大的元素为数组第一个元素 int max = arr[0]; //遍历数组的所有的元素，找到最大的元素 for (int i = 1; i < n; i++) { //若后面的元素大于指定的数组元素，则把元素进行交换 if (arr[i] > max) { max = arr[i]; } } //申请一个计数数组，下标从0~max。 int[] c = new int[max + 1]; //遍历数组，将每个元素的个数放入到计数数组中，比如分数为0的元素，在c[0]就累加1，依次类推 for (int i = 0; i < n; i++) { c[arr[i]]++; } //开始重新整理c[]数组，将c[]数组顺序求和，比如分数0的个数1，分数为1的个数为3。那么重新整理后，分数<=0的为1，分数<=1人数诶1+3=4个，因为包含了<=0的个数，依次类推 //所以终止条件为i<=max for (int i = 1; i <= max; i++) { c[i] = c[i] + c[i - 1]; } //这时候开始进行排序，创建一个跟要排序的数组一样大小的数据空间 int[] temp = new int[n]; //开始循环需要排序的数据 for (int i = 0; i < n; i++) { //计算出需要往temp临时数组哪个索引位置存放arr[i]的值。 //根据原始数组的值找到计数数组的对应值的计数个数，得到c[arr[i]]的值，也就是temp数组从0开始，所以需要减一 int index = c[arr[i]] - 1; temp[index] = arr[i]; //每次循环，计数数组的元素值减一，因为数组放到了temp数组中 c[arr[i]]--; } //重新赋值 for (int i = 0; i < n; i++) { arr[i] = temp[i]; } } }

老师，你好，有个疑问： 在计数排序中，第一次得到数组int[] c = new int[]{2,0,2,3,0,1}之后， 能不能直接遍历数组c， int j=0; for(int i=0; i<c.length; i++){ int count = c[i]; for(int k=0;k<count;k++){ a[j++] = i; } } 这样不是也对所有的分数进行排序了吗？这个不知道可以不？第一次发言，希望能回复下

老师，你讲的一会数组C,一会数组R，一会数组A，已经被绕晕了，咋办？跟不上节奏了

老师 您好。您说的手机号码排序伪代码向下面这样 sort(array,comparator)//对比第11位 sort(array,comparator)//对比第10位 sort(array,comparator)//对比第9位 sort(array,comparator)//对比第8位 sort(array,comparator)//对比第7位 sort(array,comparator)//对比第6位 sort(array,comparator)//对比第5位 sort(array,comparator)//对比第4位 sort(array,comparator)//对比第3位 sort(array,comparator)//对比第2位 sort(array,comparator)//对比第1位 我不太明白这和直接对比手机号码大小有什么区别 sort(array,comparator)//对比手机号码