个人手撕代码一、排序相关

 相关链接：

https://blog.csdn.net/weixin_41545534/article/details/115567889?spm=1001.2014.3001.5506

​​​​​​https://blog.csdn.net/weixin_50886514/article/details/119045154?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165301469816781667834550%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=165301469816781667834550&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-119045154-null-null.142^v10^pc_search_result_control_group,157^v4^control&utm_term=%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F&spm=1018.2226.3001.4187

一、冒泡排序

#include 
#include 

using namespace std;

vector vec = {
    3,5,8,7,9,4,14,15,82,37,27,45,66,1
};

void BubbleSort(vector& vec)
{
    int n=vec.size();
    if (n == 0)
        return;
    for (int i = 0; i < n; ++i)
    {
        for (int j = i; j < n; ++j)
        {
            if (vec[i] > vec[j])
            {
                int tmp = vec[j];
                vec[j] = vec[i];
                vec[i] = tmp;
            }
        }
    }
}

void PrintVec(const vector& vec)
{
    for (auto it : vec)
    {
        cout << it << " ";
    }
    cout << endl;
}

int main()
{
    PrintVec(vec);
    BubbleSort(vec);
    PrintVec(vec);
    std::cout << "Hello World!\n";
}

二、选择排序

每次外循环选择剩余最小排好。

#include 
#include 

using namespace std;

vector vec = {
    3,5,8,7,9,4,14,15,82,37,27,45,66,1
};

void ChooseSort(vector& vec)
{
    int n=vec.size();
    if (n == 0)
        return;
    for (int i = 0; i < n-1; ++i)
    {
        int smallest = i;
        for (int j = i+1; j < n; ++j)
        {
            if (vec[j] < vec[smallest])
            {
                smallest = j;
            }
        }
        int tmp = vec[i];
        vec[i] = vec[smallest];
        vec[smallest] = tmp;
    }
}

void PrintVec(const vector& vec)
{
    for (auto it : vec)
    {
        cout << it << " ";
    }
    cout << endl;
}

int main()
{
    PrintVec(vec);
    ChooseSort(vec);
    PrintVec(vec);
    std::cout << "Hello World!\n";
}

三、插入排序

#include 
#include 

using namespace std;

vector vec = {
    3,5,8,7,9,4,14,15,82,37,27,45,66,1
};

void InsertSort(vector& vec)
{
    int n=vec.size();
    if (n == 0)
        return;
    for (int i = 1; i < n; ++i)
    {
        for (int j = i; j >=1; --j)
        {
            if (vec[j-1] >  vec[j])
            {
                int tmp = vec[j-1];
                vec[j-1] = vec[j];
                vec[j] = tmp;
            }
        }

    }
}

void PrintVec(const vector& vec)
{
    for (auto it : vec)
    {
        cout << it << " ";
    }
    cout << endl;
}

int main()
{
    PrintVec(vec);
    InsertSort(vec);
    PrintVec(vec);
    std::cout << "Hello World!\n";
}

四、希尔排序

#include 
#include 

using namespace std;

vector vec = {
    3,5,8,7,9,4,14,15,82,37,27,45,66,1
};

void ShellSort(vector& vec)
{
    int n=vec.size();
    if (n == 0)
        return;
    int gap = n;
    while (gap > 1)
    {
        gap = gap / 2;
        //Insert Sort
        //from gap+1 on
        for (int i = gap; i < n; ++i)
        {
            for (int j = i; j >=gap; j -= gap)
            {
                if (vec[j - gap] > vec[j])
                {
                    int tmp = vec[j-gap];
                    vec[j - gap] = vec[j];
                    vec[j] = tmp;
                }
            }
        }
    }
}

void PrintVec(const vector& vec)
{
    for (auto it : vec)
    {
        cout << it << " ";
    }
    cout << endl;
}

int main()
{
    PrintVec(vec);
    ShellSort(vec);
    PrintVec(vec);
    return 0;
}

五、归并排序

#include 
#include 

using namespace std;

vector vec = {
    3,5,8,7,9,4,14,15,82,37,27,45,66,1
};

