插入排序、希爾排序、快速排序

插入排序：

void insertSort(int array[], int n)
{
    int temp = 0;
    int j = 0;
    for (int i = 1; i < n; i++)
    {
        if (array[i] < array[i - 1])//目前值小于有序序列的最大值
        {
            temp = array[i];
            for (j = i - 1; temp < array[j]; j--)//檢索目前值合适的插入位置，并進行移動
            {
                array[j + 1] = array[j];
            }
            array[j + 1] = temp;
        }
    }
}
           

希爾排序：

void sheelSort(int array[], int len)
{
    int gap = 0;
    int m = 0, i = 0, j = 0;
    for (gap = len / 2; gap > 0; gap /= 2)//步長gap
    {
        for (i = 0; i < gap; i++) //分為gap個組
        {
            for (j = i + gap; j < len; j += gap)//每組分别進行插入排序
            {
                if (array[j] < array[j - gap])
                {
                    int temp = array[j];
                    //尋找插入位置
                    for (m = j - gap; array[m] > temp && m >= 0; m -= gap)
                    {
                        array[m + gap] = array[m];
                    }
                    array[m + gap] = temp;
                }
            }
        }
    }
}
           

快速排序：

void quickSort(int array[], int left, int right)
{
    if (left >= right)
    {
        return;
    }

    int base = array[left];//base設定為最左邊的點
    int leftIndex = left;
    int rightIndex = right;

    while (leftIndex < rightIndex)//左右遊标依次周遊
    {
        //自右向左尋找第一個小于base的值
        while (leftIndex < rightIndex && array[rightIndex] >= base)
        {
            rightIndex--;
        }
        //自左向右尋找第一個大于base的值
        while (leftIndex < rightIndex && array[leftIndex] <= base)//
        {
            leftIndex++;
        }
        //交換這兩個值的位置
        if (leftIndex < rightIndex)//
        {
            int temp = array[leftIndex];
            array[leftIndex] = array[rightIndex];
            array[rightIndex] = temp;
        }
    }
    //将左遊标指向的值與base交換，将base置于中間
    array[left] = array[leftIndex];
    array[leftIndex] = base;
    //基于分治法進行遞歸
    quickSort(array, left, rightIndex - 1);
    quickSort(array, rightIndex + 1, right);
    
}