比较型排序算法总结

    排序是算法中最基础的问题之一，经典的排序算法是前人不断总结得到的，基于比较的方法是比较直观的方式，主要存在插入法排序、堆排序、增量排序（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],如果则交换两个值，并令i = i - gap，交换完成以后接着比较a[i] < a[i-gap]，直到 i < gap，因为a[gap] > a[0]，这是已经处理过的。如果a[i] > a[i-gap]则不处理。减小gap,一般去gap = gap/2。重新进行上面的操作，直到gap = 1，因为这时候已经满足a[i]实现了基本的排序操作。依据的基本关系式为a[i] < a[i + gap]，这个关系式说明了a[i], a[i+gap], a[i+2gap],a[i+3gap],…是一个有序的序列。

void shellSort(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);
}

void heapSort(int *a, int size)
{
        int i = 0;
        /*创建堆*/
        Build_Maxheap(a,size);

        for(i = size - 1; i > 0; --i)
        {
                /*swap(a[i],a[0])*/
                a[i] = a[i] + a[0];
                a[0] = a[i] - a[0];
                a[i] = a[i] - a[0];
                /*更新堆的结构*/
                max_heapify(a,0,i);
        }
}

    归并排序：该算法的时间复杂度为O(NlogN)，使用的比较次数几乎是最优的，是递归算法的经典例子。

这个算法的基本操作是合并两个已经排序的表，因为这两个表是已经排序的，所以若将输出放到第三个表中则该算法可以通过对输入数据一趟排序来完成。基本的合并算法是取两个输入数组A和B，一个输出数组C以及3个计数器(Actr、Bctr、Cctr)，他们开始于对应数组的开始端，A[Actr]和B[Bctr]的较小者复制到C[ctr]中的一下一个位置，相关的计数器向前推进一步，当两个输入表有一个用完，则将另一个表中剩余的部分拷贝到C中。

由于该算法的前提是两个已经排序的表，但实际上的输入肯定不能满足条件，因此需要采用分治策略，所谓“分”就是将输入表分成两个表进行处理，对两个表分别采用分治进行排序。所谓“治”就是按照上述的算法合并两个排序表得到一个完整的排序表。由上面的分析可以知道，每一次分治都存在分开和合并操作，是经典的递归问题。需要注意的是在归并算法中临时数组的处理问题，采用动态存储的方式可能要简单好一些，但是需要注意内存的释放，避免内存泄露。

void mergeSort(int * a, int left, int right)
{
        int i = 0;
        int *atmp = NULL;
        int *Actr = NULL, *Bctr = NULL, *Cctr = NULL;

        /*递归退出条件*/
        if(left >= right)
                return;

        atmp = (int *)calloc((right - left + 1) / 2,sizeof(int));
        if(NULL == atmp)
                return;

        for(i = 0; i < (right - left + 1) / 2 ; ++ i)
                atmp[i] = a[left + i];

        mergeSort(atmp,0,i - 1);
        mergeSort(a, left + i, right);

        Actr = atmp;
        Bctr = a + left + i;
        Cctr = a + left;

        while(Actr != atmp + i && Bctr != a + right + 1)
        {
                if(*Actr <= *Bctr)
                        *Cctr++ = *Actr++;
                else
                        *Cctr++ = *Bctr++;
        }
        while(Actr != atmp + i)
                *Cctr ++ = *Actr++;
        while(Bctr != a + right + 1)
                *Cctr ++ = *Bctr ++;

        free(atmp);
        atmp = NULL;
}

    归并算法的时间复杂度的推导过程：

其中时间复杂度公式满足如下的等式T(N)=2T(N/2)+N，其中的N为合并操作的时间，推导过程如下:

    归并排序存在的问题是，它很难应用于主存排序，主要问题在于合并两个排列的表需要线性附加内存，在整个算法中还需要花费将数据复制到临时数组在复制回来这样的一些附加操作，其结果是严重减慢了排序的速度。

    快速排序：是实践中最快的已知排序算法，它的平均运行时间是O(NlogN)，算法之所以快是因为非常精炼和高度优化的内部循环，但是最坏的性能是O(N^2),将堆排序与快速排序结合，可以在堆排序的O(NlogN)最坏运行时间下，得到几乎所有输入的最快运行时间。

快速排序也是一种分治的递归算法，通常包括4个步骤：

        1、如果数组S中元素个数为0或者1个，则直接返回

        2、取数组S中的一个数v作为枢纽元。

        3、将数组S-v划分成两个不相交的集合，其中S1:x <= v, S2: x > v.这一步需要注意不要写成是S1:x<=v,S2:x>=v，能减少很多的麻烦。

        4、返回{quickSort(S1) , v, quickSort(S2)}。

