快速排序（非遞歸）

以下代碼經測試，排序5000000（五千萬）int型數據沒有問題！

第一個參數是數組首地址
第二個參數是數組元素個數

typedef struct _BUFF { 
    int *LeftBuff; 
    int *RightBuff; 
    DWORD number;//有多少個  
    struct _BUFF *next; 
}BUFF; 
void QuickSort(int * const arr, DWORD number)//快速排序  
{ 
    int tmp; 
    int key; 
    DWORD left, right; 
    DWORD tmpLeft, tmpRight; 
    BUFF *p = NULL; 
    BUFF buff = {NULL, NULL, 0, NULL}; 
    buff.LeftBuff = (int *)malloc(1024*1024*sizeof (int)); 
    buff.RightBuff = (int *)malloc(1024*1024*sizeof (int)); 
    if ((NULL == buff.LeftBuff) || (NULL == buff.LeftBuff)) 
    { 
        free(buff.LeftBuff); 
        free(buff.LeftBuff); 
        printf("分配緩存出錯！\n"); 
        return; 
    } 
    buff.LeftBuff[buff.number] = 0; 
    buff.RightBuff[buff.number] = number-1; 
    buff.number++; 
    p = &buff; 
    while (buff.number/* && (NULL == buff.next)*/) 
    { 
        tmpLeft = p->LeftBuff[p->number-1]; 
        tmpRight = p->RightBuff[p->number-1]; 
        left = tmpLeft; 
        right = tmpRight; 
        key = arr[left++]; 
        do 
        { 
            while ((arr[left] < key) && (left < tmpRight)) 
            { 
                left++; 
            } 
            while ((arr[right] >= key) && (right > tmpLeft)) 
            { 
                right--; 
            } 
            if (left < right) 
            { 
                tmp = arr[left]; 
                arr[left] = arr[right]; 
                arr[right] = tmp; 
            } 
        } 
        while (left < right); 
        tmp = arr[right]; 
        arr[right] = arr[tmpLeft]; 
        arr[tmpLeft] = tmp; 
 
        if (p->number >= 1024*1024-1) 
        { 
            p->next = (BUFF *)malloc(sizeof (BUFF)); 
            if (NULL != p->next) 
            { 
                p = p->next; 
                p->LeftBuff = (int *)malloc(1024*1024*sizeof (int)); 
                p->RightBuff = (int *)malloc(1024*1024*sizeof (int)); 
                p->number = 0; 
                p->next = NULL; 
            } 
            if ((0 != p->number) || (NULL == p->LeftBuff) || (NULL == p->RightBuff)) 
            { 
                printf("分配緩存出錯！\n"); 
                while (NULL != buff.next) 
                { 
                    p = buff.next; 
                    do 
                    { 
                        p = p->next; 
                    } 
                    while (NULL != p->next); 
                    free(p); 
                } 
                getch(); 
                return; 
            } 
        } 
        else 
        { 
            p->number--; 
        } 
 
        if (tmpLeft+1 < right) 
        { 
            p->LeftBuff[p->number] = tmpLeft; 
            p->RightBuff[p->number] = right-1; 
            p->number++; 
        } 
        if (tmpRight > left) 
        { 
            p->LeftBuff[p->number] = left; 
            p->RightBuff[p->number] = tmpRight; 
            p->number++; 
        } 
        if ((0 == p->number) && (NULL != buff.next)) 
        { 
            p = &buff; 
            while (NULL == p->next->next) 
            { 
                p = p->next; 
            } 
            free(p->next); 
            p->next = NULL; 
        } 
    } 
} 
typedef struct _BUFF {
    int *LeftBuff;
    int *RightBuff;
    DWORD number;//有多少個
    struct _BUFF *next;
}BUFF;
void QuickSort(int * const arr, DWORD number)//快速排序
{
    int tmp;
    int key;
    DWORD left, right;
    DWORD tmpLeft, tmpRight;
    BUFF *p = NULL;
    BUFF buff = {NULL, NULL, 0, NULL};
    buff.LeftBuff = (int *)malloc(1024*1024*sizeof (int));
    buff.RightBuff = (int *)malloc(1024*1024*sizeof (int));
    if ((NULL == buff.LeftBuff) || (NULL == buff.LeftBuff))
    {
        free(buff.LeftBuff);
        free(buff.LeftBuff);
        printf("分配緩存出錯！\n");
        return;
    }
    buff.LeftBuff[buff.number] = 0;
    buff.RightBuff[buff.number] = number-1;
    buff.number++;
    p = &buff;
    while (buff.number/* && (NULL == buff.next)*/)
    {
        tmpLeft = p->LeftBuff[p->number-1];
        tmpRight = p->RightBuff[p->number-1];
        left = tmpLeft;
        right = tmpRight;
        key = arr[left++];
        do
        {
            while ((arr[left] < key) && (left < tmpRight))
            {
                left++;
            }
            while ((arr[right] >= key) && (right > tmpLeft))
            {
                right--;
            }
            if (left < right)
            {
                tmp = arr[left];
                arr[left] = arr[right];
                arr[right] = tmp;
            }
        }
        while (left < right);
        tmp = arr[right];
        arr[right] = arr[tmpLeft];
        arr[tmpLeft] = tmp;

        if (p->number >= 1024*1024-1)
        {
            p->next = (BUFF *)malloc(sizeof (BUFF));
            if (NULL != p->next)
            {
                p = p->next;
                p->LeftBuff = (int *)malloc(1024*1024*sizeof (int));
                p->RightBuff = (int *)malloc(1024*1024*sizeof (int));
                p->number = 0;
                p->next = NULL;
            }
            if ((0 != p->number) || (NULL == p->LeftBuff) || (NULL == p->RightBuff))
            {
                printf("分配緩存出錯！\n");
                while (NULL != buff.next)
                {
                    p = buff.next;
                    do
                    {
                        p = p->next;
                    }
                    while (NULL != p->next);
                    free(p);
                }
                getch();
                return;
            }
        }
        else
        {
            p->number--;
        }

        if (tmpLeft+1 < right)
        {
            p->LeftBuff[p->number] = tmpLeft;
            p->RightBuff[p->number] = right-1;
            p->number++;
        }
        if (tmpRight > left)
        {
            p->LeftBuff[p->number] = left;
            p->RightBuff[p->number] = tmpRight;
            p->number++;
        }
        if ((0 == p->number) && (NULL != buff.next))
        {
            p = &buff;
            while (NULL == p->next->next)
            {
                p = p->next;
            }
            free(p->next);
            p->next = NULL;
        }
    }
}

