[数据结构与算法]排序算法实现

排序

#include<stdio.h>
void Swap(int* p1, int* p2)
{
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

// 冒泡排序
void BuubleSort(int* arr, int arrlen)
{
    for (int i = 0; i < arrlen; i++)
    {
        for (int j = 1; j < arrlen; j++)
        {
            if (arr[j - 1] > arr[j])
            {
                Swap(&arr[j - 1], &arr[j]);
            }
        }
    }
}

// 选择排序
void SelectSort(int* arr, int arrlen)
{
    int begin = 0;
    int end = arrlen - 1;

    while (begin <= end)
    {
        int maxi = begin;
        int mini = begin;
        for (int i = begin; i <= end; i++)
        {
            if (arr[i] > arr[maxi])
            {
                maxi = i;
            }

            if (arr[i] < arr[mini])
            {
                mini = i;
            }
        }

        Swap(&arr[begin], &arr[mini]);
        if (maxi == begin)
        {
            maxi = mini;
        }
        Swap(&arr[maxi], &arr[end]);

        end--;
        begin++;
    }
}
//插入排序
void InsertSort(int* arr, int arrlen)
{
    for (int i = 0; i < arrlen - 1; i++)
    {
        int end = i;
        int key = arr[end + 1];
        /*while (end >= 0)
        {
            while (arr[end] > key)
            {
                arr[end + 1] = arr[end];
                end--;
            }
            arr[end + 1] = key;
            break;
        }
        */
        while (end >= 0)
        {
            if (arr[end] > key)
            {
                arr[end + 1] = arr[end];
                end--;
            }
            else
            {
                break;
            }
        }
        arr[end + 1] = key;
    }
}

//希尔排序通过
void ShellSort(int* arr, int arrLen)
{
    int gap = arrLen;
    while (gap > 1)
    {
        gap = gap / 2;

        for (int i = 0; i < arrLen - gap; i++)
        {
            int end = i;
            int key = arr[end + gap];

            while (end >= 0)
            {
                if (arr[end] > key)
                {
                    arr[end + gap] = arr[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            arr[end + gap] = key;
        }

    }
}

//挖坑法的快速排序
int PartSort(int* arr, int left, int right)
{
    int pvoit = left;
    int key = arr[pvoit];
    while (left < right)
    {
        while (left < right && arr[right] >= key)
        {
            right--;
        }
        arr[pvoit] = arr[right];
        pvoit = right;

        while (left < right && arr[left] <= key)
        {
            left++;
        }
        arr[pvoit] = arr[left];
        pvoit = left;
    }
    arr[pvoit] = key;
    return  pvoit;
}

void QuickSort(int* arr, int left, int right)
{
    if (left >= right)
    {
        return;
    }
    int pvoit = PartSort(arr, left, right);
    QuickSort(arr, left, pvoit - 1);
    QuickSort(arr, pvoit + 1, right);

}

//归并排序
void _MergeSort(int* arr, int left, int right, int* tmp)
{
    if (left >= right)
    {
        return;
    }
    int mid = (left + right) >> 1;
    _MergeSort(arr, left, mid, tmp);
    _MergeSort(arr, mid + 1, right, tmp);

    int begin1 = left;
    int end1 = mid;
    int begin2 = mid + 1;
    int end2 = right;
    int index = left;
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (arr[begin1] < arr[begin2])
        {
            tmp[index++] = arr[begin1++];
        }
        else
        {
            tmp[index++] = arr[begin2++];
        }
    }

    while (begin1 <= end1)
    {
        tmp[index++] = arr[begin1++];
    }
    while (begin2 <= end2)
    {
        tmp[index++] = arr[begin2++];
    }

    for (int i = left; i <= right; i++)
    {
        arr[i] = tmp[i];
    }

}
void MergeSort(int* arr, int left, int right)
{
    int* tmp = (int*)malloc(sizeof(int) * (right - left + 1));
    _MergeSort(arr, left, right, tmp);
    free(tmp);
    tmp = NULL;

}

void AdjustDwon(int* arr, int arrLen, int root)
{
    int parent = root;
    int child = parent * 2 + 1;//默认是左孩子

    while (child < arrLen)
    {
        if (child + 1 < arrLen && arr[child + 1] > arr[child])
        {
            child += 1;
        }

        if (arr[child] > arr[parent])
        {
            Swap(&arr[child], &arr[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}
void HeapSort(int* arr, int arrLen)
{
    //建堆
    for (int i = (arrLen - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDwon(arr, arrLen, i);
    }

    int end = arrLen - 1;
    while (end > 0)
    {
        Swap(&arr[0], &arr[end]);
        AdjustDwon(arr, end, 0);
        end--;
    }
}
int* MySort(int* arr, int arrLen, int* returnSize)
{
    // write code here
    //BuubleSort(arr, arrLen);
    //SelectSort(arr, arrLen);
    //InsertSort(arr, arrLen);
    //ShellSort(arr, arrLen);
    //MergeSort(arr, 0, arrLen - 1);
    //HeapSort(arr, arrLen);
    QuickSort(arr, 0,arrLen - 1);
    *returnSize = arrLen;
    return arr;
}