排序算法
一、冒泡排序
思路：冒泡排序算法需要遍历几次数组。每次遍历都要比较连续相邻的元素，如果某一对相邻元素是降序，则互换它们的值，否则，保持不变。由于较小的值像“气泡”一样逐渐浮想顶部，而较大的值沉向底部，所以叫冒泡排序。平均时间复杂度为O(n^2)。
最差的情况下，冒泡排序算法需要进行n-1次遍历。第一次遍历需要n-1次比较，第二次遍历需要n-2次比较，依次进行；因此比较总数为：
(n-1)+(n-2)+...+2+1=n(n-1)/2=O(n2)
最差的情况冒泡排序的时间复杂度为O(n^2)。
冒泡算法的改进：
冒泡排序的效率比较低，所以我们要通过各种方法改进。在上例中，第四轮排序之后实际上整个数组已经是有序的了，最后两轮的比较没必要进行。
注意：如果某次遍历中没有发生交换，那么就不必进行下一次遍历，因为所有元素已经排好了。
所以最好的情况是数据本来就有序，复杂度为O(n)。
平均时间复杂度为O(n^2)， 最差的情况冒泡排序的时间复杂度为O(n^2)，最好的情况是数据本来就有序，复杂度为O(n)。
算法是稳定的，因为当a=b时，由于只有大于才做交换，故a和b的位置没有机会交换，所以算法稳定。
空间复杂度为O(1)，不需要额外空间。
二、选择排序
思路：选择排序改进了冒泡排序，将必要的交换次数从O(n2)减少到O(n)，但是比较次数仍保持为O(n2)。冒泡排序每比较一次就可能交换一次，但是选择排序是将一轮比较完后，把最小的放到最前的位置（或者把最大的放到最后）。
算法分析：选择排序最好和最坏的情况一样运行了O(N2)时间，平均复杂度也是O(N2)。
算法是不稳定的，假设a=b，且a在b前面，而某轮循环中最小值在b后面，而次最小值需要跟a交换，这时候b就在a前面了，所以选择排序是不稳定的。
空间复杂度为O(1)，不需要额外的空间。
三、插入排序
四、快速排序
思路：虽然快速排序称为分治法，但分治法这三个字显然无法很好的概括快速排序的全部步骤。比较完整的来说应该是：挖坑填数+分治法：
挖坑填数的说明：L：最左边索引，R：最右边索引
1．i =L; j = R; 将基准数即最左边第一个数挖出形成第一个坑a[i]。
while循环{
2．j--由后向前找比基准数小的数，找到后挖出此数填前一个坑a[i]中。
3．i++由前向后找比基准数大的数，找到后也挖出此数填到前一个坑a[j]中。
}
4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。
5.这样整个数据中就被基准数分为了两个区间，左边比它小，右边比它大。
分治法说明：再通过递归对左右区间重复第二步，直到各区间只有一个数。
完整的代码如下：
//快速排序：挖坑填数+分治法
void fastSort(int *arr, int left, int right)
{
if (left<right && arr!=NULL) {
int i = left;//left、right要保留，最后要用
int j = right;
int key = arr[left];
/******挖坑填数******/
//每个大while循环：对left作为基准值进行了分区，小的放在了左边，大的放在了右边
while (i<j) {
while (i<j && arr[j]>=key) {
j--;
}
arr[i]=arr[j];//拿j(后边)的数填到i（前边）的坑里
while (i<j && arr[i]<=key) {
i++;
}
arr[j]=arr[i];//拿i(前边)的数填到j(后边)的坑里
}
arr[i]=key;
/******挖坑填数******/
/******分治法******/
fastSort(arr, left, i-1);
fastSort(arr, i+1, right);
/******分治法******/
}
}
1、n大时好，快速排序比较占用内存，内存随n的增大而增大，但却是效率高不稳定的排序算法。
2、最差的情况是本身是有序数组，划分之后一边是一个，一边是n-1个，这种极端情况的时间复杂度就是O(N^2)。最坏的情况下退化成插入排序了。
3、最好的情况是每次都能均匀的划分序列，O(N*log2N)。
五、归并排序
思路：将待排序序列R[0...n-1]看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。
那么归并是如何进行的呢？
我们称 R[low, mid] 第一段，R[mid+1, high] 为第二段。每次从两个段中取出一个记录进行关键字的比较，将较小者放入R2中。最后将各段中余下的部分直接复制到R2中。经过这样的过程，R2已经是一个有序的序列，再将其复制回R中，一次合并排序就完成了。
//辅助函数
void merge(int *arr, int *tmp, int start, int mid, int end)
{
int i = start;
int j = mid+1;
int tmpIndex = start;
//注意:两个分组的意思，其实自始至终都是在原数组中，只是通过index我们把它看成了两个分组
while (i<=mid && j<=end) {//两个分组从第一个开始对比，谁小谁先放进新数组中，直到有一个分组没有数据了
if (arr[i]<=arr[j]) {
tmp[tmpIndex] = arr[i];
tmpIndex++;
i++;
}
else
{
tmp[tmpIndex] = arr[j];
tmpIndex++;
j++;
}
}
//前一个分组没放完，把剩余的直接都放到新数组后面即可
while (i<=mid) {
tmp[tmpIndex] = arr[i];
tmpIndex++;
i++;
}
//后一个分组没放完，把剩余的直接都放到新数组后面即可
while (j<=end) {
tmp[tmpIndex] = arr[j];
tmpIndex++;
j++;
}
//把新数组里的排好序的放回到原数组中
while (start<=end) {
arr[start] = tmp[start];
start++;
}
}
//归并排序入口
void mergeSort(int *arr,int length)
{
int tmp[length];
int gap = 1;//每组有几个
while (gap < length) {
int start = 0;
for (start = 0; start+2*gap-1 < length; start=start+2*gap) {
merge(arr, tmp, start, start+gap-1, start+2*gap-1);
}
//此时，说明后边还有数据（情况1：两个分组，后边那个分组，不满gap；情况2：只有一个分组）
if (start+gap-1<length) {
merge(arr, tmp, start, start+gap-1, length-1);
}
gap = 2*gap;
}
}
归并排序的形式就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的可以得出它的时间复杂度是O(n*log2n)。
归并排序是稳定的。
六、堆排序
若从空间复杂度来考虑：首选堆排序，其次是快速排序，最后是归并排序。
若从稳定性来考虑，应选取归并排序，因为堆排序和快速排序都是不稳定的。
若从平均情况下的排序速度考虑，应该选择快速排序。
