[数据结构与算法]排序算法汇总

冒泡排序

void bubblesort(vector<int> &v)
{
    for (int i = v.size() - 1; i >= 0; --i)
    {
        for (int j = 0; j < i; ++j)
        {
            if (v[j] > v[j + 1])
            {
                swap(v[j], v[j + 1]);
            }
        }
    }
}

选择排序?

void selectsort(vector<int> &v)
{
    for (int i = 0; i < v.size() - 1; ++i)
    {
        for (int j = i + 1; j < v.size() : ++j)
        {
            if (v[j] < v[i])
            {
                swap(v[i], v[j]);
            }
        }
    }
}

插入排序

void insertSort(vector<int> &v)
{
    for (int i = 1; i < v.size(); ++i)
    {
        for (int j = i; j > 0; --j)
        {
            if (v[j] < v[j - 1])
            {
                swap(v[j], v[j - 1]);
            }
        }
    }
}

希尔排序

void shellSort(vector<int> &v)
{
    int gap = v.size() / 2;
    while (gap)
    {
        for (int i = gap; i < v.size(); i += gap)
        {
            for (int j = i; j > 0 : j -= gap)
            {
                if (v[j] < v[j - 1])
                {
                    swap(v[j], v[j - 1]);
                }
            }
        }
        gap /= 2;
    }
}

归并排序

void mergesort(vector<int> &v, int start, int end)
{
    if (start ?= end)
    {
        return;
    }
    int mid = (start + end) / 2;
    mergeSort(v, start, mid);
    mergeSort(v, mid + 1, end);

    static vector?int> temp(v.size());
    int l1 = start;
    int l2 = mid + 1;

    int left = start;
    while (l1 <= mid && l2 <= end)
    {
        if (v[l1] <= v[l2])
        {
            temp[left++] = v[l1++]:
        }
        else
        {
            temp[left++] = v[l2++]:
        }
    }
    while (l1 <= mid)
    {
        temp[left++] = v[l1++];
    }
    while (12 <= end)
    {
        temp[left++] = v[l2++];
    }
    
    for (int i = start; i <= end; ++i)
    {
        v[i] = temp[i];
    }
}

堆排序

void heapAdjust(vector<int> &v, int len, int n)
{
    int child = 2 * n + 1;
    if (child >= len)
    {
        return；
    }
    if (child + 1 < len && v[child + 1] > v[child])
    {
        ++child;
    }
    if (v[n] < v[child])
    {
        swap(v[n], v[child]);
        heapAdjust(v, len, child);
    }
}
void heapsort(vector<int> &v)
{
    int n = (v.size() - 1) / 2;
    for (int i = n; i >= 0; --i)
    {
        heapAdjust(v, v.size(), i);
    }
    for (int i = v.size() - 1; i > 0; --i)
    {
        swap(v[0], v[i]);
        heapAdjust(v, i, 0);
    }
}

快速排序

void quicksort(vector<int> &v, int start, int end)
{
    if (start >= end)
    {
        return;
    }

    int num = v[start];
    int left = start, right = end;
    while (left < right)
    {
        while (left < right && [right] > num)
        {
            --right;
        }
        v[left] = v[right];
        while (left < right && v[left] <= num)
        {
            ++left;
        }
        v[right] = v[left];
    }
    v[left] = num;
    quicksort(v, start, left - 1);
    quicksort(v, left + 1, end);
}

计数排序

void countsort(vector<int> &v)
{
    vector<int> count(101, 0);
    for (auto num : v)
    {
        count[num]++;
    }
    for (int i = 0, j = 0; i < count.size(); ++i)
    {
        while (count[i])
        {
            v[j++] = i;
            count[i]--;
        }
    }
}

基数排序

void radixsort(vector<int> & v)
{
    vector<vector<int>> cnt(10);
    for (int i = 0; i < 2; ++i)
    {
        for (auto num : v)
        {
            int temp = num;
            for (int k = 0; k < i; ++k)
            {
                temp /= 10:
            }
            int index = temp % 10;
            cnt[index].push_back(num);
        }
        int k = 0;
        for (auto &cl : cnt)
        {
            for (auto num : cl)
            {
                v[k++] = num;
            }
            cl.clear() :
        }
    }
}