侧边栏壁纸
  • 累计撰写 278 篇文章
  • 累计创建 3 个标签
  • 累计收到 1 条评论

目 录CONTENT

文章目录

【算法】快速排序

xuanxuan
2021-10-24 / 0 评论 / 0 点赞 / 7 阅读 / 2242 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2024-02-14,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

快速排序

排序流程

  1. 每次选区第一个的数为基准数
  2. 然后将大于和小于基准的元素分别置于基准数两边
  3. 继续分别对基准数两侧未排序的数据使用分治法进行细分处理(分而治之),直至整个序列有序。

如下图所示在这里插入图片描述在这里插入图片描述

代码实现:

#include<iostream>
using namespace std;

void print(int* arr, int len)
{
    for (int i = 0; i < len; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int parttion(int arr[], int low, int high)
{
    int i = low;//从左边开始
    int j = high;//从右边开始

    int base = arr[low];//定左边第一个为基准书,拿出来之后,该位置就可以被覆盖了

    //如果low就是最
    if (low < high)
    {
        //左找一个,右找一个......
        while (i < j) //i == j说明已经查找完毕
        {
            while (i < j && arr[j] >= base)//从右边开始遍历,比基准值大,不做改变,继续遍历,直到碰到比基准值小的
            {
                j--;
            }
            if (i < j)//右边找到小于基数的数
            {
                arr[i++] = arr[j];

            }
            while (i < j && arr[i] < base)//从左边开始遍历,比基准值小,不做改变,继续遍历,直到碰到比基准值大的
            {
                i++;
            }
            if (i < j)//左边已经找到大于基数的数
            {
                arr[j--] = arr[i];
            }
        }
        //查找完毕
        //将基准值放入它应该在的位置
        arr[i] = base;
    }   
    //返回基准值位置
    return i;
}

void QuickSort(int* arr,int low, int high)
{
    if (low < high)
    {
        int index = parttion(arr, low, high);//寻找基准值,然后开始分而治之
        //index这个位置的数已经是它该放的位置
        QuickSort(arr, low, index - 1);
        QuickSort(arr, index + 1, high);
    }
}

int main(void)
{
    int arr[] = { 3,1,4,5,5,4,1,3 };
    int len = sizeof(arr) / sizeof(arr[0]);
    QuickSort(arr, 0, len - 1);
    print(arr, len);
    return 0;
}
0

评论区