编辑代码

#include <stdio.h>

void Swap(int *p,int *q)
{
	int temp = *p;
	*p = *q;
	*q = temp;
}

void insertsort(int arr[],int len)
{
    int temp = 0;
    size_t i, j;
    for (i = 1; i < len; i++)
    {
        temp = arr[i];
        j = i - 1;
        /*for (j = i - 1; j >= 0 && arr[j] > temp; j--)
        {
            arr[j + 1] = arr[j];
        }*/
        while ( j >= 0 && arr[j] > temp )
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
}


int Median3(int arr[], int left, int right)
{
    int mid = left + (right - left) >> 1;
    if (arr[left] > arr[mid])
    {
        Swap(&arr[left], &arr[mid]);
    }
    if (arr[left] > arr[right])
    {
        Swap(&arr[left], &arr[right]);
    }
    if (arr[mid] > arr[right])
    {
        Swap(&arr[right], &arr[mid]);
    }
    Swap(&arr[mid], &arr[right-1]);
    
    // return pivot
    return arr[right - 1];
}


void Qsort(int arr[], int left, int right)
{
    int i, j, pivot;
    if(left+3>=right)
    {
        pivot = Median3(arr, left, right);
        i = left;
        j = right - 1;
        for (  ;   ; )
        {
            while (arr[++i] < pivot)    {}
            while (arr[--j] > pivot)    {}
            if (i<j)
            {
                Swap(&arr[i], &arr[j]);
            }
            else
            {
                break;
            }
        }
        Swap(&arr[i], &arr[right-1]);

        Qsort(arr, left, i - 1);
        Qsort(arr, i + 1, right);
    }
    else
    {
        insertsort(arr, right - left + 1);
    }
}

void Quicksort(int arr[], int len)
{
    Qsort(arr, 0, len - 1);
}


int main(void)
{

    int arr[] = {1, 5, 3, 2, 6, 7, 2, 54};

    Quicksort(arr, 8);

    for (size_t i = 0; i < 8; i++)
    {
        printf("%d\t", arr[i]);
    }
    
    return 0;
}