堆排序、快速排序、归并排序总结

2012-09-21 11:33:41| 分类：算法、数据结构 | 标签：算法数据结构归并排序内部排序面试 |举报 |字号大中小订阅

这三个排序以前都写过，快速排序还写了递归版和迭代版。现在在这里做一下总结。

堆排序（Heap Sort）

堆排序是一种树形选择排序，在排序过程中，将A[n]看成是完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。对N个元素从小到大排序建立大根堆，然后交换堆顶与最后一个元素，将剩下的N-1个元素调整为大根堆，执行N-1此这样的操作。堆排序是不稳定的。算法时间复杂度O(nlogn)。

[cpp]view plaincopyprint? 
//调整大根堆  
void HeapAdjust(int data[],int nStart, int nLen)  
{  
    int nMaxChild = 0;  
    int Temp;  
  
    while ((2*nStart+1) < nLen)  
    {  
        nMaxChild = 2*nStart+1;  
        if ( (2*nStart+2) < nLen)  
        {  
            //比较左子树和右子树,记录最大值的Index  
            if (data[2*nStart+1] < data[2*nStart+2])  
            {  
                nMaxChild = 2*nStart+2;  
            }  
        }  
        //change data  
        if (data[nStart] < data[nMaxChild])  
        {  
            //交换nStart与nMaxChild的数据  
            Temp = data[nStart];  
            data[nStart] = data[nMaxChild];  
            data[nMaxChild] = Temp;  
  
            //堆被破坏,需要重新调整  
            nStart = nMaxChild;  
        }  
        else  
        {  
            //比较左右孩子均小则堆未破坏,不再需要调整  
            break;  
        }  
    }  
}  
  
//堆排序 从小到大排序建立大顶堆  
void HeapSort(int data[],int nLen)  
{  
    int i;  
    int nTemp;  
    //建立堆  
    for (i = nLen/2-1; i >= 0; i--)  
    {  
        HeapAdjust(data, i, nLen);  
    }  
    for (i = nLen-1; i > 0; i--)  
    {  
        //交换堆顶元素和最后一个元素  
        nTemp = data[0];  
        data[0] = data[i];  
        data[i] = nTemp;  
  
        //将data[0...i]重写建成大根堆  
        HeapAdjust(data, 0, i);  
    }  
}  

快速排序（Quick Sort）

快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。

快速排序是不稳定的。最理想情况算法时间复杂度O(nlog2n)，最坏O(n^2)。

[cpp]view plaincopyprint? 
//快速排序  
void QuickSort(int a[], int low, int high)  
{  
    if (low < high)  
    {  
        // 划分  
        int pivot = a[low];  
        int i = low; int j = high;  
        while (i < j)  
        {  
            while (i<j && a[j] >= pivot)  j--;  
            a[i] = a[j];  
            while (i<j && a[i] <= pivot)  i++;  
            a[j] = a[i];  
        }  
        a[i] = pivot;  
        // 对子序列快排  
        QuickSort(a, low, i-1);  
        QuickSort(a, i+1, high);  
    }  
}  
  
//快速排序法的划分操作  
int Partition(int vec[],int low,int high)  
{  
     //任选元素作为轴，这里选首元素  
     int pivot = vec[low];  
     while(low < high)  
     {  
         while(low < high && vec[high] >= pivot)  
             high--;  
         vec[low] = vec[high];  
         while(low < high && vec[low] <= pivot)  
             low++;  
         vec[high] = vec[low];  
     }  
     //此时low==high  
     vec[low] = pivot;  
     return low;  
}  
  
//in-place partition algorithm  
//http://en.wikipedia.org/wiki/Quicksort  
int in_place_partition(int* array, int left, int right)  
{  
    int index = left;  
    int pivot = array[index];  
    swap(array[index], array[right]);  
    for (int i=left; i<right; i++)  
    {  
        if (array[i] < pivot)    //升序  
        {  
            swap(array[index], array[i]);  
            ++index;  
        }  
    }  
    swap(array[right], array[index]);  
    return index;  
}  
  
void Qsort(int* array, int left, int right)  
{  
    if (left >= right)  
        return;  
    int index = Partition(array, left, right);  
    Qsort(array, left, index - 1);  
    Qsort(array, index + 1, right);  
}  
  
//非递归快速排序  
void QuickSort2(int vec[],int low,int high)  
{  
    stack<int> st;  
    if(low < high)  
    {  
        int mid = Partition(vec,low,high);  
        if(low < mid-1)  
        {  
             st.push(low);  
             st.push(mid-1);  
         }  
         if(mid+1 < high)  
         {  
             st.push(mid+1);  
             st.push(high);  
         }  
         //用栈保存每个待排序子串的首尾元素下标，下一次循环时取出这个范围，对这段子序列进行partition操作  
         while(!st.empty())  
         {  
             int q = st.top();  
             st.pop();  
             int p=st.top();  
             st.pop();  
             mid = Partition(vec,p,q);  
             if(p < mid-1)  
             {  
                 st.push(p);  
                 st.push(mid-1);  
             }  
             if(mid+1<q)  
             {  
                 st.push(mid+1);  
                 st.push(q);  
             }  
         }  
     }  
}  

归并排序（Merge Sort）

基本思想是合并两个有序表，设有两个有序（升序）序列存储在同一数组中相邻的位置上，不妨设为A[l..m]，A[m+1..h]，将它们归并为一个有序数列，并存储在A[l..h]。归并排序的时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。

归并排序在最坏的情况下都是O(NlogN)的时间复杂度，缺点是Merge的时候要有O(N)的额外的空间，如何改进？使用In-place Merge Sort:http://blog.ibread.net/345/in-place-merge-sort/ 关于原地归并也可参考我前面的文章

[cpp]view plaincopyprint? 
//将有序序列a[low..mid]和a[mid+1..high]归并到a[low..high]。  
void Merge(int a[], int low, int mid, int high)  
{  
    // 归并到b[]  
    int i = low;  
    int j = mid+1;  
    int k = 0;  
    int *b = newint[high-low+1];  
    while (i <= mid && j <= high)  
    {  
        if (a[i] <= a[j]) { b[k++] = a[i++]; }  
        else  { b[k++] = a[j++]; }  
    }  
    // 归并剩余元素  
    while (i <= mid)  b[k++] = a[i++];  
    while (j <= high)  b[k++] = a[j++];  
    // 从b[]复制回a[]  
    for(i = 0; i <= high-low; ++i)  
        a[low+i] = b[i];  
    delete []b;  
}  
  
//归并排序  
void MergeSort(int a[], int low, int high)  
{  
    if(low >= high)  return;  
    else  
    {  
        int mid = (low+high)/2;  
        MergeSort(a,low,mid);  
        MergeSort(a,mid+1,high);  
        Merge(a,low,mid,high);  
    }  
}  
  
//自底向上的归并排序  
void MergeSort2(int a[], int n)  
{  
    int s,i,t = 1;  
    while(t < n)  
    {  
        s = t;  t = s*2;  
        for(i=0; i+t<=n; i+=t)  
            Merge(a,i,i+s-1,i+t-1);  
        if(i+s < n)  
            Merge(a,i,i+s-1,n-1);  
    }  
} 