您的位置:永利集团登录网址 > 永利集团登录网址 > 快速排序(非递归)

快速排序(非递归)

2019-11-15 03:46

以下代码经测试,排序5000000(五千万)int型数据没有问题!

以下代码经测试,排序5000000(五千万)int型数据没有问题!

以下代码经测试,排序5000000(五千万)int型数据没有问题!

 

第一个参数是数组首地址
第二个参数是数组元素个数

第一个参数是数组首地址
第二个参数是数组元素个数
void HeapSort(int * const arr, const DWORD number)//堆排序  

    int tmp; 
    DWORD tmpIndex; 
    DWORD i=1; 
    DWORD num; 
    DWORD indexUp; 
    DWORD indexDown; 
    if (number < 2) 
    { 
        return; 
    } 
    indexUp = number-1; 
    if (0 != (indexUp%2)) 
    { 
        tmpIndex = (indexUp - 1) / 2; 
        if (arr[indexUp] > arr[tmpIndex]) 
        { 
            tmp = arr[indexUp]; 
            arr[indexUp] = arr[tmpIndex]; 
            arr[tmpIndex] = tmp; 
        } 
        indexUp--; 
    } 
    for (; indexUp>0; indexUp-=2) 
    { 
        tmpIndex = (indexUp / 2) - 1; 
        if (arr[indexUp-1] >= arr[indexUp]) 
        { 
            if (arr[indexUp-1] > arr[tmpIndex]) 
            { 
                tmp = arr[indexUp-1]; 
                arr[indexUp-1] = arr[tmpIndex]; 
                arr[tmpIndex] = tmp; 
                indexDown = indexUp-1; 
            } 
            else 
            { 
                continue; 
            } 
        } 
        else 
        { 
            if (arr[indexUp] > arr[tmpIndex]) 
            { 
                tmp = arr[indexUp]; 
                arr[indexUp] = arr[tmpIndex]; 
                arr[tmpIndex] = tmp; 
                indexDown = indexUp; 
            } 
            else 
            { 
                continue; 
            } 
        } 
        while ((2*indexDown) < number) 
        { 
            tmpIndex = 2*indexDown +1; 
            if (arr[tmpIndex] >= arr[tmpIndex+1] || (tmpIndex+1 == number)) 
            { 
                if (arr[tmpIndex] > arr[indexDown]) 
                { 
                    tmp = arr[indexDown]; 
                    arr[indexDown] = arr[tmpIndex]; 
                    arr[tmpIndex] = tmp; 
                    indexDown = tmpIndex; 
                } 
                else 
                { 
                    break; 
                } 
            } 
            else 
            { 
                if ((arr[tmpIndex+1] > arr[indexDown]) && (tmpIndex < number)) 
                { 
                    tmp = arr[indexDown]; 
                    arr[indexDown] = arr[tmpIndex+1]; 
                    arr[tmpIndex+1] = tmp; 
                    indexDown = tmpIndex+1; 
                } 
                else 
                { 
                    break; 
                } 
            } 
        } 
    } 
    tmp = arr[0]; 
    arr[0] = arr[number-1]; 
    arr[number-1] = tmp; 
 
    for (num=number-1; num>1; num--) 
    { 
        for (indexDown=0; (2*indexDown +1) < num; ) 
        { 
            tmpIndex = 2*indexDown +1; 
            if (arr[tmpIndex] >= arr[tmpIndex+1]) 
            { 
                if (arr[tmpIndex] > arr[indexDown]) 
                { 
                    tmp = arr[indexDown]; 
                    arr[indexDown] = arr[tmpIndex]; 
                    arr[tmpIndex] = tmp; 
                    indexDown = tmpIndex; 
                } 
                else 
                { 
                    break; 
                } 
            } 
            else 
            { 
                if ((arr[tmpIndex+1] > arr[indexDown]) && (tmpIndex+1 < num)) 
                { 
                    tmp = arr[indexDown]; 
                    arr[indexDown] = arr[tmpIndex+1]; 
                    arr[tmpIndex+1] = tmp; 
                    indexDown = tmpIndex+1; 
                } 
                else 
                { 
                    break; 
                } 
            } 
        } 
        tmp = arr[0]; 
        arr[0] = arr[num-1]; 
        arr[num-1] = tmp; 
    } 

