专业术语

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
• 不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
• 内排序：所有排序操作都在内存中完成；
• 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
• 时间复杂度： 一个算法执行所耗费的时间。
• 空间复杂度：运行完一个程序所需内存的大小。

各种算法时间复杂度一览表:

图片解释:

• n: 数据规模
• k: “桶”的个数
• In-place: 占用常数内存，不占用额外内存
• Out-place: 占用额外内存

比较排序和非比较排序优劣对比

1. 分类:
   • 比较排序: 快速排序、归并排序、堆排序、冒泡排序
   • 非比较排序: 计数排序、基数排序、桶排序
2. 优劣:
   • 比较排序适用于各种规模的数据，也不在乎数据的分布，都能进行排序。
   • 非比较排序时间复杂度低，比较排序时间复杂度高。
   • 但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。

冒泡排序O(n^2)

1. 比较数组相邻2个数，若顺序不对，则调整顺序，然后对整个数组进行(n-1)次排序。
2. 冒第一次，则可以选出数组最大数，冒第二次，则可选出第二大，以此类推。
3. 可以做一个优化，如果一次比较中，没有做任何交换，则表示已经有序，停止继续。原因是两两比较，如果不是已经有序，不可能不交换。
   

以下均是比较排序:

选择排序O(n^2)

1. 假设第一个数最小，从其余数里找，如果比第一个数小，则替换。
2. 以此类推，找出所有最小，则拍完序。
   

阅读剩下更多

抽象数据类型ADT

1. 一堆数据对象+一些数据操作

单向链表特点

1. 链表在内存中非连续存储，来减小插入删除，对象移动上的开销。
2. 每一个节点都包含其自身元素内容与下一节点的链（next链），最后一个元素next链为null。

阅读剩下更多

数组的基本知识

1. 基本写法

1
2
3
4
5
6
7
8
9
10
11

int intArray[];
intArray = new int[20];

int b[] = new int[] { 1, 2, 3, 4 };
int b[] = {1, 2, 3, 4}; // latest java can use this.
for (int each: b) {
  System.out.println(each);
}

Student student[] = new Student[5];
student[1] = new Student("student1");

阅读剩下更多