【数据结构】排序

插入排序

// 直接插入排序
void InsertSort(int A[], int n)
{
    int i, j, temp;
    for (i = 1; i < n; i++)
    {
        if (A[i] < A[i - 1])
        {
            temp = A[i];
            for (j = i - 1; j >= 0 && A[j] > temp; j--)
                A[i + 1] = A[j];
            A[j + 1] = temp;
        }
    }
}

// 直接插入排序（带哨兵版）
void InsertSort1(int A[], int n)
{
    int i, j;
    // 依次将A[2]~ A{n}插入已排序序列，A[0]不存放元素
    for (i = 2; i <= n; i++)
    {
        // 若A[i]关键码小于其前驱
        if (A[i] < A[i - 1])
        {
            // 将A[i]的关键码复制为哨兵
            A[0] = A[i];
            for (j = i; A[0] < A[j]; --j)
                A[j + 1] = A[j];
            A[j + 1] = A[0];
        }
    }
}

// 折半插入排序
void InsertSort2(int A[], int n)
{
    int i, j, low, high, mid;
    for (i = 2; i <= n; i++)
    {
        A[0] = A[i];
        low = 1;
        high = i - 1;
        while (low <= high)
        {
            mid = (high + low) / 2;
            if (A[mid] > A[0])
                high = mid - 1;
            else
                low = mid + 1;
        }
        for (j = i - 1; j >= high + 1; --j)
            A[j + 1] = A[j];
        A[high + 1] = A[0];
    }
}

// 希尔排序
void ShellSort(int A[], int n)
{
    int dk, i, j;
    for (dk = n / 2; dk >= 1; dk = dk / 2)
    {
        for (i = dk + 1; i <= n; ++i)
        {
            if (A[i] < A[i + dk])
            {
                A[0] = A[i];
                for (j = i - dk; j > 0 && A[0] < A[j]; j -= dk)
                    A[j + dk] = A[j];
                A[j + dk] = A[0];
            }
        }
    }
}

交换排序

// 冒泡排序
void BubbleSort(int A[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        bool flag = false;
        for (int j = n - 1; j > i; j--)
        {
            if (A[j - 1] > A[j])
            {
                int tmp = A[j - 1];
                A[j - 1] = A[j];
                A[j] = tmp;
            }
            flag = true;
        }
        if (flag == false)
            return;
    }
}

// 快速排序

// 划分操作
int Partition(int A[], int low, int high)
{
    int pivot = A[low];
    while (low < high)
    {
        while (low < high && A[high] >= pivot)
            --high;
        A[low] = A[high];
        while (low < high && A[low] <= pivot)
            ++low;
        A[high] = A[low];
    }
    A[low] = pivot;
    return low;
}

void QuickSort(int A[], int low, int high)
{
    if (low < high)
    {
        int pivotpos = Partition(A, low, high);
        QuickSort(A, low, pivotpos - 1);
        QuickSort(A, pivotpos + 1, high);
    }
}

选择排序

// 冒泡排序
void BubbleSort(int A[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        bool flag = false;
        for (int j = n - 1; j > i; j--)
        {
            if (A[j - 1] > A[j])
            {
                int tmp = A[j - 1];
                A[j - 1] = A[j];
                A[j] = tmp;
            }
            flag = true;
        }
        if (flag == false)
            return;
    }
}

// 快速排序

// 划分操作
int Partition(int A[], int low, int high)
{
    int pivot = A[low];
    while (low < high)
    {
        while (low < high && A[high] >= pivot)
            --high;
        A[low] = A[high];
        while (low < high && A[low] <= pivot)
            ++low;
        A[high] = A[low];
    }
    A[low] = pivot;
    return low;
}

void QuickSort(int A[], int low, int high)
{
    if (low < high)
    {
        int pivotpos = Partition(A, low, high);
        QuickSort(A, low, pivotpos - 1);
        QuickSort(A, pivotpos + 1, high);
    }
}

归并排序、基数排序和计数排序

// 归并排序
int n;
int *B = (int *)malloc((n + 1) * sizeof(int));

void Merge(int A[], int low, int mid, int high)
{
    int i, j, k;
    for (k = low; k <= high; k++)
        B[k] = A[k];
    for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++)
    {
        if (B[i] <= B[j])
            A[k] = B[i++];
        else
            A[k] = A[j++];
    }
    while (i <= mid)
        A[k++] = A[i++];
    while (j <= high)
        A[k++] = A[j++];
}

void MergeSort(int A[], int low, int high)
{
    if (low < high)
    {
        int mid = (low + high) / 2;
        MergeSort(A, low, mid);
        MergeSort(A, mid + 1, high);
        Merge(A, low, mid, high);
    }
}

// 基数排序 -> 没有代码

// 计数排序
void CountSort(int A[], int B[], int n, int k)
{
    int i, C[k];
    for (i = 0; i < k; i++)
    {
        C[i] = 0;
    }
    for (i = 0; i < n; i++)
    {
        C[A[i]]++;
    }
    for (i = 1; i < k; i++)
    {
        C[i] = C[i] + C[i - 1];
    }
    for (i = n - 1; i >= 0; i--)
    {
        B[C[A[i] - 1]] = A[i];
        C[A[i]] = C[A[i]] - 1;
    }
}