排序算法
2020 年 08 月 14 日 1217 1059 字 暂无评论

01.选择排序

  • 基本思想

    • 每一趟 (例如第 i 趟，i = 0, 1, …,n-2)在后面 n-i个待排的数据元素中选出关键字最小的元素, 作为有序元素序列的第 i 个元素。

  • 排序过程

    • 首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换
    • 再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换
    • 重复上述操作，共进行n-1趟排序后，排序结束

  • 代码实现
#include <iostream>     
#include <vector>   

using namespace std;

void SelectSort(vector<int>& intArray, int array_size)
{

    //选择排序思路 数组中的第一个元素和剩余的数组元素分别比较 如果第一个元素大于其他数组元素
    //交换值 一轮下来 可以确定数组中的最小(最大)值 二轮下来 确定 次最小(最大)值 
    for (int i = 0; i < array_size - 1; i++)
    {
        for (int j = i + 1; j < array_size; j++)
        {
            int temp;
            if (intArray[i] > intArray[j])
            {
                temp = intArray[i];
                intArray[i] = intArray[j];
                intArray[j] = temp;
            }
        }
    }
}

int main() {
    vector<int> intArray{ 1,4,2,9,5,6 };
    int array_size = intArray.size();
    SelectSort(intArray, array_size);
    for (auto& a : intArray)
    {
        cout << a << " ";
    }
    return 0;
}

02.插入排序

  • 基本思路

    • 整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序
    • 实质：对线性表执行n-1次插入操作，只是先要找到插入位置
    • V[0], V[1], …, V[i-1]已经排好序。这时已经排好序。这时,用V[i]的关键字与V[i-1], V[i-2], …的关键字进行比较, 找到插入位置即将V[i]]插入, 原来位置上的对象向后顺移。

    • 插入排序关键点：

      • 拿出一个元素，留出位置
      • 符合条件的元素后移

  • 代码实现
#include <iostream>     
#include <vector>   

using namespace std;

void Inert_Sort(vector<int>& arry, int len)
{
    int i, j;
    for (i = 1; i < len; ++i)
    {
        int temp = arry[i];
        for (j = i - 1; j >= 0; --j)
        {
            if (temp < arry[j])
            {//在有序列表中比temp值大的元素后羿            
                arry[j + 1] = arry[j];    
            }
            else { break; }//temp大于有序表中的最后一位则不需要移动
        }
        arry[j + 1] = temp;//跳出内层循环后插入在合适的位置
    }
}

int main() {
    vector<int> intArray{ 1,4,2,9,5,6 };
    int array_size = intArray.size();
    Inert_Sort(intArray, array_size);
    for (auto& a : intArray)
    {
        cout << a << " ";
    }
    return 0;
}

03.冒泡排序

  • 排序过程

    • 将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序r[1].key>r[2].key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上。
    • 对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置
    • 重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作“为止。

  • 代码实现
#include <iostream>     
#include <vector>   

using namespace std;

void Bubble_Sort(vector<int>& arry,int len)
{
    for (int i = 0; i < len; i++)
    {
        for (int j = i+1; j < len; j++)
        {
            if (arry[j] < arry[j-1])
            {
                int tmp = arry[j];
                arry[j] = arry[j-1];
                arry[j-1] = tmp;
            }
        }
    }
}

int main() {
    vector<int> intArray{ 1,4,2,9,5,6 };
    int array_size = intArray.size();
    Bubble_Sort(intArray, array_size);
    for (auto& a : intArray)
    {
        cout << a << " ";
    }
    return 0;
}

04.希尔排序

  • 排序过程

    • 先取一个正整数d1<n，把所有相隔d1的记录放一组，组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止
    • O(nlogn)
    • 希尔排序是不稳定的。

  • 代码实现
#include <iostream>     
#include <vector>   

using namespace std;

void Shell_Sort(vector<int>& array, int n)  //a -- 待排序的数组, n -- 数组的长度
{
    int i, j, gap;   // gap为步长，每次减为原来的一半。
    for (gap = n / 2; gap > 0; gap /= 2)
    {
        // 共gap个组，对每一组都执行直接插入排序
        for (i = 0; i < gap; i++)
        {
            for (j = i + gap; j < n; j += gap)
            {
                // 如果a[j] < a[j-gap]，则寻找a[j]位置，并将后面数据的位置都后移。
                if (array[j] < array[j - gap])
                {
                    int tmp = array[j];
                    int k = j - gap;
                    while (k >= 0 && array[k] > tmp)
                    {
                        array[k + gap] = array[k];
                        k -= gap;
                    }
                    array[k + gap] = tmp;
                }
            }
        }
    }
}


int main() {
    vector<int> intArray{ 1,4,2,9,5,6 };
    int array_size = intArray.size();
    Shell_Sort(intArray, array_size);
    for (auto& a : intArray)
    {
        cout << a << " ";
    }
    return 0;
}

05.快速排序

  • 基本思路

    • 快速排序是对冒泡排序的一种改进。
    • 通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，基准数据排在这两个子序列的中间。
    • 然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

#include <iostream>     
#include <vector>   

using namespace std;

int partition(vector<int>& a, int p, int r) {
    int key = a[r];//取最后一个
    int i = p - 1;
    for (int j = p; j < r; j++)
    {
        if (a[j] <= key)
        {
            i++;
//i一直代表小于key元素的最后一个索引，当发现有比key小的a[j]时候，i+1 后交换     
            int temp1 = a[j];
            a[j] = a[i];
            a[i] = temp1;
        }
    }
    int temp2 = a[r];
    a[r] = a[i + 1];
    a[i + 1] = temp2;
    return i + 1;
}