void HeapSort(int * const arr, const DWORD number)//堆排序
{
    int tmp;
    DWORD tmpIndex;
    DWORD i=1;
    DWORD num;
    DWORD indexUp;
    DWORD indexDown;
    if (number < 2)
    {
        return;
    }
    indexUp = number-1;
    if (0 != (indexUp%2))
    {
        tmpIndex = (indexUp - 1) / 2;
        if (arr[indexUp] > arr[tmpIndex])
        {
            tmp = arr[indexUp];
            arr[indexUp] = arr[tmpIndex];
            arr[tmpIndex] = tmp;
        }
        indexUp--;
    }
    for (; indexUp>0; indexUp-=2)
    {
        tmpIndex = (indexUp / 2) - 1;
        if (arr[indexUp-1] >= arr[indexUp])
        {
            if (arr[indexUp-1] > arr[tmpIndex])
            {
                tmp = arr[indexUp-1];
                arr[indexUp-1] = arr[tmpIndex];
                arr[tmpIndex] = tmp;
                indexDown = indexUp-1;
            }
            else
            {
                continue;
            }
        }
        else
        {
            if (arr[indexUp] > arr[tmpIndex])
            {
                tmp = arr[indexUp];
                arr[indexUp] = arr[tmpIndex];
                arr[tmpIndex] = tmp;
                indexDown = indexUp;
            }
            else
            {
                continue;
            }
        }
        while ((2*indexDown) < number)
        {
            tmpIndex = 2*indexDown +1;
            if (arr[tmpIndex] >= arr[tmpIndex+1] || (tmpIndex+1 == number))
            {
                if (arr[tmpIndex] > arr[indexDown])
                {
                    tmp = arr[indexDown];
                    arr[indexDown] = arr[tmpIndex];
                    arr[tmpIndex] = tmp;
                    indexDown = tmpIndex;
                }
                else
                {
                    break;
                }
            }
            else
            {
                if ((arr[tmpIndex+1] > arr[indexDown]) && (tmpIndex < number))
                {
                    tmp = arr[indexDown];
                    arr[indexDown] = arr[tmpIndex+1];
                    arr[tmpIndex+1] = tmp;
                    indexDown = tmpIndex+1;
                }
                else
                {
                    break;
                }
            }
        }
    }
    tmp = arr[0];
    arr[0] = arr[number-1];
    arr[number-1] = tmp;

第一个参数是数组首地址
第二个参数是数组元素个数
void MergeSort(int * const arr, const DWORD number)//归并排序  

    DWORD i; 
    DWORD index1, index2;//将数组分为两个,分别作为两个数组第一个元素的下标  
    DWORD tmpIndex1, tmpIndex2;//分别指向两个数组中的元素相对于index1、index2的步进  
    DWORD step;//步进  
    int *tmpArr = NULL; 
    if (number < 2) 
    { 
        return; 
    } 
    tmpArr = (int *)malloc(number*sizeof (int)); 
    if (NULL == tmpArr) 
    { 
        printf("分配缓存出错!n"); 
        getch(); 
        return; 
    } 
    for (step=1; step<number; step*=2) 
    { 
        index1 = 0; 
        index2 = index1 + step; 
        tmpIndex1 = 0; 
        tmpIndex2 = 0; 
        i = 0; 
        while ((index2+tmpIndex2) < number) 
        { 
            while ((tmpIndex1 < step) && (tmpIndex2 < step) && ((index2+tmpIndex2) < number)) 
            { 
                if (arr[index1+tmpIndex1] <= arr[index2+tmpIndex2]) 
                { 
                    tmpArr[i] = arr[index1+tmpIndex1]; 
                    tmpIndex1++; 
                } 
                else 
                { 
                    tmpArr[i] = arr[index2+tmpIndex2]; 
                    tmpIndex2++; 
                } 
                i++; 
            } 
            while (tmpIndex1<step) 
            { 
                tmpArr[i++] = arr[index1+tmpIndex1]; 
                tmpIndex1++; 
            } 
            while ((tmpIndex2<step) && ((index2+tmpIndex2) < number)) 
            { 
                tmpArr[i++] = arr[index2+tmpIndex2]; 
                tmpIndex2++; 
            } 
            index1 = index1 + 2*step; 
            index2 = index2 + 2*step; 
            tmpIndex1 = 0; 
            tmpIndex2 = 0; 
        } 
        memcpy(arr, tmpArr, number*sizeof (int)); 
    } 
    free(tmpArr); 

void MergeSort(int * const arr, const DWORD number)//归并排序
{
    DWORD i;
    DWORD index1, index2;//将数组分为两个,分别作为两个数组第一个元素的下标
    DWORD tmpIndex1, tmpIndex2;//分别指向两个数组中的元素相对于index1、index2的步进
    DWORD step;//步进
    int *tmpArr = NULL;
    if (number < 2)
    {
        return;
    }
    tmpArr = (int *)malloc(number*sizeof (int));
    if (NULL == tmpArr)
    {
        printf("分配缓存出错!n");
        getch();
        return;
    }
    for (step=1; step<number; step*=2)
    {
        index1 = 0;
        index2 = index1 + step;
        tmpIndex1 = 0;
        tmpIndex2 = 0;
        i = 0;
        while ((index2+tmpIndex2) < number)
        {
            while ((tmpIndex1 < step) && (tmpIndex2 < step) && ((index2+tmpIndex2) < number))
            {
                if (arr[index1+tmpIndex1] <= arr[index2+tmpIndex2])
                {
                    tmpArr[i] = arr[index1+tmpIndex1];
                    tmpIndex1++;
                }
                else
                {
                    tmpArr[i] = arr[index2+tmpIndex2];
                    tmpIndex2++;
                }
                i++;
            }
            while (tmpIndex1<step)
            {
                tmpArr[i++] = arr[index1+tmpIndex1];
                tmpIndex1++;
            }
            while ((tmpIndex2<step) && ((index2+tmpIndex2) < number))
            {
                tmpArr[i++] = arr[index2+tmpIndex2];
                tmpIndex2++;
            }
            index1 = index1 + 2*step;
            index2 = index2 + 2*step;
            tmpIndex1 = 0;
            tmpIndex2 = 0;
        }
        memcpy(arr, tmpArr, number*sizeof (int));
    }
    free(tmpArr);
}

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;

    for (num=number-1; num>1; num--)
    {
        for (indexDown=0; (2*indexDown +1) < num; )
        {
            tmpIndex = 2*indexDown +1;
            if (arr[tmpIndex] >= arr[tmpIndex+1])
            {
                if (arr[tmpIndex] > arr[indexDown])
                {
                    tmp = arr[indexDown];
                    arr[indexDown] = arr[tmpIndex];
                    arr[tmpIndex] = tmp;
                    indexDown = tmpIndex;
                }
                else
                {
                    break;
                }
            }
            else
            {
                if ((arr[tmpIndex+1] > arr[indexDown]) && (tmpIndex+1 < num))
                {
                    tmp = arr[indexDown];
                    arr[indexDown] = arr[tmpIndex+1];
                    arr[tmpIndex+1] = tmp;
                    indexDown = tmpIndex+1;
                }
                else
                {
                    break;
                }
            }
        }
        tmp = arr[0];
        arr[0] = arr[num-1];
        arr[num-1] = 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--;
        }

#include <stdio.h>  
#include <conio.h>  
#include <windows.h>  
 
void HeapSort(int * const arr, const 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个随机数耗时:%umsn", num, EndTime - StartTime); 
     
    StartTime = GetTickCount(); 
    HeapSort(arr, num); 
    EndTime = GetTickCount(); 
    printf("堆排序耗时:%umsn", EndTime - StartTime); 
    ExamineArr(arr, num);//检查排序结果  
 
    free(arr); 
    getch(); 
    return 0; 

 
void HeapSort(int * const arr, const DWORD number)//堆排序  

    int tmp; 
    DWORD tmpIndex; 
    DWORD i=1; 
    DWORD num; 
    DWORD indexUp; 
    DWORD indexDown; 
    if (number < 2) 
    { 
        return; 
    } 
    indexUp = number-1; 
    if (0 != (indexUp%2)) 
    { 
        tmpIndex = (indexUp - 1) / 2; 
        if (arr[indexUp] > arr[tmpIndex]) 
        { 
            tmp = arr[indexUp]; 
            arr[indexUp] = arr[tmpIndex]; 
            arr[tmpIndex] = tmp; 
        } 
        indexUp--; 
    } 
    for (; indexUp>0; indexUp-=2) 
    { 
        tmpIndex = (indexUp / 2) - 1; 
        if (arr[indexUp-1] >= arr[indexUp]) 
        { 
            if (arr[indexUp-1] > arr[tmpIndex]) 
            { 
                tmp = arr[indexUp-1]; 
                arr[indexUp-1] = arr[tmpIndex]; 
                arr[tmpIndex] = tmp; 
                indexDown = indexUp-1; 
            } 
            else 
            { 
                continue; 
            } 
        } 
        else 
        { 
            if (arr[indexUp] > arr[tmpIndex]) 
            { 
                tmp = arr[indexUp]; 
                arr[indexUp] = arr[tmpIndex]; 
                arr[tmpIndex] = tmp; 
                indexDown = indexUp; 
            } 
            else 
            { 
                continue; 
            } 
        } 
        while ((2*indexDown) < number) 
        { 
            tmpIndex = 2*indexDown +1; 
            if (arr[tmpIndex] >= arr[tmpIndex+1] || (tmpIndex+1 == number)) 
            { 
                if (arr[tmpIndex] > arr[indexDown]) 
                { 
                    tmp = arr[indexDown]; 
                    arr[indexDown] = arr[tmpIndex]; 
                    arr[tmpIndex] = tmp; 
                    indexDown = tmpIndex; 
                } 
                else 
                { 
                    break; 
                } 
            } 
            else 
            { 
                if ((arr[tmpIndex+1] > arr[indexDown]) && (tmpIndex < number)) 
                { 
                    tmp = arr[indexDown]; 
                    arr[indexDown] = arr[tmpIndex+1]; 
                    arr[tmpIndex+1] = tmp; 
                    indexDown = tmpIndex+1; 
                } 
                else 
                { 
                    break; 
                } 
            } 
        } 
    } 
    tmp = arr[0]; 
    arr[0] = arr[number-1]; 
    arr[number-1] = tmp; 
 
    for (num=number-1; num>1; num--) 
    { 
        for (indexDown=0; (2*indexDown +1) < num; ) 
        { 
            tmpIndex = 2*indexDown +1; 
            if (arr[tmpIndex] >= arr[tmpIndex+1]) 
            { 
                if (arr[tmpIndex] > arr[indexDown]) 
                { 
                    tmp = arr[indexDown]; 
                    arr[indexDown] = arr[tmpIndex]; 
                    arr[tmpIndex] = tmp; 
                    indexDown = tmpIndex; 
                } 
                else 
                { 
                    break; 
                } 
            } 
            else 
            { 
                if ((arr[tmpIndex+1] > arr[indexDown]) && (tmpIndex+1 < num)) 
                { 
                    tmp = arr[indexDown]; 
                    arr[indexDown] = arr[tmpIndex+1]; 
                    arr[tmpIndex+1] = tmp; 
                    indexDown = tmpIndex+1; 
                } 
                else 
                { 
                    break; 
                } 
            } 
        } 
        tmp = arr[0]; 
        arr[0] = arr[num-1]; 
        arr[num-1] = tmp; 
    } 

 
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; 
        } 
    } 

