内存映射实现快速排序

/*
 * 内存映射实现快速排序
 * Lzy 2011-6-17
 */

#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <sys/mman.h>

#define DATA_NUM 100    //要进行排序的数据为1000个

/*
 * 一趟快速排序
 * 取第一个为基准值
 * 先从右向左扫描，找取第一个小于基准值的元素，交换位置
 * 再从左向右扫描，找取第一个大于基准值的元素，交换位置
 */
int partion(int num[], int left, int right)
{
    int temp;
    int pos = num[left];        //定义基准值

    while(left < right)
    {
        while(left < right && num[right] >= pos)        //从右向左进行扫描，查找第一个小于基准值的数据元素
        {
            right--;
        }
        temp = num[left];            //数据交换
        num[left] = num[right];
        num[right] = temp;

        while(left < right && num[left] <= pos)    //从左向右进行扫描，查找第一个大于基准值的数据元素
        {
            left++;
        }
        temp = num[left];                        //数据交换
        num[left] = num[right];
        num[right] = temp;
    }
    return left;
}

/*
 * 递归调用实现快速排序
 */
void qu_sort(int num[], int left, int right)
{
    int pos;

    if(left < right)
    {
        pos = partion(num, left, right);        //划分左右子树
        qu_sort(num, left, pos-1);                //递归调用，对左子树进行排序
        qu_sort(num, pos+1, right);                //递归调用，对右子树进行排序
    }
}

int main(void)
{
    int i, data;
    int fd, length;

    int *ptr;

    fd = open("data", O_RDWR | O_CREAT, 0776);    //打开文件
    if(fd < 0)
    {
        perror("open");
        exit(0);
    }

    for(i = 0; i < DATA_NUM; i++)    //往文件中写入DATA_NUM个数据
    {
        data = rand() % 1000;            //产生随机数
        write(fd, &data, sizeof(data));        //数据写入文件
    }

    ptr = mmap(NULL, DATA_NUM*sizeof(int), PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);    //内存映射
    if((int)ptr == -1)
    {
        perror("mmap");
        exit(0);
    }

    qu_sort(ptr, 0, DATA_NUM-1);                    //数据排序

    munmap(ptr, DATA_NUM*sizeof(int));                //取消映射

    lseek(fd, 0, SEEK_SET);                            //读写位置指向文件头
    for(i = 0; i < DATA_NUM; i++)                    //往文件中写入DATA_NUM个数据
    {
        read(fd, &data, sizeof(data));                //数据写入文件
        printf("%d ",data);
    }
    printf("\n");

    close(fd);
    return 0;
}