本文试图将四类最基础也最常用的损失函数进行统一归纳，以明白各自的区别，加深对他们的记忆和理解。

本文会从两个步骤分析损失函数，第一个是从输入到模型的输出，第二个是从模型的输出到损失函数的计算。

第一个步奏，从输入到模型的输出。我先解释一下什么是模型的输出。比如当我们训练好了一个回归模型，用来判断房子的大小和价格的关系。那么，当我们输入一个房子的大小时，模型就会输出一个房子的价格，而这房子的价格就是模型的输出。简单来说，如果用x表示输入的话，f(x)可以用来表示模型的输出。

建立在第一个问题上，我们有了损失函数的概念。损失函数就是来衡量模型的输出与真实值之间的差距。我们试图减小这个差距以达到训练模型的目的。因此，可以认为损失函数是依附于模型输入与输出之上的。



输入，模型输出，损失函数的三者关系

我们可以用上图来表示输入，模型输出，真实值和损失函数之间的关系。

为了更加方便的说明下面的内容，我们还需要注意到样本的概念。这里不试图说明样本概念，只是想提及一个输入和多个输入的区别。



多个输入多个输出

我们在训练模型时，常常是对很多输入和输出来进行的。我们必须要明确多个输入和多个输出的基本规律，而我们求损失函数也是基于多个输出的。实际上，更进一步，我们求导亦是如此。

还要注意的是，输入的数量和输入的维度是不一样的概念，不要混淆。举例来说，还是使用房价的回归来说，我们使用房子的大小和房子距离最近的地铁之间的距离来拟合。这时候，每一个输入xi应该包含两个维度，一个是房子面积，一个是房子与某个地铁的距离。而我们有很多个房子的价格，每一个房子数据则为一个个样本。如下图，这里有三个样本，x1,x2,x3，每个样本则有两个维度。



样本数量与输入维度

综合以上，并进一步说明以下符号的表示：

我们用x表示输入，xij(ij为右下角标)表示不同的输入。其中，i表示样本的标号，j表示维度标号。

f(xi)表示输入为xi时的模型输出。

用L表示所有输入（不管是多少个输入）的总损失，其中Li(i为右下角标)表示输入为xi时的损失。

g(xi)表示真实值，g可以理解为groundtruth。

N表示样本数量。

M表示输入的维度。

用W表示参数。w1表示对应于输入的第一个维度的参数。

还有其他符号会在给出时说明。

1.Mean Square Error

该损失函数可以认为是最基础的损失函数，最易理解。在机器学习中可以简写为MSE，如tensorflow中可以用MSE来说明你使用的损失函数。

中文可以翻译成均方误差。其中，“均”是指平均，如下公式中的N分之一和求和符号，就是对多个输入的损失值求和之后求平均；“方”表示对某个数的平方，如下面公式中的平方；而误差则可以理解为两个数之间的差，可以理解为下面公式中的减号，推广开来可以理解为两个向量之间的差。公式可以是：



Mean Square Error

首先，这个公式并不限制f(x)是怎么得到的。而且直接将模型输入使用在损失函数中。其中2分之1，是为了方便求导计算。

补充说明一下，通常f(x)可以用公式来表示，下面会用其他方式来表示不同损失函数的计算：



公式（1）- 模型的输出

从这个输入到输出的函数来看，这是一个线性关系，最为简单的关系。

大家也都对这个函数很熟悉，这里就不过多介绍。关键是下面的几个损失函数。

2.cross entropy error

可翻译为交叉熵损失，与信息论中熵的概念也是有关系，这里就不展开了。

在第一步，也就是从输入到模型的输出，交叉熵损失的模型输出与均方误差已经有所不同。上面说到，均方误差是一个最简单的线性关系。而对于交叉熵损失来说，需要一个非线性的映射。

在得到f(xi)之后，交叉熵损失函数将其进一步作为输入输进sigmoid的函数中，我们用S(f(xi))来表示：



sigmoid函数

sigmoid函数图像如下图，这是一个输出值在0到1之间的映射关系，属于非线性映射。



sigmoid函数图像

总的来说，对于交叉熵损失函数从输入到输出与均方误差不同的地方在于，在其得到线性映射之后又加了一个sigmoid的非线性映射。

而对于该模型来说，s值就是模型的输出。

以下分析得到模型的输出之后，交叉熵损失如何进一步计算损失的。

