基础算法训练（七）快速排序

​
​

活动地址：CSDN21天学习挑战赛

学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰。
热爱写作，愿意让自己成为更好的人…

基础算法训练（七）快速排序

写在前面的一些话：本人是本科在校软件工程在读准大三大学生，在跟上学校安排课程的同时，通过自学学习了Java后端开发的内容，学习了Spring，SpringMVC，SpringBoot等框架，在不断的学习中不断进步的同时，也感觉到一些迷茫，有时也会看不到前面的路该怎么走，本着一颗求知与记录的心情开始了写博客的生活，把自己的学习历程记录下来的同时，也希望认识到更多的人一起互勉学习

今天学习的是目前为止最需要逻辑思考的算法，快速排序，可能在很多人学习算法之前就听说过快速排序的大名，确实快速排序想要完整的敲出来是有一定的难度，但是，最重要的其实并不是怎么正确且完整的背诵代码，而是要理解快速排序的思路，了解快速排序的精髓，才是学习快速排序的最佳方法！今天是第七天的基础算法学习！一起加油！

第一章 了解算法

一、什么是算法？

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间，空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

二、算法的特征

一个算法应该具有以下五个重要的特征：
🧡有穷性（Finiteness）：
算法的有穷性是指算法必须能在执行有限个步骤之后终止；

确切性 （Definiteness）：
算法的每一步骤必须有确切的定义；

输入项（Input）：
一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；

输出项（Output）：
一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；

🤎可行性（Effectiveness）：
算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤，即每个计算步骤都可以在有限时间内完成（也称之为有效性）。

三、为什么要学习算法

算法对计算机科学的所有分支都非常重要。在绝大多数的计算机科学分支领域中，要想完成任何实质性的工作，理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。通过我们学习算法，可以更好的提高代码的执行效率，最关键的是可以从思维上的一个提升，通过学习算法可以更加多个角度的去看待以及处理问题，并找出一个问题的最优解

第二章 排序算法

排序算法是《数据结构与算法》中最基本的算法之一。

排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、快速排序、归并排序、快速排序、堆排序、基数排序等。而今天学习的是快速排序

一、快速排序概念

快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

该方法的基本思想是：

• 1．先从数列中取出一个数作为基准数。
• 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
• 3．再对左右区间重复第二步，直到各区间只有一个数。

二、快速排序执行流程

该方法的基本思想是：

• 1．先从数列中取出一个数作为基准数。
• 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
• 3．再对左右区间重复第二步，直到各区间只有一个数。

快速排序之所以比较快，是因为与冒泡排序相比，每次的交换时跳跃式的，每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。

三、执行代码

程序设计思路：

1. 设定任意排序的含若干个数的数组
2. 编写算法
3. 返回排序成功的数组

这是代码的执行图示：

程序代码：

package com.Yurrize.quick;

import java.util.Arrays;

public class quickSort {
    

    public static void main(String[] args) {
    
        // input data
        int[] arr = {
    3,1,17,28,29,27,31,39,49,4,50};
        // 调用快速排序，传入初始的左右端点
        quickSort(arr,0,arr.length - 1);

        System.out.println(Arrays.toString(arr));
    }

    private static int partition(int[] a,int p,int r){
    
        // 声明待排元素
        int x = a[r];
        // 初始化较小数区间端点
        int i = p - 1;
        // 循环结束后，区间已经划定完毕
        for(int j = p;j < r;j++){
    
            // 将较小的数向前扔
            if(a[j] < x){
    
                i++;
                // 交换两个元素
                int tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
            }
        }
        // 交换待排元素到指定位置
        int tmp = a[i + 1];
        a[i + 1] = a[r];
        a[r] = tmp;
        return i + 1;
    }

    private static void quickSort(int[] a,int p,int r){
    

        //给定递归出口
        if(p < r){
    
            // 划分后得到已排好元素的位置
            int q = partition(a,p,r);
            // 根据位置得到较小数列区间
            quickSort(a,p,q-1);
            // 根据位置得到较大数序列区间
            quickSort(a,q + 1,r);
        }
    }

}

输入数组arr{3,1,17,28,29,27,31,39,49,4,50};

编写算法quickSort(int[]arr)

处理返回结果:

程序执行成功，输出有序数组：

四、算法分析

时间复杂度

时间复杂度

快速排序在最坏情况下的时间复杂度和冒泡排序一样，是 O(n2)，实际上每次比较都需要交换，但是这种情况并不常见。我们可以思考一下如果每次比较都需要交换，那么数列的平均时间复杂度是 O(nlogn)，事实上在大多数时候，排序的速度要快于这个平均时间复杂度。这种算法实际上是一种分治法思想，也就是分而治之，把问题分为一个个的小部分来分别解决，再把结果组合起来。

空间复杂度

空间复杂度

快速排序只是使用数组原本的空间进行排序，所以所占用的空间应该是常量级的，但是由于每次划分之后是递归调用，所以递归调用在运行的过程中会消耗一定的空间，在一般情况下的空间复杂度为 O(logn)，在最差的情况下，若每次只完成了一个元素，那么空间复杂度为 O(n)。所以我们一般认为快速排序的空间复杂度为 O(logn)。

快速排序是一个不稳定的算法，在经过排序之后，可能会对相同值的元素的相对位置造成改变。

快速排序基本上被认为是相同数量级的所有排序算法中，平均性能最好的。

总结🧶

今天是坚持学习算法的第七天，快速排序更注重逻辑性，具有一定的难度，新手学习的时候虽然不能把代码一次性的敲出来，但是最重要的是理解快速排序的思路！