#include <stdio.h>  
#include <conio.h>  
#include <windows.h>  
 
void MergeSort(int * const arr, const 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个随机数耗时:%umsn", num, EndTime - StartTime); 
     
    StartTime = GetTickCount(); 
    MergeSort(arr, num); 
    EndTime = GetTickCount(); 
    printf("归并排序耗时:%umsn", EndTime - StartTime); 
    ExamineArr(arr, num);//检查排序结果  
 
    free(arr); 
    getch(); 
    return 0; 

 
void MergeSort(int * const arr, const DWORD number)//归并排序  

    DWORD i; 
    DWORD index1, index2;//将数组分为两个,分别作为两个数组第一个元素的下标  
    DWORD tmpIndex1, tmpIndex2;//分别指向两个数组中的元素相对于index1、index2的步进  
    DWORD step;//步进  
    int *tmpArr = NULL; 
    if (number < 2) 
    { 
        return; 
    } 
    tmpArr = (int *)malloc(number*sizeof (int)); 
    if (NULL == tmpArr) 
    { 
        printf("分配缓存出错!n"); 
        getch(); 
        return; 
    } 
    for (step=1; step<number; step*=2) 
    { 
        index1 = 0; 
        index2 = index1 + step; 
        tmpIndex1 = 0; 
        tmpIndex2 = 0; 
        i = 0; 
        while ((index2+tmpIndex2) < number) 
        { 
            while ((tmpIndex1 < step) && (tmpIndex2 < step) && ((index2+tmpIndex2) < number)) 
            { 
                if (arr[index1+tmpIndex1] <= arr[index2+tmpIndex2]) 
                { 
                    tmpArr[i] = arr[index1+tmpIndex1]; 
                    tmpIndex1++; 
                } 
                else 
                { 
                    tmpArr[i] = arr[index2+tmpIndex2]; 
                    tmpIndex2++; 
                } 
                i++; 
            } 
            while (tmpIndex1<step) 
            { 
                tmpArr[i++] = arr[index1+tmpIndex1]; 
                tmpIndex1++; 
            } 
            while ((tmpIndex2<step) && ((index2+tmpIndex2) < number)) 
            { 
                tmpArr[i++] = arr[index2+tmpIndex2]; 
                tmpIndex2++; 
            } 
            index1 = index1 + 2*step; 
            index2 = index2 + 2*step; 
            tmpIndex1 = 0; 
            tmpIndex2 = 0; 
        } 
        memcpy(arr, tmpArr, number*sizeof (int)); 
    } 
    free(tmpArr); 

 
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; 
        } 
    } 