如第一节所说，均方误差是用真实值与输出值之间的绝对误差的平方来表示的。

由于各种原因，我们在使用交叉熵损失函数的时候，真实值只有两种情况，一种是0，一种是1。而交叉熵损失中的模型输出在0到1之间。我们使用log函数来表示真实值与模型输出之间的关系。而真实值有两个，我们可以分开讨论。



交叉熵的损失函数

这里，我使用了ln 来 代替 log，这样可以更方便的求导。我们可以接着继续观察一下ln函数的图像。



-ln(x)函数

这里，我们可以看到当输入在0到1之间时，-ln(x)的值域在0到正无穷之间。

损失函数的价值可以分析一下，当真实值为1时，如果模型输出越接近1，则损失值越接近于0；如果模型输出越接近0，则损失值则接近于正无穷。当真实值为0时，如果模型越接近0，则损失值也接近于0，反之亦然。这里可以认为起到了衡量真实值与模型输出之间的作用。

为了统一一下上面的两个真实值的公式，我们有下面这个公式(我们使用g表示g(xi)，使用f表示f(xi))：



统一格式的交叉熵损失

最后，我们再次总结一下，交叉熵损失函数从模型输出到损失函数，使用了对数函数，其特点是真实值要么是0要么是1。损失函数可以让越接近真实值的损失值接近于0，远离真实值的损失值趋向于无穷大。其常用于分类问题中。

3.softmax

交叉熵损失可以解决二分类问题，但是却无法一次性针对多分类问题。这时，我们可以使用softmax进行分类。

同均方误差函数一样，我们得到了f(xi)之后，我们进一步处理。可以描述为求e次方，然后再归一化。得到的一个所有分类总和为1的数，我们用概率来描述这样的方式，实际上，每个数也表示了对应的分类概率，我们用p来作为记号(这里我们用fi来表示f(xi))：



softmax的模型输出

这里只表示一个样本的情况，g=k表示真实情况为k类，X=xi表示输入为xi，j就是一个样本分类的数量。以上就是模型的输出。

而损失函数则是描述真实值和模型输出之间的差距。我们计算好了模型输出之后，我们就可以计算损失函数：



softmax的损失函数

前面第二节已经说到，ln函数的图像关系。我们知道当某一分类的模型输出接近于1的时候，损失值是接近0的。

但是，这里我们貌似只看到了模型的输出，而并没有见到真实值。实际情况并非如此，我们对应的损失函数是某样本下真实值对应的模型输出值的ln值。如果这个值越接近于1，说明我们模型认为这个样本应该就是该类。为了更加形象的说明，下面举出一个实际的例子，例子中只有一个样本，一个样本对应的分类可能有三个，分别为猫，汽车，和人，我们直接从得到了f开始计算：



一个计算softmax的例子

这里关键是要理解损失函数的值与真实值的关系。真实值由于是正确的分类，并没有直接参与计算，而是其对应标签下的概率值参与计算。

可以知道，softmax也是一个非线性的映射，处理的是多分类问题，输出是每个类的概率值，损失函数是正确分类的对数函数值。

4.SVM

还是针对多分类问题，我们在得到了f值之后，进一步进行计算。我们知道模型的输出是我们对样本的分类，而实际上SVM的输出是与核相关的，这也是其独特之处。这里我并不是很想讲核函数是什么，与输出又有什么关系。我们直接认为SVM的输出就是均方误差里的输出，也就是上面一直提到的f(xi)，当然，这还不是最后的输出，SVM的输出就是每个样本的在每个分类下最大值对应的类。

下面我们讲SVM的损失怎么由f（x）计算得到。由于是多分类问题，而我们又使用当前样本在每个分类下最大值对应的类作为我们的预测值，我们可以假设如果正确分类下的值是最大值，则我们的预测是正确的。那么如何衡量这个值了，可以使用差来表示。而又有多个分类，我们进一步可以使用差值的和来进行衡量。

而SVM一个特性就是，只有当真实标签下对应的值比其他值大上一个值才认为是零损失。个人称这个值是保险值。整体公式如下：



SVM损失函数

公式中1就是上面说到的那个值。累加符号表示样本的每一个分类（除了正确的那个分类）。

举个例子，同上面的那个例子，还是从得到了f值开始：



SVM损失的一个例子

