0


常见的排序算法(下)


联系方式(qq):623847465 gitee(码云):
Mercury. (zzwlwp) - Gitee.com

我一路种下了蘑菇,只是为了让你知道回家的路。🍂

程序猿:我宁愿写bug,也不愿什么都不做! 🐵


上期学习完了前四个排序,这期我们来学习剩下的三个排序:

🍔 1、冒泡排序

🍟 2、快速排序 ( 三种方法 )

🍞 3、归并排序

🧀 4、****排序算法复杂度及稳定性分析

今天我们主要难点有快速排序归并排序会简单涉及到二叉树相关知识,相对来说比较抽象!所以如果有看不懂或者不明白的地方可以看看我之前的详解二叉树,也可以直接问我!教你打篮球的程序猿随时在线。👴


🍔 1、冒泡排序

冒泡排序是我们相对最好理解的个排序,但是有些小优化的地方我会指出来,我们先看图解:

void BubbleSort(int* a, int n)//升序
{
    //时间复杂度O(N^2)
    while (n > 0)
    {
        int exchange = 0;
        for (int i = 1; i < n; ++i)//防止越界访问
        {
            if (a[i - 1] > a[i])
            {
                Swap(&a[i - 1], &a[i]);//交换
                exchange = 1;
            }
        }
        if (exchange == 0)
        {
            break;
        }
        --n;
    }
}

代码分析:我们每排完一趟,就可以确定最后一个位置的数,再者我们定义了一个exchange来判断在排序过程中是否发生了交换,如果没有发生交换,证明此数组已经有序,我们可以直接跳出循环,避免不必要的循环!

冒泡排序的特性总结:

  1. 冒泡排序是一种非常容易理解的排序

  2. 时间复杂度:O(N^2) 、空间复杂度:O(1)

  3. 稳定性:稳定


🍟 2、快速排序 ( 三种方法 )

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。

**基本思想为:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。 **

**第一种方法是我们最常见的挖坑法: **

** 代码实现如下:**

void QuickSort(int* a, int left, int right)//升序
{
    if (left >= right)
    {
        return;
    }

    int begin = left;
    int end = right;
    int pivot = begin;
    int key = a[begin];

    while (begin < end)
    {
        //右边找小
        while (begin < end && a[end] >= key) //这里如果不写begin<end的话可能会出现越界访问
        {
            --end;
        }
        //小的放到左边的坑里,自己形成了新的坑位
        a[pivot] = a[end];
        pivot = end;
        
        //左边找大
        while (begin < end && a[begin] <= key)
        {
            ++begin;
        }
        //大的放到左边的坑里,自己形成了新的坑位
        a[pivot] = a[begin];
        pivot = begin;
    }

    //当begin和end相遇,证明他们两都到了坑的位置
    pivot = begin;//随便给一个
    a[pivot] = key;

    //[left, pivot - 1] pivot [pivot+ 1, right]
    //左子区间和右子区间有序,我们就有序了,如何让他们有序呢?分治递归
    QuickSort(a, left, key - 1);
    QuickSort(a, key + 1, right);
}

//函数传参:QuickSort(arr, 0, sizeof(arr) / sizeof(int) - 1);

** 第二种方法左右指针法:**

** 代码实现如下:**

void QuickSort(int* a, int left, int right)//升序
{
    if (left >= right)
    {
        return;
    }

    int begin = left;
    int end = right;
    int keyi = begin;

    while (begin < end)
    {
        //找小
        while (begin < end && a[end] >= a[keyi])
        {
            --end;
        }
        //找大
        while (begin < end && a[begin] <= a[keyi])
        {
            ++begin;
        }
        Swap(&a[begin], &a[end]);
    }

    Swap(&a[begin], &a[keyi]);
    keyi = begin;

    //[left, keyi - 1] keyIndex [keyi + 1, right]
    //左子区间和右子区间有序,我们就有序了,如何让他们有序呢?分治递归

    QuickSort(a, left, keyi - 1);
    QuickSort(a, keyi + 1, right);
}

** 第三种方法前后指针法:**

**代码实现如下: **

void QuickSort(int* a, int left, int right)//升序
{
    if (left >= right)
    {
        return;
    }

    int keyi = left;
    int prev = left;
    int cur = left + 1;
    while (cur <= right)
    {
        //++prev != cur为了防止自己跟自己交换造成不必要的消耗
        if (a[cur] < a[keyi] && ++prev != cur)
        {
            Swap(&a[prev], &a[cur]);
        }
        ++cur;
    }
    Swap(&a[keyi], &a[prev]);
    keyi = prev;
    
    //[left, keyi - 1] keyi [keyi + 1, right]
    //左子区间和右子区间有序,我们就有序了,如何让他们有序呢?分治递归

    QuickSort(a, left, keyi - 1);
    QuickSort(a, keyi + 1, right);
}

🍞 3、归并排序

基本思想: 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法 (Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

归并排序我们思想还是和快排思想差不多采用分治算法,当数组被分为单独一个元素就是有序的了(见上图),在接着归并到一个数组中,即可实现排序!

** 代码实现如下:**

void _MergeSort(int* a, int left, int right, int* tmp)
{
    if (left >= right)
        return;

    int mid = (left + right) >> 1;
    // 假设[left, mid] [mid + 1, right] 有序,那么我们就可以归并了
    _MergeSort(a, left, mid, tmp);
    _MergeSort(a, mid + 1, right, tmp);

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

    while (begin1 <= end1)
    {
        tmp[index++] = a[begin1++];
    }

    while (begin2 <= end2)
    {
        tmp[index++] = a[begin2++];
    }

    //拷贝回去
    for (int i = left; i <= right; ++i)
    {
        a[i] = tmp[i];
    }
}

void MergeSort(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    _MergeSort(a, 0, n - 1, tmp);

    free(tmp);
}

🧀 4、排序算法复杂度及稳定性分析

稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍 在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。


I can do all things(我能做成任何事!)相信自己,加油!

联系方式(qq):623847465 gitee(码云):Mercury. (zzwlwp) - Gitee.com

下期预告:待定😁


本文转载自: https://blog.csdn.net/m0_61784621/article/details/123794336
版权归原作者 程序猿教你打篮球 所有, 如有侵权,请联系我们删除。

“常见的排序算法(下)”的评论:

还没有评论