測試代碼：

#include <stdio.h>  
#include <conio.h>  
#include <windows.h>  
 
typedef struct _BUFF { 
    int *LeftBuff; 
    int *RightBuff; 
    DWORD number;//有多少個  
    struct _BUFF *next; 
}BUFF; 
 
void QuickSort(int * const arr, DWORD number);//快速排序  
void ExamineArr(const int * const arr, DWORD number);//檢查排序結果  
 
int main(int argc, char *argv[]) 
{ 
    DWORD StartTime, EndTime; 
    DWORD i; 
    DWORD num = 50000000; 
    int *arr = NULL; 
    arr = (int *)malloc(num * sizeof (int)); 
    if (NULL == arr) 
    { 
        free(arr); 
        printf("內存分配失敗，程序退出！\n"); 
        getch(); 
        return -1; 
    } 
 
    StartTime = GetTickCount(); 
    for (i=0; i<num; i++) 
    { 
        *(arr+i) = rand(); 
    } 
    EndTime = GetTickCount(); 
    printf("生成%u個隨機數耗時：%ums\n", num, EndTime - StartTime); 
     
    StartTime = GetTickCount(); 
    QuickSort(arr, num); 
    EndTime = GetTickCount(); 
    printf("快速排序耗時：%ums\n", EndTime - StartTime); 
    ExamineArr(arr, num);//檢查排序結果  
 
    free(arr); 
    getch(); 
    return 0; 
} 
 