另外提一句，我们说SVM其实主要分为两个部分，第一个部分是通过输入求模型的输出，这里面核函数起到重要作用，这里我试图用简单的话来解释核函数有什么作用，它就相当于把输入的x映射到另一个空间上，可以认为这是利用一组不同的基来表示一些向量（也就是原始输入）。而第二个部分就是利用输出得到损失函数，这中间那个值起到重要作用。而在深度学习中，我们通常直接使用第二部分。

总结

最后，本文做一个总结。



总结

在初步认识了类的构造方法，尤其是六大默认成员函数以及重载运算符后，我们就可以利用这些特性，来DIY一个自己的类，我的选择是构建一个可以进行日期方面运算/判断的类:
需要实现的功能:

赋值运算(=);
加减天数还有前/后置++和–；
计算出两个日期之间相差了多少天
判断两个日期的大小(>,==,<);
额外关系运算(>=,<=);

因为Date是一个自定义类型，所有上述的所有功能都需要运算符重载；

详细实现思路请看代码注释:

class Date {
	public:
	int getCipacaty (int year , int month) {//获取每个月的天数
		int days [13] = { 0 , 31 , 28 , 31 , 30 , 31 , 30 , 31 , 31 , 30 , 31 , 30 , 31 };
		int day = days [month];
		if ( month == 2 ) {
			if ( (year % 4 == 0 && year % 10 != 0) || (year % 400 == 0) ) {//针对闰年的二月特殊判断
				day += 1;
			}
		}
		return day;
	}
	Date (int year = 1900 , int month = 1 , int day = 1) {//这是全缺省构造函数；
		if ( year <= 0 || month > 12 || month<1 || day <= 0 || day>getCipacaty (year , month) ) {
			std::cout << "非法日期,日期已设置1900-1-1" << std::endl;
			_year = 1900;
			_month = 1;
			_day = 1;
		}
		_year = year;
		_month = month;
		_day = day;
	}
	Date (const Date& d) {//这是拷贝构造函数；
		_year = d._year;//因为此处参数是d的引用，所以使用.访问成员变量；
		_month = d._month;
		_day = d._day;
	}
	Date& operator=(const Date& d){//之后清一色的运算符重载
		if ( this != &d ) {
			_year = d._year;
			_month = d._month;
			_day = d._day;
		}
		return *this;
	}
	Date operator+=(int day) {
		if ( day < 0 ) {//考虑小于零；
			return *this -= -day;
		}
		_day += day;
		while ( _day > getCipacaty (_year ,_month) ) {
			_day -= getCipacaty (_year , _month);
			++_month;
			if ( _month == 13 ) {
				_month = 1;
				++_year;
			}
		}
		return *this;
	}
	Date operator-=(int day) {
		if ( day < 0 ) {
			return *this += -day;
		}
		_day -= day;
		while ( _day <=0 ) {
			_day += getCipacaty (_year , _month);
			--_month;
			if ( _month == 0 ) {
				_month = 12;
				--_year;
			}
		}
		return *this;
	}
	Date operator+(int days){
		Date ret (*this);//不能改变原来的值，所以先拷贝一份
		ret += days;
		return ret;
	}
	Date operator-(int days) {
		Date ret (*this);//不能改变原来的值，所以先拷贝一份
		ret -= days;
		return ret;
	}
	
	int operator-(const Date& d) {//两个Date互减,考虑润年
		Date c (*this);//因为是const，所以拷贝一下
		int flag = 1;
		if ( c < d ) { flag = -1; }
		int day = 0;
		if ( c < d ) {
			while ( c < d ) {
				++c;
				++day;
			}
			
		}
		else {
			while ( c > d ) {
				--c;
				++day;
			}
		}
		return day*flag;
	}
	Date& operator++() {//前置++；
		*this += 1;
		return *this;
	}
	Date operator++(int) {//后置++；
		Date tmp (*this);
		*this += 1;
		return tmp;
	}
	Date& operator--() {
		*this -= 1;
		return *this;
	}
	Date operator--(int) {
		Date tmp (*this);
		*this -= 1;
		return tmp;
	}
	bool operator>(const Date& d)const {
		if ( _year > d._year ) { return true; }
		else if(_year < d._year) { return false; }
		else {
			if ( _month > d._month ) { return true; }
			else if (_month< d._month ) { return false; }
			else {
				if ( _day > d._day ) { return true; }
				else { return false; }
			}
		}
	}
	bool operator==(const Date& d)const {
		if ( _year == d._year ) {
			if ( _month == d._month ) {
				if ( _day == d._day ) { return true; }
			}
		}
		return false;
	}
	bool operator<(const Date& d)const {
		if ((*this != d) && (!(*this>d))) {
			return true;
		}
		return false;
	}
	bool operator>=(const Date& d)const {
		if ( *this > d || *this == d ) { return true; }
		else {
			return false;
		}
	}
	bool operator<=(const Date& d)const {
		if ( *this < d || *this == d ) { return true; }
		else {
			return false;
		}
	}
	bool operator!=(const Date& d)const {
		if ( !(*this == d) ) {
			return true;
		}
		return false;
	}
	void display () {
		std::cout << _year<<"-" << _month<<"-"<<_day<<std::endl;
	}
	private:
	int _year;
	int _month;
	int _day;
};


