算法概念

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

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

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

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

相关概念

数据结构

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

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

算法的效率

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

通常会使用到两个概念：

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

时间复杂度

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

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

空间复杂度

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

交换排序

交换排序介绍

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

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

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

冒泡排序

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

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

• 算法说明
  总结来说，每一趟冒泡排序将会排好一个元素。排序时会（在无序中）的一端开始元素的扫描，先以最后一个元素为基准，与前一个元素进行比较，如果较小，则交换。如果遇到一个更小的，则不交换，继续向前进行两个相邻元素的比较。按照这样的过程执行后，无序区中最小的元素一定会被交换至最前，被划入有序区，也就排好了一个元素
  不断的在无序区中执行该步骤，如果在某一次比较的过程中没有发生元素的交换，则证明元素都已经有序，可以提取结束整个算法。或者直到无序区中的元素减少的一个时，整个算法结束，此时整个序列应有序。

伪代码

for i = 1 to n-1
    change = 0
    for j = n downto i + 1
        if A[j] < A[j - 1]
            exchange A[j] with A[j-1]
            change = 1
    if change == 0
        return

由于每趟排序会排好一个元素，所以至多n-1趟就可以完成排序，也就说明无序区中的元素都已排好，算法可以提取结束，使用change变量进行标记

算法实践

• 算法实现
  输入数据（input）：11，34，20，10，12，35，41，32，43，14

java 源代码

public class BubbleSort {

    public static void main(String[] args) {
        // input data
        int[] a = {11,34,20,10,12,35,41,32,43,14};
        // 调用冒泡排序
        sort(a);
        // 查看排序结果
        for (int data : a){
            System.out.print(data + "\t");
        }
    }

    private static void sort(int[] a){
        // 外层循环：控制排序的总趟数
        for(int i = 0;i < a.length - 1;i++){
            // 定义变量记录是否发生交换
            int change = 0;
            // 内层循环用于元素的两两比较和交换
            for (int j = a.length - 1;j > i;j--){
                // 如果后面的元素较小，则交换
                if (a[j] < a[j-1]){
                    // 两个元素进行交换
                    int tmp = a[j];
                    a[j] = a[j - 1];
                    a[j - 1] = tmp;
                    // 记录发生了交换
                    change = 1;
                }
            }
            // 如果一次比较中没有发生交换则提前结束
            if (change == 0){
                return;
            }
        }
    }
}

• 执行效果
  10 11 12 14 20 32 34 35 41 43