void Merge(vector& vec, int l,int m, int r)
{
    if (l >= r)
        return;
    int len = r - l + 1;
    vector tmp(len);
    int i = l, j = m + 1;
    int k = 0;
    while ((i <= m) && (j <= r))
    {
        if (vec[i] <= vec[j])
        {
            tmp[k++] = vec[i++];
        }
        else
        {
            tmp[k++] = vec[j++];
        }
    }
    while (i <= m)
    {
        tmp[k++] = vec[i++];
    }
    while (j <= r)
    {
        tmp[k++] = vec[j++];
    }
    for (k = l; k <= r; k++)
    {
        vec[k] = tmp[k-l];
    }
}

void MergeSort(vector& vec,int l,int r)
{
    if (l >= r)
        return;
    int m = (l + r) / 2;
    MergeSort(vec, l, m);
    MergeSort(vec, m+1, r);
    Merge(vec, l, m, r);
}

void PrintVec(const vector& vec)
{
    for (auto it : vec)
    {
        cout << it << " ";
    }
    cout << endl;
}

int main()
{
    PrintVec(vec);
    MergeSort(vec,0,vec.size()-1);
    PrintVec(vec);
    return 0;
}

六、快速排序

https://blog.csdn.net/qq_40941722/article/details/94396010?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165300584216780366582335%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=165300584216780366582335&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-94396010-null-null.142^v10^pc_search_result_control_group,157^v4^control&utm_term=快速排序&spm=1018.2226.3001.4187

#include 
#include 

using namespace std;

vector vec = {
    3,5,8,7,9,4,14,15,82,37,27,45,66,1
};

void QuickSort(vector& vec, int l,int r)
{
    if (l >= r)
        return;
    int pivot = vec[l];
    int i = l, j = r;
    while (i < j)
    {
        //move j
        while (pivot <= vec[j] && j > i)
        {
            j--;
        }
        while (pivot >= vec[i] && j > i)
        {
            i++;
        }
        if (i < j)
        {
            int tmp = vec[i];
            vec[i] = vec[j];
            vec[j] = tmp;
        }
    }
    vec[l] = vec[i];
    vec[i] = pivot;
    QuickSort(vec, l, i-1);
    QuickSort(vec, i+1, r);
}


void PrintVec(const vector& vec)
{
    for (auto it : vec)
    {
        cout << it << " ";
    }
    cout << endl;
}

int main()
{
    PrintVec(vec);
    QuickSort(vec,0,vec.size()-1);
    PrintVec(vec);
    return 0;
}

七、堆排序

https://blog.csdn.net/weixin_41545534/article/details/115567889?spm=1001.2014.3001.5506​​​​​​​

#include 
#include 

using namespace std;

vector vec = {
    3,5,8,7,9,4,14,15,82,37,27,45,66,1
};

void Adjust(vector& vec,int end, int idx)
{
    int left_idx = 2 * idx + 1;
    int right_idx = 2 * idx + 2;
    int max_idx=idx;
    if (left_idx < end && vec[left_idx]>vec[max_idx])
        max_idx = left_idx;
    if (right_idx < end && vec[right_idx]>vec[max_idx])
        max_idx = right_idx;
    //if changed
    if (max_idx != idx)
    {
        swap(vec[max_idx],vec[idx]);
        Adjust(vec,end, max_idx);
    }
    
}

void HeapSort(vector& vec)
{
    //Build Heap
    int n = vec.size();
    if (n == 0)
        return;
    for (int i = (n/2-1); i >=0; --i)
    {
        Adjust(vec, n,i);
    }
    //swap and re-adjust 0-i element
    for (int i = n - 1; i >= 1; --i)
    {
        swap(vec[i],vec[0]);
        Adjust(vec,i, 0);
    }
}


void PrintVec(const vector& vec)
{
    for (auto it : vec)
    {
        cout << it << " ";
    }
    cout << endl;
}

int main()
{
    PrintVec(vec);
    HeapSort(vec);
    PrintVec(vec);
    return 0;
}