int main () {
	Date d1 (1998 , 5,27);
	Date d2 (2019 , 03 , 27);
	d1.display();
	std::cout << "—" << std::endl;
	d2.display ();
	std::cout << "="<<d2 - d1 << std::endl;
	system ("pause");
	return 0;
}

约定
待排序的元素需要实现 Java 的 Comparable 接口，该接口有 compareTo() 方法，可以用它来判断两个元素的大小关系。
使用辅助函数 less() 和 swap() 来进行比较和交换的操作，使得代码的可读性和可移植性更好。
排序算法的成本模型是比较和交换的次数。
public abstract class Sort<T extends Comparable<T>> {

    public abstract void sort(T[] nums);

    protected boolean less(T v, T w) {
        return v.compareTo(w) < 0;
    }

    protected void swap(T[] a, int i, int j) {
        T t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

选择排序
从数组中选择最小元素，将它与数组的第一个元素交换位置。再从数组剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。
选择排序需要 ~N2/2 次比较和 ~N 次交换，它的运行时间与输入无关，这个特点使得它对一个已经排序的数组也需要这么多的比较和交换操作。
  


public class Selection<T extends Comparable<T>> extends Sort<T> {

    @Override
    public void sort(T[] nums) {
        int N = nums.length;
        for (int i = 0; i < N - 1; i++) {
            int min = i;
            for (int j = i + 1; j < N; j++) {
                if (less(nums[j], nums[min])) {
                    min = j;
                }
            }
            swap(nums, i, min);
        }
    }
}

冒泡排序
从左到右不断交换相邻逆序的元素，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。
在一轮循环中，如果没有发生交换，那么说明数组已经是有序的，此时可以直接退出。
  


public class Bubble<T extends Comparable<T>> extends Sort<T> {

    @Override
    public void sort(T[] nums) {
        int N = nums.length;
        boolean isSorted = false;
        for (int i = N - 1; i > 0 && !isSorted; i--) {
            isSorted = true;
            for (int j = 0; j < i; j++) {
                if (less(nums[j + 1], nums[j])) {
                    isSorted = false;
                    swap(nums, j, j + 1);
                }
            }
        }
    }
}

插入排序
每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左侧数组依然有序。
对于数组 {3, 5, 2, 4, 1}，它具有以下逆序：(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)，插入排序每次只能交换相邻元素，令逆序数量减少 1，因此插入排序需要交换的次数为逆序数量。
插入排序的时间复杂度取决于数组的初始顺序，如果数组已经部分有序了，那么逆序较少，需要的交换次数也就较少，时间复杂度较低。

平均情况下插入排序需要 ~N2/4 比较以及 ~N2/4 次交换；
最坏的情况下需要 ~N2/2 比较以及 ~N2/2 次交换，最坏的情况是数组是倒序的；
最好的情况下需要 N-1 次比较和 0 次交换，最好的情况就是数组已经有序了。

  


public class Insertion<T extends Comparable<T>> extends Sort<T> {

    @Override
    public void sort(T[] nums) {
        int N = nums.length;
        for (int i = 1; i < N; i++) {
            for (int j = i; j > 0 && less(nums[j], nums[j - 1]); j--) {
                swap(nums, j, j - 1);
            }
        }
    }
}

希尔排序
对于大规模的数组，插入排序很慢，因为它只能交换相邻的元素，每次只能将逆序数量减少 1。希尔排序的出现就是为了解决插入排序的这种局限性，它通过交换不相邻的元素，每次可以将逆序数量减少大于 1。
希尔排序使用插入排序对间隔 h 的序列进行排序。通过不断减小 h，最后令 h=1，就可以使得整个数组是有序的。
  


public class Shell<T extends Comparable<T>> extends Sort<T> {

    @Override
    public void sort(T[] nums) {

        int N = nums.length;
        int h = 1;

        while (h < N / 3) {
            h = 3 * h + 1; // 1, 4, 13, 40, ...
        }

        while (h >= 1) {
            for (int i = h; i < N; i++) {
                for (int j = i; j >= h && less(nums[j], nums[j - h]); j -= h) {
                    swap(nums, j, j - h);
                }
            }
            h = h / 3;
        }
    }
}


希尔排序的运行时间达不到平方级别，使用递增序列 1, 4, 13, 40, …  的希尔排序所需要的比较次数不会超过 N 的若干倍乘于递增序列的长度。后面介绍的高级排序算法只会比希尔排序快两倍左右。
归并排序
归并排序的思想是将数组分成两部分，分别进行排序，然后归并起来。
  


1. 归并方法
归并方法将数组中两个已经排序的部分归并成一个。
public abstract class MergeSort<T extends Comparable<T>> extends Sort<T> {

    protected T[] aux;


    protected void merge(T[] nums, int l, int m, int h) {

        int i = l, j = m + 1;

        for (int k = l; k <= h; k++) {
            aux[k] = nums[k]; // 将数据复制到辅助数组
        }

        for (int k = l; k <= h; k++) {
            if (i > m) {
                nums[k] = aux[j++];

            } else if (j > h) {
                nums[k] = aux[i++];

            } else if (aux[i].compareTo(aux[j]) <= 0) {
                nums[k] = aux[i++]; // 先进行这一步，保证稳定性

            } else {
                nums[k] = aux[j++];
            }
        }
    }
}

2. 自顶向下归并排序
将一个大数组分成两个小数组去求解。
因为每次都将问题对半分成两个子问题，这种对半分的算法复杂度一般为 O(NlogN)。
public class Up2DownMergeSort<T extends Comparable<T>> extends MergeSort<T> {

    @Override
    public void sort(T[] nums) {
        aux = (T[]) new Comparable[nums.length];
        sort(nums, 0, nums.length - 1);
    }

    private void sort(T[] nums, int l, int h) {
        if (h <= l) {
            return;
        }
        int mid = l + (h - l) / 2;
        sort(nums, l, mid);
        sort(nums, mid + 1, h);
        merge(nums, l, mid, h);
    }
}

3. 自底向上归并排序
先归并那些微型数组，然后成对归并得到的微型数组。
public class Down2UpMergeSort<T extends Comparable<T>> extends MergeSort<T> {

    @Override
    public void sort(T[] nums) {

        int N = nums.length;
        aux = (T[]) new Comparable[N];

        for (int sz = 1; sz < N; sz += sz) {
            for (int lo = 0; lo < N - sz; lo += sz + sz) {
                merge(nums, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
            }
        }
    }
}


快速排序
1. 基本算法

归并排序将数组分为两个子数组分别排序，并将有序的子数组归并使得整个数组排序；
快速排序通过一个切分元素将数组分为两个子数组，左子数组小于等于切分元素，右子数组大于等于切分元素，将这两个子数组排序也就将整个数组排序了。

  


public class QuickSort<T extends Comparable<T>> extends Sort<T> {

    @Override
    public void sort(T[] nums) {
        shuffle(nums);
        sort(nums, 0, nums.length - 1);
    }

    private void sort(T[] nums, int l, int h) {
        if (h <= l)
            return;
        int j = partition(nums, l, h);
        sort(nums, l, j - 1);
        sort(nums, j + 1, h);
    }

    private void shuffle(T[] nums) {
        List<Comparable> list = Arrays.asList(nums);
        Collections.shuffle(list);
        list.toArray(nums);
    }
}


2. 切分
取 a[l] 作为切分元素，然后从数组的左端向右扫描直到找到第一个大于等于它的元素，再从数组的右端向左扫描找到第一个小于它的元素，交换这两个元素。不断进行这个过程，就可以保证左指针 i 的左侧元素都不大于切分元素，右指针 j 的右侧元素都不小于切分元素。当两个指针相遇时，将切分元素 a[l] 和 a[j] 交换位置。
  


private int partition(T[] nums, int l, int h) {
    int i = l, j = h + 1;
    T v = nums[l];
    while (true) {
        while (less(nums[++i], v) && i != h) ;
        while (less(v, nums[--j]) && j != l) ;
        if (i >= j)
            break;
        swap(nums, i, j);
    }
    swap(nums, l, j);
    return j;
}


3. 性能分析
快速排序是原地排序，不需要辅助数组，但是递归调用需要辅助栈。
快速排序最好的情况下是每次都正好将数组对半分，这样递归调用次数才是最少的。这种情况下比较次数为 CN=2CN/2+N，复杂度为 O(NlogN)。
最坏的情况下，第一次从最小的元素切分，第二次从第二小的元素切分，如此这般。因此最坏的情况下需要比较 N2/2。为了防止数组最开始就是有序的，在进行快速排序时需要随机打乱数组。
4. 算法改进
4.1 切换到插入排序
因为快速排序在小数组中也会递归调用自己，对于小数组，插入排序比快速排序的性能更好，因此在小数组中可以切换到插入排序。
4.2 三数取中
最好的情况下是每次都能取数组的中位数作为切分元素，但是计算中位数的代价很高。一种折中方法是取 3 个元素，并将大小居中的元素作为切分元素。
4.3 三向切分
对于有大量重复元素的数组，可以将数组切分为三部分，分别对应小于、等于和大于切分元素。
三向切分快速排序对于有大量重复元素的随机数组可以在线性时间内完成排序。
public class ThreeWayQuickSort<T extends Comparable<T>> extends QuickSort<T> {

    @Override
    protected void sort(T[] nums, int l, int h) {
        if (h <= l) {
            return;
        }
        int lt = l, i = l + 1, gt = h;
        T v = nums[l];
        while (i <= gt) {
            int cmp = nums[i].compareTo(v);
            if (cmp < 0) {
                swap(nums, lt++, i++);
            } else if (cmp > 0) {
                swap(nums, i, gt--);
            } else {
                i++;
            }
        }
        sort(nums, l, lt - 1);
        sort(nums, gt + 1, h);
    }
}


5. 基于切分的快速选择算法
快速排序的 partition() 方法，会返回一个整数 j 使得 a[l…j-1] 小于等于 a[j]，且 a[j+1…h] 大于等于 a[j]，此时 a[j] 就是数组的第 j 大元素。
可以利用这个特性找出数组的第 k 个元素。
该算法是线性级别的，假设每次能将数组二分，那么比较的总次数为 (N+N/2+N/4+…)，直到找到第 k 个元素，这个和显然小于 2N。
public T select(T[] nums, int k) {
    int l = 0, h = nums.length - 1;
    while (h > l) {
        int j = partition(nums, l, h);

        if (j == k) {
            return nums[k];

        } else if (j > k) {
            h = j - 1;

        } else {
            l = j + 1;
        }
    }
    return nums[k];
}


堆排序
1. 堆
堆中某个节点的值总是大于等于其子节点的值，并且堆是一颗完全二叉树。
堆可以用数组来表示，这是因为堆是完全二叉树，而完全二叉树很容易就存储在数组中。位置 k 的节点的父节点位置为 k/2，而它的两个子节点的位置分别为 2k 和 2k+1。这里不使用数组索引为 0 的位置，是为了更清晰地描述节点的位置关系。
  


public class Heap<T extends Comparable<T>> {

    private T[] heap;
    private int N = 0;

    public Heap(int maxN) {
        this.heap = (T[]) new Comparable[maxN + 1];
    }

    public boolean isEmpty() {
        return N == 0;
    }

    public int size() {
        return N;
    }

    private boolean less(int i, int j) {
        return heap[i].compareTo(heap[j]) < 0;
    }

    private void swap(int i, int j) {
        T t = heap[i];
        heap[i] = heap[j];
        heap[j] = t;
    }
}


2. 上浮和下沉
在堆中，当一个节点比父节点大，那么需要交换这个两个节点。交换后还可能比它新的父节点大，因此需要不断地进行比较和交换操作，把这种操作称为上浮。
  


private void swim(int k) {
    while (k > 1 && less(k / 2, k)) {
        swap(k / 2, k);
        k = k / 2;
    }
}


类似地，当一个节点比子节点来得小，也需要不断地向下进行比较和交换操作，把这种操作称为下沉。一个节点如果有两个子节点，应当与两个子节点中最大那个节点进行交换。
  


private void sink(int k) {
    while (2 * k <= N) {
        int j = 2 * k;
        if (j < N && less(j, j + 1))
            j++;
        if (!less(k, j))
            break;
        swap(k, j);
        k = j;
    }
}


3. 插入元素
将新元素放到数组末尾，然后上浮到合适的位置。
public void insert(Comparable v) {
    heap[++N] = v;
    swim(N);
}


4. 删除最大元素
从数组顶端删除最大的元素，并将数组的最后一个元素放到顶端，并让这个元素下沉到合适的位置。
public T delMax() {
    T max = heap[1];
    swap(1, N--);
    heap[N + 1] = null;
    sink(1);
    return max;
}


5. 堆排序
把最大元素和当前堆中数组的最后一个元素交换位置，并且不删除它，那么就可以得到一个从尾到头的递减序列，从正向来看就是一个递增序列，这就是堆排序。
5.1 构建堆
无序数组建立堆最直接的方法是从左到右遍历数组进行上浮操作。一个更高效的方法是从右至左进行下沉操作，如果一个节点的两个节点都已经是堆有序，那么进行下沉操作可以使得这个节点为根节点的堆有序。叶子节点不需要进行下沉操作，可以忽略叶子节点的元素，因此只需要遍历一半的元素即可。
  


5.2 交换堆顶元素与最后一个元素
交换之后需要进行下沉操作维持堆的有序状态。
  


public class HeapSort<T extends Comparable<T>> extends Sort<T> {
    /**
     * 数组第 0 个位置不能有元素
     */
    @Override
    public void sort(T[] nums) {
        int N = nums.length - 1;
        for (int k = N / 2; k >= 1; k--)
            sink(nums, k, N);

        while (N > 1) {
            swap(nums, 1, N--);
            sink(nums, 1, N);
        }
    }

    private void sink(T[] nums, int k, int N) {
        while (2 * k <= N) {
            int j = 2 * k;
            if (j < N && less(nums, j, j + 1))
                j++;
            if (!less(nums, k, j))
                break;
            swap(nums, k, j);
            k = j;
        }
    }

    private boolean less(T[] nums, int i, int j) {
        return nums[i].compareTo(nums[j]) < 0;
    }
}


6. 分析
一个堆的高度为 logN，因此在堆中插入元素和删除最大元素的复杂度都为 logN。
对于堆排序，由于要对 N 个节点进行下沉操作，因此复杂度为 NlogN。
堆排序是一种原地排序，没有利用额外的空间。
现代操作系统很少使用堆排序，因为它无法利用局部性原理进行缓存，也就是数组元素很少和相邻的元素进行比较和交换。
小结
1. 排序算法的比较




算法
稳定性
时间复杂度
空间复杂度
备注




选择排序
×
N2
1



冒泡排序
√
N2
1



插入排序
√
N ~ N2
1
时间复杂度和初始顺序有关


希尔排序
×
N 的若干倍乘于递增序列的长度
1
改进版插入排序


快速排序
×
NlogN
logN



三向切分快速排序
×
N ~ NlogN
logN
适用于有大量重复主键


归并排序
√
NlogN
N



堆排序
×
NlogN
1
无法利用局部性原理


快速排序是最快的通用排序算法，它的内循环的指令很少，而且它还能利用缓存，因为它总是顺序地访问数据。它的运行时间近似为 ~cNlogN，这里的 c 比其它线性对数级别的排序算法都要小。
使用三向切分快速排序，实际应用中可能出现的某些分布的输入能够达到线性级别，而其它排序算法仍然需要线性对数时间。
2. Java 的排序算法实现
Java 主要排序方法为 java.util.Arrays.sort()，对于原始数据类型使用三向切分的快速排序，对于引用类型使用归并排序。

相关分析：是研究两个或两个以上变量之间相关程度大小以及用 一定函数表达现象相关关系的的方法

相关分析的作用： 

1.确定现象之间有有无关系 

2.确定相关关系的密切程度和方向

相关关系的种类： 

按相关关系的程度：不相关、完全相关、不完全相关 

按相关关系方向：正相关、负相关

相关关系的判断 

1.一般判断（定性分析） 

2.散点图

相关系数（r） 

|r|表明两变量之间的相关程度

斯皮尔曼等级相关系数