摘要
本文系Introduction to Java Programming 10e (Java语言程序设计-进阶篇)的学习笔记。涉及以下内容：
插入排序
冒泡排序
归并排序
快速排序
堆排序
桶排序和基数排序
外部排序
一． 插入排序
插入排序的时间复杂度是O(n^2)。
插入排序重复地将新元素插入到一个排好序的子线性表中，直到整个线性表排好序。
算法描述如下：
for(int i=0;i<list.length;i++){
将list[i]插入，将导致已排好序的子线性表后移。
}
public static void insertionSort(int[] list)
{
if(list.length>=2)
{
for(int i=1;i<list.length;i++)
{
int currentElement=list[i];
int k;
for(k=i-1;k>=0&&list[k]>currentElement;k--) {
list[k+1]=list[k];
}
list[k+1]=currentElement;
}
}
}
二． 冒泡排序
最差情况下冒泡的时间复杂度是O(n^2)。
冒泡排序多次遍历数组，在每次遍历中连续比较相邻的元素，如果没按顺序排列，就交换它们的值。
较小的值像“气泡”一样逐渐浮向顶部，而较大的值沉向底部。第一次遍历后最后一个元素是数组中的最大值，第二次遍历后，倒数第二个元素是数组中第二大的数。这个过程持续到所有元素都排好序。
public static void bubbleSort(int[] list)
{
boolean needNextPass=true;
for(int k=1;k<list.length&&needNextPass;k++) {
needNextPass=false;
for(int i=0;i<list.length-k;i++) {
if (list[i] > list[i + 1]) {
int temp = list[i + 1];
list[i + 1] = list[i];
list[i] = temp;
needNextPass=true;
}
}
}
System.out.println(Arrays.toString(list));
}
三． 归并排序
归并排序的时间复杂度是O(nlogn)。
归并排序将数组分为2半，对每部分递归地应用归并排序。在每部分排好序后对它们进行归并。
public class MergeSort {
public static void mergeSort(int[] list)
{
if(list.length>1) {
int[] firstHalf = new int[list.length / 2];
System.arraycopy(list, 0, firstHalf, 0, list.length / 2);
mergeSort(firstHalf);
int secondHalfLength = list.length - list.length / 2;
int[] secondHalf = new int[secondHalfLength];
System.arraycopy(list, list.length / 2, secondHalf, 0, secondHalfLength);
mergeSort(secondHalf);
merge(firstHalf, secondHalf, list);
}
}
public static void merge(int[] list1,int[] list2,int[] temp)
{
int current1=0;
int current2=0;
int current3=0;
while (current1<list1.length&¤t2<list2.length) {
if(list1[current1]<list2[current2])
temp[current3++]=list1[current1++];
else
temp[current3++]=list2[current2++];
}
while (current1<list1.length) {
temp[current3++]=list1[current1++];
}
while (current2<list2.length) {
temp[current3++]=list2[current2++];
}
}
}
四． 快速排序
快速排序的平均时间为O(nlogn) –各种精确的平均情况分析超出本笔记目标。快排的空间效率高于归并排序。
快速排序的工作机制：该算法在数组中选择一个元素称为主元(pivot)，并将数组分为两部分，使得前半部的元素都小于或等于主元，后半部的元素都大于主元。对第一部分递归地应用快速排序算法，然后对第二部分递归地应用快速排序算法。
快速排序由C.A.R.Hoare于1962年开发。主元的选择会影响算法的性能。
public class QuickSort {
public static void quickSort(int[] list)
{
quickSort(list,0,list.length-1);
}
public static void quickSort(int[] list,int first,int last)
{
if(last>first) {
int pivotIndex = partition(list, first, last);
quickSort(list, 0, pivotIndex - 1);
quickSort(list, pivotIndex + 1, last);
}
}
public static int partition(int[] list,int first,int last)
{
int pivot=list[first];
int low=first+1;
int high=last;
while(high>low) {
while(low<=high&&list[low]<=pivot)
low++;
while(high>=low&&list[high]>=pivot)
high--;
if(high>low) {
int temp=list[high];
list[high]=list[low];
list[low]=temp;
}
}
while(high>first&&list[high]>=pivot)
high--;
if(pivot>list[high]) {
list[first]=list[high];
list[high]=pivot;
return high;
}
else {
return first;
}
}
}
五． 堆排序
堆排序的时间复杂度为O(nlogn)，与归并排序相同，但堆排序的空间效率高于归并排序。
堆排序使用的是二叉堆。它首先将所有的元素添加到一个堆上，然后不断移除最大的元素以获得一个排好序的线性表。
二叉堆(binary heap) 是一棵具有以下属性的二叉树：
1).它是一棵完全二叉树。
2).每个结点大于或等于它的任意一个孩子。
上图中，只有a是一个堆。b的根(39)小于它的右孩子(42)，c和d的二叉树都不是完全的。
1.堆的存储
如果堆的大小事先知道，那么可以将堆存储到一个数组。数根在位置0处，它的两个孩子在位置1和位置2处。
对于位置i的结点，它的左子结点在位置2i+1处，它的右子结点在位置2i+2处，而它父结点在位置(i-1)/2处。
2.添加一个新结点
为了给堆添加一个新结点，首先将它添加到堆的末尾，然后按如下方式重建这棵树：
将最后一个结点作为当前结点；
while(当前结点大于它的父结点){
将当前结点与它的父结点交换；
现在当前结点往上面进了一个层次；
}
3.删除根结点
经常需要删除推中最大元素，也就是堆中的根结点。在删除根结点后，必须要重建这棵树以保持堆的属性：
用最后一个结点替换根结点；
让根结点成为当前结点；
while(当前结点具有子结点并且当前结点小于它的子结点){
将当前结点与它的较大子结点交换；
现在当前结点往下面退了一个层次；
}
上图将原根删除后
public class Head<E extends Comparable<E>> {
private java.util.ArrayList<E> list=new java.util.ArrayList<>();
public Heap() {
}
public Head(E[] objects){
for(int i=0;i<objects.length;i++)
add(objects[i]);
}
public void add(E newObject){
list.add(newObject);
int currentIndex=list.size()-1;
while (currentIndex>0){
int parentIndex=(currentIndex-1)/2;
if(list.get(currentIndex).compareTo(list.get(parentIndex))>0){
E temp=list.get(currentIndex);
list.set(currentIndex,list.get(parentIndex));
list.set(parentIndex,temp);
}
else
break;
currentIndex=parentIndex;
}
}
public E remove(){
if(list.size()==0)return null;
E removedObject=list.get(0);
list.set(0,list.get(list.size()-1));
list.remove(list.size()-1);
int currentIndex=0;
while (currentIndex<list.size()){
int leftChildIndex=2*currentIndex+1;
int rightChildIndex=2*currentIndex+2;
if(leftChildIndex>=list.size()) break;//the tree is a heap
int maxIndex=leftChildIndex;
if(rightChildIndex<list.size()){
if(list.get(maxIndex).compareTo(list.get(rightChildIndex))<0){
maxIndex=rightChildIndex;
}
}
//swap if the current node is less than the maximum
if(list.get(currentIndex).compareTo(list.get(maxIndex))<0){
E temp=list.get(maxIndex);
list.set(maxIndex,list.get(currentIndex));
list.set(currentIndex,temp);
currentIndex=maxIndex;
}
else
break;
}
return removedObject;
}
public int getSize(){
return list.size();
}
}
六． 桶排序和基数排序
通常基数排序需要耗费O(dn)的时间对带整数键的n个元素排序，其中d是所有键值中基数位数目的最大值。
桶排序是稳定的(stable)，这意味着原始线性表中的两个元素有相同的键值，那么它们在有序线性表中的顺序是不变的。
import java.util.LinkedList;
//注意这里只实现了简单的1位处理
public class BucketSort {
public static void bucketSort(int[] list)
{
LinkedList[] bucket=new LinkedList[10];
for(int i=0;i<list.length;i++) {
int key=calKey(list[i]);
if(bucket[key]==null)
bucket[key]=new LinkedList();
System.out.println(list[i]);
bucket[key].add(list[i]);
}
int k=0;
for(int i=0;i<bucket.length;i++) {
if(bucket[i]!=null) {
for(int j=0;j<bucket[i].size();j++) {
list[k++]=(int)bucket[i].get(j);
}
}
}
}
private static int calKey(int value)
{
return value%10;
}
}
七． 外部排序
外部排序的I/O复杂度为O(n)，合并步骤的总数为log(n/c)，总数为O(n)*log(n/c)，因此外部排序的复杂度是O(nlogn)。
外部排序通常用来对大容量数据进行排序，一种归并排序的变体分两步：
阶段I:重复将数据从文件读入数组，并使用内部排序算法对数组排序，然后将数据从数组输出到一个临时文件，临时文件中保存的是S1,S2,…Sk的有序分段，分段S的大小依赖于分配的内存大小，最后一个分段Sk的数值可能会较少（不满）。
阶段II:
将每对有序分段（比如S1和S2,S3和S4，…）归并到一个大一些的有序分段中，并将新分段存储到新的临时文件中。继续同样的过程直到得到仅仅一个有序分段。
（代码略）