void QuickSort(int * const arr, DWORD number)//快速排序  
{ 
    int tmp; 
    int key; 
    DWORD left, right; 
    DWORD tmpLeft, tmpRight; 
    BUFF *p = NULL; 
    BUFF buff = {NULL, NULL, 0, NULL}; 
    buff.LeftBuff = (int *)malloc(1024*1024*sizeof (int)); 
    buff.RightBuff = (int *)malloc(1024*1024*sizeof (int)); 
    if ((NULL == buff.LeftBuff) || (NULL == buff.LeftBuff)) 
    { 
        free(buff.LeftBuff); 
        free(buff.LeftBuff); 
        printf("分配緩存出錯！\n"); 
        return; 
    } 
    buff.LeftBuff[buff.number] = 0; 
    buff.RightBuff[buff.number] = number-1; 
    buff.number++; 
    p = &buff; 
    while (buff.number/* && (NULL == buff.next)*/) 
    { 
        tmpLeft = p->LeftBuff[p->number-1]; 
        tmpRight = p->RightBuff[p->number-1]; 
        left = tmpLeft; 
        right = tmpRight; 
        key = arr[left++]; 
        do 
        { 
            while ((arr[left] < key) && (left < tmpRight)) 
            { 
                left++; 
            } 
            while ((arr[right] >= key) && (right > tmpLeft)) 
            { 
                right--; 
            } 
            if (left < right) 
            { 
                tmp = arr[left]; 
                arr[left] = arr[right]; 
                arr[right] = tmp; 
            } 
        } 
        while (left < right); 
        tmp = arr[right]; 
        arr[right] = arr[tmpLeft]; 
        arr[tmpLeft] = tmp; 
 
        if (p->number >= 1024*1024-1) 
        { 
            p->next = (BUFF *)malloc(sizeof (BUFF)); 
            if (NULL != p->next) 
            { 
                p = p->next; 
                p->LeftBuff = (int *)malloc(1024*1024*sizeof (int)); 
                p->RightBuff = (int *)malloc(1024*1024*sizeof (int)); 
                p->number = 0; 
                p->next = NULL; 
            } 
            if ((0 != p->number) || (NULL == p->LeftBuff) || (NULL == p->RightBuff)) 
            { 
                printf("分配緩存出錯！\n"); 
                while (NULL != buff.next) 
                { 
                    p = buff.next; 
                    do 
                    { 
                        p = p->next; 
                    } 
                    while (NULL != p->next); 
                    free(p); 
                } 
                getch(); 
                return; 
            } 
        } 
        else 
        { 
            p->number--; 
        } 
 
        if (tmpLeft+1 < right) 
        { 
            p->LeftBuff[p->number] = tmpLeft; 
            p->RightBuff[p->number] = right-1; 
            p->number++; 
        } 
        if (tmpRight > left) 
        { 
            p->LeftBuff[p->number] = left; 
            p->RightBuff[p->number] = tmpRight; 
            p->number++; 
        } 
        if ((0 == p->number) && (NULL != buff.next)) 
        { 
            p = &buff; 
            while (NULL == p->next->next) 
            { 
                p = p->next; 
            } 
            free(p->next); 
            p->next = NULL; 
        } 
    } 
} 
 
void ExamineArr(const int * const arr, DWORD number) 
{ 
    DWORD i=0, j=1; 
    if (number <2) 
    { 
        return; 
    } 
    for (; j<number; i++,j++) 
    { 
        if (arr[i] > arr[j]) 
        { 
            printf("第%u個數大於第%u個數！\n", i, j); 
            return; 
        } 
    } 
} 



摘自 kevinshq的專欄