排序算法----快速排序----详解&&代码

简介: 排序算法----快速排序----详解&&代码

快速排序:


基本思想:在数列进行快速排序时,选择第一个数为基准值(begin),判断if(left>begin)就swap(left,right),然后right–(向前移一位),if(left<begin)就left++(left向前移一位),当left和right移到一起


就把基准值插入到数列中,循环结束后,left=right,原本数列a[begin+1]~a[end],左边比基准值小,右边比基准值大,

然后把基准值插入到合适序列中,判断基准值比最后left和right共同指的那个数哪个大

如果基准值比它大就放在它后边(交换就行)如果基准值比它小就放在它前边(基准值直接和left-1交换)

代码:

//快速排序
void QuickSort(int data[], int begin, int end)
{
    int temp;
    int left = begin + 1;
    int right = end;
    if (begin < end) //数列中存在数据进入排序
    {
        while (left < right)
        {
            //判断基准值与left的大小
            if (data[begin] < data[left])
            {
                //交换a[left]和a[right]的值,right--
                swap(&data[left], &data[right]);
                right--;
            }
            else
                left++;
        }
        //循环结束后,left=right,原本数列a[begin+1]~a[end],左边比基准值小,右边比基准值打,然后把基准值插入到合适序列中
        //判断基准值比最后left和right共同指的那个数哪个大
        //如果基准值比它大就放在它后边(交换就行)
        //如果基准值比它小就放在它前边(基准值直接和left-1交换)
        if (data[begin] > data[left])
        {
            swap(&data[begin], &data[left]);
        }
        else
        {
            left--;
            swap(&data[begin], &data[left]);
        }
        //此时原本数列a[begin]~a[end]就被分成了两个数列     a[begin]~a[left-1]和a[left+1]~a[end]
        QuickSort(data, begin, left);
        QuickSort(data, left + 1, end);
    }
}
相关文章
|
1天前
|
并行计算 算法 Python
Dantzig-Wolfe分解算法解释与Python代码示例
Dantzig-Wolfe分解算法解释与Python代码示例
|
7天前
|
算法 搜索推荐 编译器
算法高手养成记:Python快速排序的深度优化与实战案例分析
【7月更文挑战第11天】快速排序是编程基础,以O(n log n)时间复杂度和原址排序著称。其核心是“分而治之”,通过选择基准元素分割数组并递归排序两部分。优化包括:选择中位数作基准、尾递归优化、小数组用简单排序。以下是一个考虑优化的Python实现片段,展示了随机基准选择。通过实践和优化,能提升算法技能。**
13 3
|
9天前
|
存储 算法 大数据
Python算法高手的必修课:深入理解分治法、贪心算法、动态规划,让你的代码更智能!
【7月更文挑战第9天】在Python算法学习中,分治法(如归并排序)将大问题分解为小部分递归解决;贪心算法(如货币找零)在每步选择局部最优解尝试达到全局最优;动态规划(如斐波那契数列)通过存储子问题解避免重复计算,解决重叠子问题。掌握这三种方法能提升代码效率,解决复杂问题。
|
16天前
|
算法 PHP
【php经典算法】冒泡排序,冒泡排序原理,冒泡排序执行逻辑,执行过程,执行结果 代码
【php经典算法】冒泡排序,冒泡排序原理,冒泡排序执行逻辑,执行过程,执行结果 代码
12 1
|
27天前
|
搜索推荐 算法 Java
Java中的快速排序、归并排序和堆排序是常见的排序算法。
【6月更文挑战第21天】Java中的快速排序、归并排序和堆排序是常见的排序算法。快速排序采用分治,以基准元素划分数组并递归排序;归并排序同样分治,先分割再合并有序子数组;堆排序通过构建堆来排序,保持堆性质并交换堆顶元素。每种算法各有优劣:快排平均高效,最坏O(n²);归并稳定O(n log n)但需额外空间;堆排序O(n log n)且原地排序,但不稳定。
22 3
|
1月前
|
算法 搜索推荐 JavaScript
算法学习:快速排序
算法学习:快速排序
16 1
|
1月前
|
搜索推荐 算法
【排序】数据结构——排序算法概念及代码详解(插入、冒泡、快速、希尔)
【排序】数据结构——排序算法概念及代码详解(插入、冒泡、快速、希尔)
|
16天前
|
算法 搜索推荐 C#
|
24天前
|
人工智能 算法 Java
java中经典算法代码整理
java中经典算法代码整理
21 0