​
​

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

算法概念

任何被明确定义的计算过程可以称作算法，它将某个值活一组值作为输入，并产生莫格值或一组值作为输出。所以算法可以被称作将输入转为输出的一系列的计算步骤。

这样的概况是比较抽象和标准的，其实说白了就是步骤明确的解决问题的方法。由于是在计算机中执行，所以通常先用伪代码表示，清晰的表达出思路和步骤。这样真正执行的时候，就可以使用不同的语言来实现出相同的兄啊过给。

概况的说，算法就是解决问题的工具。在描述一个算法时，我们关注的是输入与输出。也就是说只要把原始数据和结果描述清楚了，那么算法所作的事情也就清楚了。

在设计一个算法时也是需要先明确我们有什么和我们要什么。

相关概念

数据结构

算法经常会和数据结构一起出现，这是因为对于同一个问题，使用不同的数据结构来存储数据，对应的算法可能千差万别。
所以在整个学习过程中，也会涉及到各种数据结构的使用
常见的数据结构包括：

• 数组
• 堆
• 栈
• 队列
• 链表
• 树等等

算法的效率

在一个算法设计完成后，还需要对算法的执行情况作一个评估。一个好的算法，可以大幅度的节省资源消耗和时间。在进行评估时不需要太具体，毕竟数据量是不确定的，通常是以数据量为基准确定一个量级。

通常会使用到两个概念：

• 时间复杂度
• 空间复杂度

时间复杂度

通常把算法中的基本操作重复执行的频度称为算法的时间复杂度。算法中的基本操作一般是指算法中最深层循环内的语句（赋值、判断、四则运算等基础操作）。我们可以把时间频度记为T（n），它与算法中语句的执行次数成正比。其中的n被称为问题的规模，大多数情况下为输入的数据量。

对于每一段代码，都可以转为常数或者与n相关的函数表达式，记作f（n）。如果我们把每一段代码的花费的时间加起来就能够得到一个刻画时间复杂度的表达式，在合并后保留量级最大的部分即可确定时间复杂度。

空间复杂度

程序从开始执行到结束所需要的内存量。也就是整个代码中最大需要占用多少的空间。为了评估算法本身，输入数据所占用的空间不会考虑，通常更关注运算时需要额外定义多少临时变量或多少存储结构。

交换排序

交换排序的核心思想是，每次将元素两两比较，如果不满足正确的相对排序（如：较小的应该在前）则进行交换。不断的根据某个规律进行比较和交换，知道全部满足为止，此时也就得到了一个有序的序列。

• 冒泡排序
  也称气泡排序，是经典的交换排序的方法。整个过程就是在无序区中对相邻元素进行两两比较，将不满足相对顺序的一对元素进行交换，再进行下一对元素的比较。每一趟冒泡后，就会送要给最小的元素达到最上端。在无序区中重复这个过程，直到所有元素有序。

• 快速排序
  快速排序是冒泡排序的改进算法，主要思想是在待排序列中取一个元素（通常为第一个）作为参照，将序列分为两个子序列，比参照值小的元素和比参照值大的元素各自组成一个子序列。每趟排序会使参照元素归位，并得到两个子序列。在子序列中继续执行该步骤，直到子序列的长度为0或1.

快速排序

• 输入
  n个数的序列，通常直接存放在数组中，可能是任何顺序。

• 输出
  输入序列的一个新排列，满足从小到大的顺序（默认讨论升序，简单的修改就可以实现降序排列）

• 算法说明
  快速排序是一种划分交换排序方法，采用了分治策略。首先将原问题划分成若干个规模更小、与原问题相似的子问题，然后用递归方法解决这些子问题，最后再将他们组合成原问题的解。
  第一趟排好序列中的一个数，放在它应该在的位置上，同时得到两个子序列，左侧都是比它小的数，右侧都是比它大的数,接下来在每个子序列中不断重复归位一个元素、得到子序列的过程，直到子序列的长度为1或0，此时整体的序列已经有序

• 算法流程
  以下为第一趟排序的过程，选定一个待排元素x后，不断缩小无限制区域，使得得到的两个子序列（两个区域）满足其中一个都比x小，另一个都比x大，最后将待排元素插入到两个区间中间即完成排序.

伪代码

在快速排序中使用到了递归的操作，在编写伪代码时可以勇士FUNCTION来声明定义一个函数名称，以进行调用：

FUNCTION PARTITION(A,p,r)
x =  A[r]
i = p - 1
for j = p to r - 1
    if a[j] < x
        i = i + 1
        exchange A[i] with A[j]
exchange A[i + 1] with A[r]
return i + 1

PARTITION函数的作用时进行第一趟排序，排好一个元素，并得到两个子序列，返回值就是接下来划分子序列的参照。

FUNCTION QUICKSORT(A,p,r)
if p < r
    q = PARTITION(A,p,r)
    QUICKSORT(A,p,q-1)
    QUICKSORT(A,q+1,r)

QUICKSORT函数进行了递归的操作，将原问题分解为一系列的子问题，每次都在序列上进行划分、调用的操作，每次不断的改变区间的长度，直到不需要再划分为止。

算法实践

• 输入数据： 2，8，7，1，3，5，6，4

java源代码

算法中用到了递归调用

public class QuickSort {

    public static void main(String[] args) {
        // input data
        int[] a = {2,8,7,1,3,5,6,4};
        // 调用快速排序，传入初始的左右端点
        quickSort(a,0,a.length - 1);
        // 查看排序结果
        for (int data : a){
            System.out.print(data + "\t");
        }
    }

    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){
        // 重要：递归的出口（终止条件）为区间长度小于1
        if(p < r){
            // 划分后得到已排好元素的位置
            int q = partition(a,p,r);
            // 根据位置得到较小数列区间
            quickSort(a,p,q-1);
            // 根据位置得到较大数序列区间
            quickSort(a,q + 1,r);
        }
    }

}

• 执行效果
  1 2 3 4 5 6 7 8