linux：堆排序和快速排序的整理

浏览数：16 / 时间：2015年06月20日

快排采用分治法（Divide and Conquer）把一个list分为两个sub-lists。

算法步骤

1. 从数列中跳出一个元素，作为基准(pivot)。

2. 重新排序数列，所有比基准值小的元素(elements < pivot)放在基准值的前面，而所有比基准值大的元素(elements > pivot)放在基准值后面，与基准值相等的数可以放在任意一边。此操作即为分区(partition)操作。

3. 递归地把小于基准值元素的子数列和大于基准值元素的子数列进行排序。递归在数列长度为0或者1时退出，此时该子数列已经永久排序完成。

1）如数列5 8 7 …，若此时5归位，那么其 left sub-list 的长度为0，退出递归。

2）如数列1 2 8 4…，若此时2归位，那么其 left sub-list的长度为1，退出递归。

注意：该算法一定是可以退出的，因为在每次的迭代中，它

使用快慢指针。仍以数列第一个元素为基准元素。初始化时，慢指针指向基准元素，也就是数列第一个元素，快指针指向数列第二个元素。快指针用于遍历数列。当程序运行时，慢指针将指向比基准元素小的元素的最后一个位置。当快指针指向的元素小于满指针指向的元素时，才进行交换，其实就是将小于基准元素的元素的位置往前移（思想类似于去空格，参看此博文）。

partition代码如下：

int partion(int *arr, int len)
{
    int last = 0;
    int fast = 1;
    int key = arr[0];
    for(;fast < len; fast++)
    {
        if(arr[fast] < key)
        {
            swap(&arr[last+1], &arr[fast]);
            last++;
        }
    }
    swap(&arr[0], &arr[last]); //归位
    return last;
}

至少会把一个元素放在它最后应该在的位置。

引言

首先需要明确，如何根据父亲结点的位置得知孩子结点的位置，以及如何根据孩子结点的位置得知父亲结点的位置。

假设数列索引从0开始，如果父亲结点的索引为i，那么左孩子索引为2i+1，右孩子索引为2i+2；如果孩子结点的索引为j，那么父亲结点的索引为(j-1)/2。

堆排序的核心在于函数 void adjustdown(int *arr, int i, int end) ，其中第i+1个元素到最后一个元素均已满足堆结构，每次adjustdown可以使当前位置i的元素也满足堆结构。如果是大堆，则经过adjustdown后当前位置的元素最大；如果是小堆，则经过adjustdown后当前位置的元素最小。

以下代码，将数列从小到大排序。采用大堆，并且使用了非递归的方法。函数adjustdown中的五个if语句实际上有一部分是可以合并的，但是为了逻辑清晰，在本代码中，完整保留下来了。注释我写的很用心，相信读者可以看懂。

代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

static void show(int *arr, int len)
{
    int index;
    for(index = 0; index < len; index++)
    {
        printf("%d ",arr[index]);
    }
    printf("\n");
}

static void swap(int *left, int *right)
{
    int tmp = *left;
    *left = *right;
    *right = tmp;
}

void adjustdown(int *arr, int i, int end)
{
    int key = arr[i];
    int p = i;              
    int left = 2 * p + 1;
    /* 越界就是没孩子 */    /* 只要能进循环，一定有左孩子 */
    while( left <= end )
    {
        /* 有右孩子的情况下，大于等于左右孩子不用换 */
        if( (key >= arr[left]) && (left+1 <= end && key >= arr[left+1]))
        {
            break;
        }else if( key >= arr[left] && left + 1 > end) /* 没有右孩子，只有左孩子，且大于等于左孩子不用换*/
        {
            break;
        }else if(left + 1 <= end && arr[left+1] >= arr[left] && key < arr[left+1]) /* 与右孩子换。要保证有右孩子，且右孩子大于等于左孩子，父亲小于右孩子 */
        {
            swap(arr+p, arr+left+1);
            p = left + 1;         //父亲与谁换，就到谁的位置了
             left = 2 * p + 1;      //父亲新的左孩子的位置
        }else if(left + 1 <= end && arr[left] > arr[left + 1] && key < arr[left])/* 与左孩子换。有右孩子的情况下，右孩子小于左孩子，父亲小于左孩子 */
        {
            swap(arr + p, arr + left);
            p = left;
            left = 2 * p + 1;
        }else if(left + 1 > end && arr[left] > key) /* 与左孩子换。没右孩子的情况下，只需父亲小于左孩子 */
        {
            swap(arr + p, arr + left);
            p = left;
            left = 2 * p + 1;
        }
    }    
}


void heap_sort(int *arr, int len)
{
    int p;   // 最后一个父亲
    int end; // 最后一个有效下标
    /* 建一个大顶堆，从最后一个父亲开始调 */
    for(p = (len -1 -1) /2 ; p >= 0; p--)
    {
        adjustdown(arr, p ,len - 1);
    }
    /* 根结点的值最大，与末尾交换，并继续建立堆结构，再交换... */
    for(end = len - 1; end >= 1; end--)
    {
        swap(arr, arr + end );   // end已经是最大值
        adjustdown(arr,0,end-1);  // 从arr+1 到 end-1位置都是满足堆结构的
    }
}

int main(int argc, char *argv[])
{
    int index;
    int arr[10];
    memset(arr,0,10);
    srand(time(NULL));
    for(index = 0; index < 10; index++)
    {
        arr[index] = rand()%20+1;
    }
    show(arr,10);
    
    heap_sort(arr,10);
    show(arr,10);

    system("pause");
    return 0;
}