比较型排序算法总结

排序是算法中最基础的问题之一，经典的排序算法是前人不断总结得到的，基于比较的方法是比较直观的方式，主要存在插入法排序、堆排序、增量排序（shell排序）、归并排序、快速排序，每一种排序算法都有自己的优缺点，比如插入法排序适用于那些长度短的排序，对于长的表，有些爱莫能助啊，堆排序主要是依据了二叉堆的特性，但是创建堆的过程也是一个复杂的问题，增量排序的过程是一个不断精确的过程，但是目前也只是一个经验方式。归并排序是一个递归的问题，采用分治的思想实现，但是这种算法需要额外的存储空间，快速排序虽然是实践中比较常用的算法，但是对于有序的数组采用快速排序就是灾难。比较型算法的时间复杂度最优也只能到达O(NlogN)。

插入排序算法：该算法的复杂度为O(N^2),需要比对N-1趟，最坏情况下，每一趟比对的元素个数会随着i的增加而增加。比如进行到了第k+1趟，实际上就是假设了前k个元素是有序的，这时候只需要将a[k+1]与a[k]比较，如果a[k+1]大于a[k]则说明a[k+1]是目前最大的数，如果a[k+1] < a[k].这时说明a[k]的位置不对，需要往后移动，也就是a[k+1]中保存a[k]的值，可以将a[k+1]的值与a[k]交换。然后比较a[k]与a[k-1]，直到找到该元素的合适位置。

void insertSort(int *a, int size)
{
int i = 0, j = 0, tmp = 0;
for(i = 1; i < size; ++ i)
{
tmp = a[i];
for(j = i; j > 0 && tmp < a[j-1]; --j)
a[j] = a[j - 1];
a[j] = tmp;
}
}

增量排序(shell 排序)：该算法的复杂度要略小于插入排序算法，但是也基本上认为是亚O(N^2)。实现的基本过程如下，选择一个较大的增量gap，一般选择为数组长度的一般作为起始的增量。然后从当前增量作为起始下标开始访问，比较a[i]和a[i-gap],如果a[i] a[0]，这是已经处理过的。如果a[i] > a[i-gap]则不处理。减小gap,一般去gap = gap/2。重新进行上面的操作，直到gap = 1，因为这时候已经满足a[i]

voidshellSort(int *a, int size)
{
int i = 0, j = 0, gap = 0.
int tmp = 0;

/*选择合适的增量*/
for(gap = size / 2; gap > 0; gap /= 2 )
{
/*以增量为下标进行比较*/
for( i = gap ; i < size ; ++ i)
{
/*找到比较数的位置*/
tmp = a[i];
for(j = i; j >= gap && tmp < a[j - gap]; j -= gap)
a[j] = a[j - gap];/*更新a[j-gap]的位置*/
a[j] = tmp; /*找到比较数的位置*/
}
}
}

堆排序：堆排序的实现主要是采用了最小堆或者最大堆的特性，堆中的根元素肯定是最小元素或者最大元素，删除其中的根元素实质上就找到了最大/最小值。这样通过N次删除就找到了一个有序序列。我们知道在二叉堆中删除和插入操作采用了上虑和下虑的方式，每次删除和插入操作的时间复杂度为O(logN)。但是堆排序存在一个堆的创建问题，这个创建是非常的浪费时间的，时间复杂度为O(N)，这样一个堆排序的操作事件大约为O(NlogN)。相比前面的两种方式要快速。实现的过程如下，分配一个新的内存空间，遍历元素N，创建一个二叉堆数组，然后执行N次删除操作，删除的元素添加到原来的内存空间中，实现了数组的排序操作，这种方式时间复杂度上有所减小，但是空间复杂度上却有了很大的增加，存储容量增加了近一倍。

聪明的解决方式根据堆的性质，删除一个元素就会释放最后的一个存储单元，这时候将删除的元素保存到释放存储单元中，然后删除一个元素就保存到释放的内存中去，就能避免存储量增加的问题。但是这时候出现的序列就是一个反序，但总归是有序序列。当然也可以通过创建(Max)堆来得到min序列，创建(Min)堆来得到max序列。因此堆排序的基本模型就是创建一个堆，删除堆元素的操作过程。

堆排序是非常稳定的算法，他平均使用的比较只比最坏情形下指出的略少，堆排序总是使用至少NlogN-O(N)次排序，而且存在能够到达这个界的输入数据。

void max_heapify(int *a,int index, int size)
{
int child = LEFTSON(index);

int tmp = a[index];

for(; LEFTSON(index) < size ; index = child)
{
child = LEFTSON(index);
if(child != size - 1 && a[child] < a[child + 1])
child ++;

/***************************
* 提升儿子到父结点，
* 儿子结点的位置上存在空穴，
* 需要继续比较
**************************/
if(a[child] > tmp)
a[index] = a[child];
else/*不需要提升*/
break;
}
/*保存结点的位置找到*/
a[index] = tmp;
}

void Build_Maxheap(int *a, int size)
{
int step = 0;

/***************************************
* (size-1)/2实质是找到a[size-1]的父结点，
* 也就是倒数第二层，堆的创建过程是一个
* 由低层到高层逐渐创建的过程
**************************************/
for(step = (size - 1) / 2 ; step >= 0; -- step)
max_heapify(a, step, size);
}