3、排序算法
1）内部排序：
归并排序、交换排序（冒泡排序、快排）、选择排序、插入排序
冒泡排序
（1）比较相邻的元素。如果第一个比第二个大，就交换他们两个。
（2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
（3）针对所有的元素重复以上的步骤，除了最后一个。
（4）持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
时间复杂度：O(n^2)，最优时间复杂度：O(n)，平均时间复杂度：O(n^2)
public static void bubbleSort(Comparable[] a) {
int j, flag;
Comparable temp;
for (int i = 0; i
flag = 0;
for (j = 1; j
if(a[j].compareTo(a[j - 1]) < 0) {
temp = a[j];
a[j] = a[j -1];
a[j - 1] =temp;
flag = 1;
}
}
//如果没有交换，代表已经排序完毕，直接返回
if (flag == 0) {
return;
}
}
}
插入排序
（1）从第一个元素开始，该元素可以认为已经被排序
（2）取出下一个元素，在已经排序的元素序列中从后向前扫描
（3）如果该元素（已排序）大于新元素，将该元素移到下一位置
（4）重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
（5）将新元素插入到该位置后
（6）重复步骤2~5
时间复杂度：O(n^2)，最优时间复杂度：O(n),平均时间复杂度：O(n^2)
public static void insertionSort(Comparable[] a) {
int length = a.length;
Comparable temp;
for (int i = 1; i < length; i++) {
for (int j = i; j> 0 && a[j].compareTo(a[j - 1]) < 0; j--) {
temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp;
}
}
}
// 对实现Comparable的类型进行排序，先将大的元素都向右移动，减少一半交换次数
public static void insertionSort(Comparable[] a) {
int length = a.length;
Comparable temp;
int j;
for (int i = 1; i < length; i++) {
temp = a[i];
for (j = i; j > 0&& temp.compareTo(a[j - 1]) < 0; j--) {
a[j] = a[j - 1];
}
a[j] = temp;
}
}
选择排序
首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。
时间复杂度：O(n^2)，最优时间复杂度：O(n^2)，平均时间复杂度：O(n^2)
public static Integer[] selectSort(Integer[] arr)
{
List sortList = new ArrayList<>();
List numList = new LinkedList(Arrays.asList(arr));
int len = arr.length;
for (int i = 0; i < len; i++)
{
int smallest =findSmallest(numList);
arr[i] = numList.get(smallest);
numList.remove(smallest);
}
return arr;
}
private static int findSmallest(List numList)
{
int smallest = numList.get(0);
int smallestIndex = 0;
int len = numList.size();
for (int i = 0; i < len; i++)
{
if (numList.get(i) < smallest)
{
smallest = numList.get(i);
smallestIndex = i;
}
}
return smallestIndex;
}
希尔排序
希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。
时间复杂度：根据步长而不同，最优时间复杂度：O(n),平均时间复杂度：根据步长而不同
public static void shellSort(Comparable[] a) {
int length = a.length;
int h = 1;
Comparable temp;
while (h < length /3) {
h = 3 * h + 1;
}
while (h >= 1) {
for (int i = h; i< length; i++) {
for (int j = i;j >= h && a[j].compareTo(a[j - h]) < 0; j -= h) {
temp = a[j];
a[j] = a[j -h];
a[j - h] =temp;
}
}
h /= 3;
}
}
堆排序
（1）创建最大堆（Build_Max_Heap）：将堆所有数据重新排序
（2）堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
时间复杂度：O(nlogn)，最优时间复杂度：O(nlogn),平均时间复杂度：O(nlogn)
public static void heapSort(Comparable[] a) {
int length = a.length;
Comparable temp;
for (int k = length / 2;k >= 1; k--) {
sink(a, k, length);
}
while (length > 0) {
temp = a[0];
a[0] = a[length -1];
a[length - 1] =temp;
length--;
sink(a, 1, length);
}
}
private static void sink(Comparable[] a, int k, int n) {
Comparable temp;
while (2 * k <= n) {
int j = 2 * k;
if (j < n&& a[j - 1].compareTo(a[j]) < 0) {
j++;
}
if (a[k -1].compareTo(a[j - 1]) >= 0) {
break;
}
temp = a[k - 1];
a[k - 1] = a[j - 1];
a[j - 1] = temp;
k = j;
}
}
归并排序
归并操作（merge），也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。
时间复杂度：O(nlogn)，最优时间复杂度：O(n),平均时间复杂度：O(nlogn),空间复杂度O(n)
private staticComparable[] aux;
// 自顶向下
public staticvoid mergeSort(Comparable[] a) {
aux = new Comparable[a.length];
mergeSort(a, 0, a.length - 1);
}
public static void mergeSort(Comparable[] a, int lo, int hi) {
if (hi <= lo) {
return;
}
int mid = (lo + hi)>>> 1;
mergeSort(a, lo, mid);
mergeSort(a, mid + 1,hi);
merge(a, lo, mid, hi);
}
public static void merge(Comparable[] a, int lo, int mid, int hi){
int i = lo, j = mid + 1;
for (int k = lo; k <=hi; k++) {
aux[k] = a[k];
}
for (int k = lo; k <=hi; k++) {
if (i > mid) {
a[k] = aux[j++];
} else if (j >hi) {
a[k] = aux[i++];
} else if(aux[j].compareTo(aux[i]) < 0) {
a[k] = aux[j++];
} else {
a[k] = aux[i++];
}
}
}
快速排序
快排步骤：
*（1）选择基准值；
*（2）将数组分为两个子数组：小于基准值的元素和大于基准值的元素；
*（3）对这两个子数组进行快速排序。
时间复杂度：O(n^2)，最优时间复杂度：O(nlogn),平均时间复杂度：O(nlogn)
快排的时间复杂度跟选取基准的方法有关，一下是默认选择了第一个元素作为基准，随机性较大。
可以在序列中选取开始中间结尾三个数的中位数作为基准，进行优化。
public static List quickSort(List list)
{
int length = list.size();
if (length < 2)
{
System.out.println("The size of list less than 2!");
return list; // 基线条件：为空或者只包含一个元素的数组是“有序”的
}
int pivot = list.get(length / 2); // 递归条件，如果总是将第一个元素用作基准值，则最差算法运行时间为O（n^2）,如果选择中间元素为基准值则最佳算法时间为O（nlogn），每次随机选择基准值则平均算法时间为O（nlogn）
List<Integer> less = new ArrayList<>();
List greater = new ArrayList<>();
list.remove(length / 2);
for (int element : list)
{
if (element < pivot)
{
less.add(element);
// 由所有小于基准值的元素组成的子数组
}
else
{
greater.add(element);
// 由所有大于基准值的元素组成的子数组
}
}
System.out.println("less is " + less);
List lessSort =quickSort(less);
// 对小于基准值的子数组递归执行快速排序
List greaterSort =quickSort(greater);// 对大于基准值的子数组递归执行快速排序
lessSort.add(pivot); // 组合小于基准值的子数组、基准值、大于基准值的子数组
lessSort.addAll(greaterSort);
return lessSort;
}
public static void main(String[] args)
{
List list = new ArrayList<>();
list.add(9);
list.add(6);
list.add(0);
list.add(10);
list.add(-1);
list.add(2);
System.out.println(quickSort(list));
List linkedList = new ArrayList<>(Arrays.asList(new Integer[] { 1, 2, 3 }));
linkedList.remove(1);
System.out.println(linkedList);
}
2）外部排序：
掌握利用内存和外部存储处理超大数据集，至少要理解过程和思路、排序的稳定性和效率等。
1、定义问题
外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。外部排序最常用的算法是多路归并排序，即将原文件分解成多个能够一次性装入内存的部分，分别把每一部分调入内存完成排序。然后，对已经排序的子文件进行多路归并排序。
2、处理过程
（1）按可用内存的大小，把外存上含有n个记录的文件分成若干个长度为L的子文件，把这些子文件依次读入内存，并利用有效的内部排序方法对它们进行排序，再将排序后得到的有序子文件重新写入外存；
（2）对这些有序子文件逐趟归并，使其逐渐由小到大，直至得到整个有序文件为止。
内存排序环节：磁盘中的数据序列被分割成多个段（假定内存有限）读入到内存中，在内存中用模板sort实现排序过程，效率高！
多路归并排序环节：依次从从每个已排序的段文件中（什么是段文件，看上面的内存排序环节，形象了点！！）读入一个数据，注意是一个；挑选最小的写入的目标文件中。
假设文件需要分成k块读入，需要从小到大进行排序。
（1）依次读入每个文件块，在内存中对当前文件块进行排序（应用恰当的内排序算法）。此时，每块文件相当于一个由小到大排列的有序队列。
（2）在内存中建立一个最小值堆，读入每块文件的队列头。
（3）弹出堆顶元素，如果元素来自第i块，则从第i块文件中补充一个元素到最小值堆。弹出的元素暂存至临时数组。
（4）当临时数组存满时，将数组写至磁盘，并清空数组内容。
（5）重复过程（3）、（4），直至所有文件块读取完毕。
先从一个例子来看外排序中的归并是如何进行的？
假设有一个含10000个记录的文件，首先通过10次内部排序得到10个初始归并段R1～R10，其中每一段都含1000个记录。然后对它们作如图10.11所示的两两归并，直至得到一个有序文件为止如下图
多路归并排序
多路归并排序算法在常见数据结构书中都有涉及。从2路到多路（k路），增大k可以减少外存信息读写时间，但k个归并段中选取最小的记录需要比较k-1次，为得到u个记录的一个有序段共需要(u-1)(k-1)次，若归并趟数为s次，那么对n个记录的文件进行外排时，内部归并过程中进行的总的比较次数为s(n-1)(k-1)，若共有m个归并段，则s=logkm,所以总的比较次数为： (向上取整)(logkm)(k-1)(n-1)=(向上取整)(log2m/log2k)(k-1)(n-1)，而(k-1)/log2k随k增而增因此内部归并时间随k增长而增长了，抵消了外存读写减少的时间，这样做不行，由此引出了“败者树”tree of loser的使用。在内部归并过程中利用败者树将k个归并段中选取最小记录比较的次数降为(向上取整)(log2k)次使总比较次数为(向上取整)(log2m)(n-1)，与k无关。
多路归并排序算法的过程大致为：
1）首先将k个归并段中的首元素关键字依次存入b[0]--b[k-1]的叶子结点空间里，然后调用CreateLoserTree创建败者树，创建完毕之后最小的关键字下标（即所在归并段的序号）便被存入ls[0]中。然后不断循环：
2）把ls[0]所存最小关键字来自于哪个归并段的序号得到为q，将该归并段的首元素输出到有序归并段里，然后把下一个元素关键字放入上一个元素本来所 在的叶子结点b[q]中，调用Adjust顺着b[q]这个叶子结点往上调整败者树直到新的最小的关键字被选出来，其下标同样存在ls[0]中。循环这个 操作过程直至所有元素被写到有序归并段里。
败者树
叶子节点记录k个段中的最小数据，然后两两进行比赛。败者树是在双亲节点中记录下刚刚进行完的这场比赛的败者，让胜者去参加更高一层的比赛。决赛，根节点记录输者，所以需要重建一个新的根节点，记录胜者(如下图节点0）。
示例：我们这里以四路归并为例，假设每个归并段已经在输入缓冲区如下图。
每路的第一个元素为胜利树的叶子节点，（5,7）比较出5胜出7失败成为其根节点，（29,9）比较9胜出29失败成为其根节点，胜者（5,9）进行下次的比赛9失败成为其根节点5胜出输出到输出缓冲区。由第一路归并段输出，所有将第一路归并段的第二个元素加到叶子节点如下图：
加入叶子节点16进行第二次的比较，跟胜利树一样，由于右子树叶子节点没有发生变化其右子树不用再继续比较。
位图算法：
问题描述：
输入：给定一个文件，里面最多含有n个不重复的正整数（也就是说可能含有少于n个不重复正整数），且其中每个数都小于等于n，n=10^7。
输出：得到按从小到大升序排列的包含所有输入的整数的列表。
条件：最多有大约1MB的内存空间可用，但磁盘空间足够。且要求运行时间在5分钟以下，10秒为最佳结果。
位图方案。熟悉位图的朋友可能会想到用位图来表示这个文件集合。例如正如编程珠玑一书上所述，用一个20位长的字符串来表示一个所有元素都小于20的简单的非负整数集合，边框用如下字符串来表示集合{1,2,3,5,8,13}：
0 1 1 1 0 1 0 01 0 0 0 0 1 0 0 0 0 0 0
上述集合中各数对应的位置则置1，没有对应的数的位置则置0。
参考编程珠玑一书上的位图方案，针对我们的10^7个数据量的磁盘文件排序问题，我们可以这么考虑，由于每个7位十进制整数表示一个小于1000万的整数。我们可以使用一个具有1000万个位的字符串来表示这个文件，其中，当且仅当整数i在文件中存在时，第i位为1。采取这个位图的方案是因为我们面对的这个问题的特殊性：1、输入数据限制在相对较小的范围内，2、数据没有重复，3、其中的每条记录都是单一的整数，没有任何其它与之关联的数据。
所以，此问题用位图的方案分为以下三步进行解决：
第一步，将所有的位都置为0，从而将集合初始化为空。
第二步，通过读入文件中的每个整数来建立集合，将每个对应的位都置为1。
第三步，检验每一位，如果该位为1，就输出对应的整数。
经过以上三步后，产生有序的输出文件。令n为位图向量中的位数（本例中为1000 0000），程序可以用伪代码表示如下：
上述的位图方案，共需要扫描输入数据两次，具体执行步骤如下：
第一次，只处理1—4999999之间的数据，这些数都是小于5000000的，对这些数进行位图排序，只需要约5000000/8=625000Byte，也就是0.625M，排序后输出。
第二次，扫描输入文件时，只处理4999999-10000000的数据项，也只需要0.625M（可以使用第一次处理申请的内存）。
因此，总共也只需要0.625M
位图的的方法有必要强调一下，就是位图的适用范围为针对不重复的数据进行排序，若数据有重复，位图方案就不适用了。