上面的四步就完成了数组的快速排序，可见快速排序也是一个递归的过程，需要将多个子集进行。

    快速排序的实现主要是第三步的实现，如何实现将数据分成两个集合的操作。实现的方式如下：

假设选择的枢纽元pivot是数组的开始值a[0]，那么将两个下标i,j分别表示数组的第1个数a[1](i = 1)和最后一个数a[N](j = N)，如果i < j，也就是数组长度大于2个时，将指向第一个数a[1]和枢纽元pivot进行比较，如果小于等于枢纽元则说明当前值是S1集合的，因此不需要移动，增加i指向下一个数a[2]，直到找到大于枢纽元的数a[i]，则i暂停增加，这时操作另一个下标j，比较j表征的数a[j]是否大于枢纽元pivot，如果大于则说明当前的数属于S2，不需要移动，减小j，直到找到小于等于枢纽元的数a[j]，如果i < j，则说明这两个数是需要改变位置的，因此调整两个数的位置swap(a[p],a[q])，然后接着上面的方法移动两个下标，并完成相应的交换操作，当两个下标表征相同的位置(j == i，这种情况是pivot = a[i])或者j < i(这种情况是不存在相同元素pivot != a[i])以后，说明集合分类操作已经完成，后一个j指向的位置就是当前枢纽元的位置，这时候小于j的下标的数据就是S1,而大于j的下标的数据就是S2。因此还需要将枢纽元a[0]与a[j]交换，得到枢纽元的位置。对于这种数组元素较大的情况，此时的j一般认为都是满足a[j] <= pivot。（等于的情况也是可能存在的）。

但是存在一个特殊情况，如果操作的数组只存在两个数据时，这种划分方法就存在一些问题，因为一开始两个下标i,j就指向了相同的位置，这时候如果a[0]大于a[1] ，那么经过上面的操作以后j = 0, i = 1，这时候的pivot应该是放在a[1]处，但是根据上面的条件可知，集合划分至少需要三个元素，但是我们可以比较枢纽元与当前a[j]的值，对于两种情况下都满足交换的条件就是a[j] < pivot,因此只要当这个条件满足是就交换a[j]和a[0]。上述的操作我们称之为集合划分操作。

int Partition(int *a, int left, int right)
{
        /*采用第一个元素作为枢纽元*/
        int pivot = a[left];
        int i = left + 1;
        int j = right;

        /*只有一个元素，实际上不用进行任何操作，直接返回*/
        if(i > j)
                return j;

        /*实际上存在一个问题就是i== j，这时候数组有两个值*/
        while(1)
        {
                /*跳过所有小于等于pivot的值，同时设置边界条件*/
                while(a[i] <= pivot && i < right)
                        ++ i ;
                /*跳过所有大于pivot的值，同时设置边界条件*/
                while(pivot < a[j] && j > left)
                        -- j ;
                /*******************************************
                 *如果 i < j，则说明数组之间存在间隔
                 *上面的条件全部不满足则说明找到S1，S2需要交换的数
                 *一般当存在相同的数时，会存在i == j，这时实际上
                 *a[left] = a[j]
                 *一般都会产生i > j,这种情况发生在i+1=j时的交换操作
                 *交换操作完成以后i++,j--，使得i < j.
                 *******************************************/
                if(i < j)
                        swap(&a[i ],&a[j]);
                else
                        break;
        }
        /******************************************************
        根据上面的分析实际上j下标指向的数数都是小于或者等于pivot的
        等于pivot时就不需要交换a[left]和a[j],只需要返回枢纽元应该的位置即可，
        同时也解决了只有两个数值的数组问题。
        *******************************************************/
        if(pivot > a[j])
                swap(&a[left],&a[j]);
        /*返回枢纽元应该存在的位置*/
        return j;
}

/*传统的快速排序算法*/
void t_quickSort(int *a, int left, int right)
{
        int i = 0;

        /*如果left小于right*/
        if(left < right)
        {
                 /*找到枢纽元的位置，并划分了两个集合S1,S2*/
                i = Partition(a,left,right);
                 /*S1集合排序*/
                t_quickSort(a, left , i - 1);
                /*S2集合排序*/
                t_quickSort(a, i + 1, right);
        }
}

    但是这种方法存在一个比较严重的问题，就是如果当数组是一个已经完成排序的情况，采用快速排序的时间复杂度将是灾难性的。此时的时间复杂度为O(N^2),也就是最坏的情况，为了解决这种问题，采用了其他的解决方案，改变枢纽元的选择决策，采用随机选取或者三值的中值作为枢纽元。枢纽元的选择能避免有序数组的快速排序问题。还有就是当数组的长度较小时，采用插入法等常规方法的速度更快，而且如上面分析所示，划分集合的问题至少需要三个元素，虽然上面的方法能够解决只有两个元素的情况，但是如果考虑不周全就很难解决。可以根据长度来选择具体的排序排序方法，也就是当长度小于10时采用插入法排序，而当大于10时就直接采用快速排序，这时候的注意事项就比较少，不用考虑数组长度是否为2等。采用改良型的快速排序算法如下所示。