#include <stdio.h>
#include <conio.h>
#include <windows.h>

        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;
        }
    }
}

图片 1

void MergeSort(int * const arr, const DWORD number);//归并排序
void ExamineArr(const int * const arr, DWORD number);//检查排序结果

 

摘自 kevinshq的专栏

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;
    }

测试代码:

第一个参数是数组首地址 第二个参数是数组元素个数 void HeapSort(int * const arr...

    StartTime = GetTickCount();
    for (i=0; i<num; i++)
    {
        *(arr+i) = rand();
    }
    EndTime = GetTickCount();
    printf("生成%u个随机数耗时:%umsn", num, EndTime - StartTime);
   
    StartTime = GetTickCount();
    MergeSort(arr, num);
    EndTime = GetTickCount();
    printf("归并排序耗时:%umsn", EndTime - StartTime);
    ExamineArr(arr, num);//检查排序结果

#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个随机数耗时:%umsn", num, EndTime - StartTime); 
     
    StartTime = GetTickCount(); 
    QuickSort(arr, num); 
    EndTime = GetTickCount(); 
    printf("快速排序耗时:%umsn", 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; 
        } 
    } 

    free(arr);
    getch();
    return 0;
}

图片 2

void MergeSort(int * const arr, const DWORD number)//归并排序
{
    DWORD i;
    DWORD index1, index2;//将数组分为两个,分别作为两个数组第一个元素的下标
    DWORD tmpIndex1, tmpIndex2;//分别指向两个数组中的元素相对于index1、index2的步进
    DWORD step;//步进
    int *tmpArr = NULL;
    if (number < 2)
    {
        return;
    }
    tmpArr = (int *)malloc(number*sizeof (int));
    if (NULL == tmpArr)
    {
        printf("分配缓存出错!n");
        getch();
        return;
    }
    for (step=1; step<number; step*=2)
    {
        index1 = 0;
        index2 = index1 + step;
        tmpIndex1 = 0;
        tmpIndex2 = 0;
        i = 0;
        while ((index2+tmpIndex2) < number)
        {
            while ((tmpIndex1 < step) && (tmpIndex2 < step) && ((index2+tmpIndex2) < number))
            {
                if (arr[index1+tmpIndex1] <= arr[index2+tmpIndex2])
                {
                    tmpArr[i] = arr[index1+tmpIndex1];
                    tmpIndex1++;
                }
                else
                {
                    tmpArr[i] = arr[index2+tmpIndex2];
                    tmpIndex2++;
                }
                i++;
            }
            while (tmpIndex1<step)
            {
                tmpArr[i++] = arr[index1+tmpIndex1];
                tmpIndex1++;
            }
            while ((tmpIndex2<step) && ((index2+tmpIndex2) < number))
            {
                tmpArr[i++] = arr[index2+tmpIndex2];
                tmpIndex2++;
            }
            index1 = index1 + 2*step;
            index2 = index2 + 2*step;
            tmpIndex1 = 0;
            tmpIndex2 = 0;
        }
        memcpy(arr, tmpArr, number*sizeof (int));
    }
    free(tmpArr);
}

摘自 kevinshq的专栏

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;
        }
    }
}

第一个参数是数组首地址 第二个参数是数组元素个数 typedef struct _BUFF { int *L...

 图片 3

摘自 kevinshq的专栏

第一个参数是数组首地址 第二个参数是数组元素个数 void MergeSort(int * const ar...

本文由永利集团登录网址发布于永利集团登录网址,转载请注明出处:快速排序(非递归)

关键词: