Quicksort快速排序

简介: 快速排序思想
  1. 快速排序中心思想
  2. 快速排序操作实现

在这里插入图片描述

快速排序中心思想

百度描述->

快速排序算法通过多次比较和交换来实现排序,其排序流程如下 (1)首先设定一个分界值,通过该分界值将数组分成左右两部分。
(2)将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于分界值,而右边部分中各元素都大于或等于分界值。
(3)然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。
(4)重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。

总结->

基本思想

**1选定中心轴
2将大于中心轴的数字放在中心轴的右边
3将小于中心轴的数字放在中心轴的左边
4分别对左右子序列重复前三步操作**


快速排序操作实现

这边我就用C语言实现了>>

//L为要排序的起始下标,R为数组要排最后元素的下标
void QuickSort(int arr[], int L, int R)
{
    if (L >= R)            //设定结束条件
        return;
    int right = R;    //另设变量存储数组的起始位置和末尾
    int left = L;
    int point = arr[L];//选定中心轴
    while (left < right)
    {
        while (left < right && point <= arr[right])
        {                                //在left<right条件下,把比中心轴大的放在右边,小的放在左边
            right--;        //如果本身比中心轴大的数就在中心轴右边,则继续移动right
        }
        if (left < right)    //如果跳出上面循环,则一定是因为right指向的值比中心轴小,则需要把它移动到左边    
        {
            arr[left++] = arr[right];
        }
        while (left < right && point > arr[left])
        {
            left++;//如果本身比中心轴小的数就在中心轴左边,则继续移动left
        }
        if (left < right)//同样如果跳出上面循环,则一定是因为left指向的值比中心轴大,则需要把它移动到右边        
        {
            arr[right--] = arr[left];
        }    //最后两数移动到同一位置,就把刚才选中心轴的数放在这位置上
        arr[left] = point;
    }
    //上面已经进行一次排序,分成两组,一组比中心轴大,在左边,一组比中心轴小,在右边
    QuickSort(arr, L, right - 1);//递归将左边的进行排序
    QuickSort(arr, right + 1, R);//递归将右边的进行排序
}

调用一下函数

int main()
{
    int arr[10] = { 2,1,4,3,9,6,5,7,8,10 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    Quicksort(arr,0,sz-1);
    for (int i = 0; i < 10; i++)
    {
        printf("%d ", arr[i]);
    }
    return 0;
}

运行结果>
在这里插入图片描述


完事!!

在这里插入图片描述

相关文章
|
20天前
|
搜索推荐 C语言
【排序算法】快速排序升级版--三路快排详解 + 实现(c语言)
本文介绍了快速排序的升级版——三路快排。传统快速排序在处理大量相同元素时效率较低,而三路快排通过将数组分为三部分(小于、等于、大于基准值)来优化这一问题。文章详细讲解了三路快排的实现步骤,并提供了完整的代码示例。
47 4
|
2月前
|
算法 搜索推荐 Shell
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
24 1
|
2月前
|
搜索推荐 Java Go
深入了解快速排序算法
深入了解快速排序算法
39 2
|
2月前
|
存储 搜索推荐 算法
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
|
2月前
|
算法 Python
Python算法编程:冒泡排序、选择排序、快速排序
Python算法编程:冒泡排序、选择排序、快速排序
|
2月前
|
搜索推荐 C语言 C++
【C语言】指针篇-精通库中的快速排序算法:巧妙掌握技巧(4/5)
【C语言】指针篇-精通库中的快速排序算法:巧妙掌握技巧(4/5)
|
4月前
|
搜索推荐 算法 Java
现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int),已知类QuickSort的quickSort(int[])方法实现了快速排序算法
该博客文章通过UML类图和Java源码示例,展示了如何使用适配器模式将QuickSort类和BinarySearch类的排序和查找功能适配到DataOperation接口中,实现算法的解耦和复用。
45 1
现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int),已知类QuickSort的quickSort(int[])方法实现了快速排序算法
|
4月前
|
算法 搜索推荐
算法设计 (分治法应用实验报告)基于分治法的合并排序、快速排序、最近对问题
这篇文章是关于分治法应用的实验报告,详细介绍了如何利用分治法实现合并排序和快速排序算法,并探讨了使用分治法解决二维平面上的最近对问题的方法,包括伪代码、源代码实现及时间效率分析,并附有运行结果和小结。
|
5月前
|
算法 搜索推荐 编译器
算法高手养成记:Python快速排序的深度优化与实战案例分析
【7月更文挑战第11天】快速排序是编程基础,以O(n log n)时间复杂度和原址排序著称。其核心是“分而治之”,通过选择基准元素分割数组并递归排序两部分。优化包括:选择中位数作基准、尾递归优化、小数组用简单排序。以下是一个考虑优化的Python实现片段,展示了随机基准选择。通过实践和优化,能提升算法技能。**
58 3
|
5月前
|
算法 搜索推荐 C#