/*快速排序*/
void insertionSort(int *a, int left, int right)
{
    int i = 0, j = 0;
    int tmp = 0;
    if(left >= right)
        return;

    for( i = left + 1; i <= right; ++ i)
    {
        tmp = a[i];
        for(j = i; j > left && tmp < a[j - 1]; -- j)
            a[j] = a[j - 1];
        a[j] = tmp;
    }
}

/*数据交换*/
void swap(int *a, int *b)
{
    if(a != b)
    {
        *a = *a + *b;
        *b = *a - *b;
        *a = *a - *b;
    }
}

/*选择合适的枢纽元函数*/
int median(int *a, int left, int right)
{
    int mid = (right + left) / 2;

    if(a[mid] < a[left])
        swap(&a[mid], &a[left]);
    if(a[right] < a[left])
        swap(&a[right], &a[left]);
    if(a[right] < a[mid])
        swap(&a[right], &a[mid]);

    swap(&a[mid],&a[right - 1]);

    return a[right - 1];
}

/*实现快速排序的实际函数*/
void quickSort(int *a, int left, int right)
{
    int i = left, j = right - 1;
    int pivot = 0;
    if(left + 10 <= right)
    {
        /*选择枢纽元*/
        pivot = median(a,left,right);

        while(1)
        {
            /*找到大于pivot的下标*/
            while(a[++ i] <= pivot){}
            /*找到不大于pivot的下标*/
            while(a[--j] > pivot){}

            if(i < j)
                swap(&a[i],&a[j]);
            else
                break;
        }
        /*确定枢纽元的位置*/
        swap(&a[i],&a[right - 1]);
        quickSort(a,left,i - 1);
        quickSort(a,i + 1,right);
    }
    else/*小长度的数组采用插入法排序*/
        insertionSort(a, left,right);
}

void QuickSort(int *a, int size)
{
    quickSort(a,0,size - 1);
}

时间复杂度的测试，首先测试有序数组的排序操作，测试代码和算法效果如下所示：

#define LEN 100000

int main()
{
        int i = 0;
        int a[LEN];
        int b[LEN];
        int c[LEN];
        int d[LEN];
        int e[LEN];
        clock_t _start, _end;
        double times = 0;

        srand((int)time(0));

        for(i = 0; i < LEN; ++ i)
        {
                a[i] = i;
                b[i] = a[i];
                c[i] = a[i];
                d[i] = a[i];
                e[i] = a[i];
        }

        _start = clock();
        TQuickSort(a,LEN);
        _end = clock();
        times = (double)(_end - _start)/CLOCKS_PER_SEC;
        printf("The QuickSort took %fs\n",times);
        _start = clock();
        QuickSort(b,LEN);
        _end = clock();
        times = (double)(_end - _start)/CLOCKS_PER_SEC;
        printf("The Changed QuickSort took %fs\n",times);
#if 10
        _start = clock();
        MergeSort(c,LEN);
        _end = clock();
        times = (double)(_end - _start)/CLOCKS_PER_SEC;
        printf("The MergeSort took %fs\n",times);

        _start = clock();
        InsertionSort(d,LEN);
        _end = clock();
        times = (double)(_end - _start)/CLOCKS_PER_SEC;
        printf("The InsertionSort took %fs\n",times);

        _start = clock();
        heapSort(e,LEN);
        _end = clock();
        times = (double)(_end - _start)/CLOCKS_PER_SEC;
        printf("The heapSort took %fs\n",times);
#endif
        return 0;
}

结果如下：

[gong@Gong-Computer sort]$ ./quickSort
The QuickSort took 12.850000s
The Changed QuickSort took 0.000000s
The MergeSort took 0.030000s
The InsertionSort took 0.000000s
The heapSort took 0.020000s

    从上面的实验结果可知，当为有序数组时，快速排序的速度并不快，甚至是最慢的。插入排序反而是最快的方式。同时我们可以发现采用上面的改进的快速排序算法排序速度很快，并不像传统的算法那么费时间。
    测试采用随机数产生的数组进行排序时的实验效果：

[gong@Gong-Computer sort]$ ./quickSort
The QuickSort took 0.020000s
The Changed QuickSort took 0.010000s
The MergeSort took 0.030000s
The InsertionSort took 15.240000s
The heapSort took 0.020000s

    从上面的结果可知，对于非有序的数组，快速排序的效果是非常好的，但是插入排序就非常的差劲啦。