sort.cs

void swap(int arr[], int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

//bubble
void f1(int arr[], int length)
{
    for (int i = 0; i < length - 1; i++)
    {
        for (int j = 0; j < length - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                swap(arr, j, j + 1);
            }
        }
    }
}

//selection
void f2(int arr[], int length)
{
    for (int i = 0; i < length - 1; i++)
    {
        int indexOfMin = i;
        for (int j = i; j < length; j++)
        {
            if (arr[indexOfMin] > arr[j])
            {
                indexOfMin = j;
            }
        }
        swap(arr, i, indexOfMin);
    }
}

//insertion
void f3(int arr[], int length)
{
    for (int i = 0; i < length - 1; i++)
    {
        int last = arr[i + 1];
        int j;
        for (j = i + 1; j >= 1 && arr[j - 1] > last; j--)
        {
            arr[j] = arr[j - 1];
        }
        arr[j] = last;
    }
}

//shell
void f4(int arr[], int length)
{
    int gap = length / 2;
    while (gap != 0)
    {
        for (int h = 0; h < gap; h++)
        {
            //gap为1时，等效于平常的插入排序
            for (int i = h + gap; i < length; i += gap)
            {
                int last = arr[i];
                int j;
                for (j = i; j >= gap && arr[j - gap] > last; j -= gap)
                {
                    arr[j] = arr[j - gap];
                }
                arr[j] = last;
            }
        }
        gap = gap / 2;
    }
}

void QuickSort(int arr[], int first, int last)
{
    int index;
    if (first < last)
    {
        index = Partition(arr, first, last);
        QuickSort(arr, first, index - 1);
        QuickSort(arr, index + 1, last);
    }
}

int Partition(int arr[], int first, int last)
{
    int i, j, x;

    i = first + 1;
    j = last;

    x = arr[first];

    while (true)
    {
        while (arr[i] < x) i++;
        while (arr[j] > x) j--;

        if (i >= j)
            break;

        swap(arr, i, j);
    }

    arr[first] = arr[j];
    arr[j] = x;

    return j;
}