void Quick_Sort(vector<int>& a, int p, int r) {
    int position = 0;
    if (p < r)
    {
        position = partition(a, p, r);//返回划分元素的最终位置
        Quick_Sort(a, p, position - 1);//划分左边递归
        Quick_Sort(a, position + 1, r);//划分右边递归
    }
}


int main() {
    vector<int> intArray{ 1,4,2,9,5,6 };
    int array_size = intArray.size();
    Quick_Sort(intArray, 0,array_size-1);
    for (auto& a : intArray)
    {
        cout << a << " ";
    }
    return 0;
}
//单路快排
#include <iostream>     
#include <vector>   

using namespace std;

int partition(vector<int>& vec,int l,int r){
    swap(vec[r],vec[rand()%(r-l+1)+l]); //优化
    int key = vec[r];
    int i=l-1;
    for(int j=l;j<r;j++){
        if(vec[j] <= key){
            i++;
            swap(vec[i],vec[j]);
        }
    }
    i++;
    swap(vec[i],vec[r]);
    return i;
}

void Quick_Sort(vector<int>& vec,int l,int r){
    int p = 0;
    if(l < r){
        srand(time(NULL)); //优化
        p = partition(vec,l,r);
        Quick_Sort(vec,l,p-1);
        Quick_Sort(vec,p+1,r);
    }
}

int main() {
    vector<int> intArray{ 1,4,2,9,5,6 };
    int array_size = intArray.size();
    Quick_Sort(intArray, 0,array_size-1);
    for (auto& a : intArray)
    {
        cout << a << " ";
    }
    return 0;
}
//双路快排
#include <iostream>     
#include <vector>   

using namespace std;

int partition2(vector<int>& vec,int l,int r){
    swap(vec[l],vec[rand()%(r-l+1)+l]); //优化
    int key = vec[l];
    int i = l+1, j = r;
    while(true){
        while(i <= r && vec[i] < key)i++;
        while(j >= l+1 && vec[j] > key)j--;
        if(i>j)break;
        swap(vec[i],vec[j]);
        i++;
        j--;
    }
    swap(vec[l],vec[j]);
    return j;
}

void Quick_Sort2(vector<int>& vec,int l,int r){
    int p = 0;
    if(l < r){
        srand(time(NULL)); //优化
        p = partition2(vec,l,r);
        Quick_Sort(vec,l,p-1);
        Quick_Sort(vec,p+1,r);
    }
}

int main() {
    vector<int> intArray{ 1,4,2,9,5,6 };
    int array_size = intArray.size();
    Quick_Sort2(intArray, 0,array_size-1);
    for (auto& a : intArray)
    {
        cout << a << " ";
    }
    return 0;
}
//三路快排
#include <iostream>     
#include <vector>   

using namespace std;

void Quick_Sort3(vector<int>& vec,int l,int r){
    if(l < r){
        srand(time(NULL)); //优化
        swap(vec[l],vec[rand()%(r-l+1)+l]); //优化
        int key = vec[l];

        int lt = l;
        int gt = r+1;
        int i = l+1;
        while(i<gt){
            if(vec[i] < key){
                swap(vec[i++],vec[++lt]);
            }
            else if(vec[i] > key){
                swap(vec[i],vec[--gt]);
            }
            else{
                ++i;
            }
        }
        swap(vec[l],vec[lt]);

        Quick_Sort3(vec,l,lt-1);
        Quick_Sort3(vec,gt,r);
    }
}

int main() {
    vector<int> intArray{ 1,4,2,9,5,6 };
    int array_size = intArray.size();
    Quick_Sort3(intArray, 0,array_size-1);
    for (auto& a : intArray)
    {
        cout << a << " ";
    }
    return 0;
}

06.归并排序

  • 算法思路

    • 比较a[i]和b[j]的大小，若a[i]≤b[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1。否则将第二个有序表中的元素b[j]复制到r[k]中，并令j和k分别加上1。
    • 如此循环下去，直到其中一个有序表取完。
    • 然后再将另一个有序表中剩余的元素复制到r中下标k到下标t的单元。

  • 代码实现
#include <iostream>     
#include <vector>   

using namespace std;

void merge(vector<int>& arr, int L, int mid, int R)
{
    vector<int> help(R - L + 1,0);
    int p1 = L, p2 = mid + 1, i = 0;
    while (p1 <= mid && p2 <= R)
    {
        help[i++] = arr[p1] > arr[p2] ? arr[p2++] : arr[p1++];
    }
    while (p1 <= mid)
        help[i++] = arr[p1++];
    while (p2 <= R)
        help[i++] = arr[p2++];

    for (int i = 0; i < R - L + 1; i++)
    {
        arr[L + i] = help[i];
    }
}
void sortprocess(vector<int>& arr, int L, int R)
{
    if (L < R)
    {
        int mid = L + ((R - L) >> 1);  //  (L+R)/2
        sortprocess(arr, L, mid);
        sortprocess(arr, mid + 1, R);
        merge(arr, L, mid, R);
    }
}

void Merge_Sort(vector<int>& arr, int L, int R)
{
    if (arr.size() < 2)
        return;
    sortprocess(arr, L, R);
}


int main() {
    vector<int> intArray{ 1,4,2,9,5,6 };
    int array_size = intArray.size();
    Merge_Sort(intArray, 0,array_size-1);
    for (auto& a : intArray)
    {
        cout << a << " ";
    }
    return 0;
}
无标签

评论已关闭