Quick_sort

佚名 6年前 (2019-04-26) 随笔 1809人围观抢沙发百度已收录

typedef int ElementType;

void Quick_sort(ElementType A[], int N)
{
    Quicksort(A, 0, N-1);    
} 

void Quicksort(ElementType A[], int left, int right)
{
    if(right-left+1 < 100)
    {
        //插入排序
        Insert_sort(A, right-left+1); 
    }
    else
    {
        //调用快排
        //找中位数,优化快排 
        pivot = Median3(A, left, right);
        
        int i = left;
        int j = right;
        
        while(true)
        {
            while(A[++i] < pivot);
            while(A[--j] > pivot);
            if(i < j)
                swap(&A[i], &A[j]);
            else
                break;
        }
        swap(&A[i], &A[right-1]);
        
        //递归左右
        Quicksort(A, left, i-1);
        Quicksort(A, i+1, right); 
    }
}

void Insert_sort(ElementType A[], int N)
{
    for(int i = 1; i < N; i++)
    {
        int j;
        int Temp = A[i];
        for(j = i-1; j >= 0 && A[j] > Temp; j--)
        {
            A[j] = A[j+1];
        }
        A[j] = Temp;
    }
}