1.算法概述
1.1什么是算法
算法是特定问题的求解步骤的描述，是独立存在的一种解决问题的思想和方法。对于算法而言计算机编程语言并不重要，可以用任何计算机编程语言来编写算法。
程序=数据结构+算法
1.2数据结构和算法的区别和联系
数据结构只是静态的描述了数据元素之间的关系，高效的程序需要在数据结构的基础之上设计、选择合适的算法才能完成。数据结构是算法实现的载体，算法是为了解决实际问题提出的思想和方法。二者之间缺一不可，相辅相成。
1.3算法效率的度量
一般算法的效率是通过时间复杂度和空间复杂度来度量的。但是目前对于越来越便宜、越来越大的内存空间来说，我们更关注时间复杂度。但是，在某些特殊场景下，比如程序运行在单片机上时，就有可能要考虑算法的空间复杂度。同一个问题，我们可以用不同的算法来解决，我们应当根据具体实际需求来选取最合适的算法。例如，有的算法时间复杂度是O(n2)，但是空间复杂度为O(1)，另外一个算法时间复杂度为O(n)，空间复杂度为O(n)。如果我们更加关注的是时间上的效率，肯定选择第二种算法，，这也就是所谓的空间换时间。如果在某些特殊场景下，存储空间非常紧缺，就要选取第一种算法。
一般情况下，我们更加关注时间复杂度。
算法效率度量，一般有两种方式：
1.3.1事后统计法
定义：事后统计法是在程序编制完成后，通过实际运行程序并收集运行时间、占用内存等数据来评估算法性能的方法。
这种方法可行，但是不是一个好方法，该方法有两个缺陷：
第一个缺陷，要想对某种算法进行评测，必须先依据该算法编制相应的程序，并实际运行；
第二个缺陷，算法运行的时间等效率的统计它依赖于所允许的计算机硬件、软件等环境因素这些环境因素有时候会掩盖算法本身的优劣。
1.3.2事前分析法
定义：事前分析法是在算法设计阶段，通过分析算法的逻辑结构和操作步骤，估算算法的时间和空间复杂度来评估算法性能的方法。
1.3.3求解算法时间复杂度的具体步骤
找出算法中的基本语句；算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
计算基本语句的执行次数的数量级；只要保证基本语句执行次数函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数，这样的话，我们的注意力只集中在最重要的一点上：增长率。
1.3.4常见的时间复杂度
| 执行次数函数 | 阶 | 非正式术语 |
| 12 | O(1) | 常数阶 |
| 2n+8 | O(n) | 线性阶 |
| 3n^2^+5n+19 | O(n^2^) | 平方阶 |
| 4n^3^+2n^2^+6n+22 | O(n^3^) | 立方阶 |
| 7logn+8 | O(logn) | 对数阶 |
| 9nlogn+15 | O(nlogn) | nlogn阶 |
| 2^n^+5n^3^+7n^2^+66 | O(2^n^) | 指数阶 |
例子：
temp = i; i = j; j = temp;上面代码段的执行时间是一个与问题规模n无关的常数，算法的时间复杂度为常数阶。如果一个算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个比较大的常数而已。此类算法的时间复杂度都为常数阶，即O(1)
for (i = 0; i < n; i++)
cout << i << endl;上面代码段的时间复杂度为O(n)
sum = 0;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
sum++;上面代码段的时间复杂度为O(n^2^)
count = 1;
while (count <= n)
count = count * 2;上面代码段的时间复杂度为O(logn)
1.3.5算法的空间复杂度定义
算法的空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的度量，用大O(n)记号表示。
一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的空间、算法的输入、输出数据所占的存储空间、和算法在运行过程中临时占用的存储空间三部分。算法本身所占用的存储空间和算法的编写的长短成正比，要压缩算法本身所占用的空间，就必须编写出较短的程序。算法的输入输出数据所占的存储空间是由要解决的问题决定的，它不随着算法不同而改变。算法在运行过程中所需要的临时存储空间随着算法的不同而异，有的算法只需要较少的临时工作单元，而且不随着问题规模的大小而改变，我们称这种算法是就地执行的，有的算法需要的临时工作单元和要解决问题的规模n有关，它随着n的增大而增长，当n比较大的时候，就需要占用较多的存储空间。
2.排序算法
2.1概念
排序是计算机中非常重要的一个操作，其目的是将一组无序的数据元素通过某种算法调整为有序的数据元素。
在现实生活中，排序是基础而且重要的操作，例如，京东上按照条件(价格、销量、好评度等)进行排序。
排序过程中的关键操作：
比较：任意两个数据元素通过比较来确定先后次序；
交换：如果比较后顺序不对，需要交换。
排序的分类：
根据带排序的数据元素的多少和使用的内存类别，排序分为内部排序和外部排序。
内部排序：数据比较少，可以一次全部加载到内存中进行的排序称为内部排序。绝大部分排序都属于内部排序。
外部排序：数据量大到无法一次性全部加载到内存中，需要借助硬盘等辅助存储器进行排序，称为外部排序。
排序算法的稳定性
定义：如果在序列中有两个数据元素r[i]和r[j]其中r[i]==r[j]，在排序前，r[i]在r[j]的前面，排序之后,如果r[i]仍然在r[j]的前面，则称该排序算法是稳定的，否则，则称该算法是不稳定的。
如果排序的内容是一个复杂对象的多个数字属性，且其原本的初始顺序存在意义，那么我们需要在二次排序的基础上保持原有排序的意义，才需要使用稳定性的排序算法。例如要排序的内容是一组原本按照价格排序的对象，现在需要按照销量进行排序，如果使用稳定性的排序算法，那么销量相同的对象依旧保持着价格的排序结果。当然，如果不需要保持初始排序的意义，那么使用不使用稳定性的排序算法都无所谓。
2.2冒泡排序(Bubble Sort)
（假设，从小到大排序）原理：从第一个元素开始，比较相邻两个元素的大小，若大小顺序有误，则交换。然后进行下一个元素的比较。如此扫描一趟后，可以确保最大的元素放到最后的位置，接着，进行第二次扫描。。。。。直到完成所有的排序。
算法分析：
时间复杂度：在冒泡排序中，第一趟需要进行n-1次比较，第二趟需要进行n-2次比较。。。。。第n-1趟需要1次比较，因此，总的比较次数为：(n-1)+(n-2)+(n-3)+......+3+2+1=n(n-1)/2
时间复杂度为O(n^2^)
空间复杂度：由于在冒泡排序的整个过程中，只有交换的时候需要一个单位的临时辅助空间，所以冒泡排序的空间复杂度为O(1)
稳定性：冒泡排序就是把大的元素往后调，如果相等不交换，所以冒泡排序是一种稳定的排序算法。
#include <iostream>
using namespace std;
void printArry(int arr[], int len)
{
for (int i = 0; i < len; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
void bubbleSort(int arr[], int len)
{
int count = 0;//记录比较次数
for (int i = 0; i < len - 1; i++)
{
bool flag = false;
for (int j = 0; j <len - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = true;
}
count++;
}
if (!flag)
{
break;
}
}
//cout << "总共比较了" << count << "次" << endl;
}
int main()
{
//int a[] = { 6,3,1,5,7,9,2,8,4 };
int a[] = { 9,8,7,6,5,4,3,2,1 };
int length = sizeof(a) / sizeof(int);
cout << "这是冒泡排序" << endl;
printArry(a, length);
bubbleSort(a, length);
printArry(a, length);
return 0;
}2.3选择排序(Selection Sort)
原理：从待排序的数据元素中选一个最小值，和当前序列最左边的元素进行交换。
算法分析：
时间复杂度：在选择排序中，需要进行n-1趟选择，第一趟需要进行n-1次比较，第二趟需要进行n-2次比较。。。。。第n-1趟需要1次比较，因此，总的比较次数为：(n-1)+(n-2)+(n-3)+......+3+2+1=n(n-1)/2
时间复杂度为O(n^2^)
空间复杂度：只需要两个临时存储单元，所以空间复杂度为O(1)
稳定性：选择排序是给每个位置选择当前最小值，比如给第一个位置选择最小的，在剩余的元素里面给第二位置选择第二小的。。。。以此类推，直到第n-1个元素，第n个元素就不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择中，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后，稳定性就被破坏了。所以，选择排序是不稳定的排序算法。
#include <iostream>
using namespace std;
void printArry(int arr[], int len)
{
for (int i = 0; i < len; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
void selectionsort(int arr[], int len)
{
for (int i = 0; i < len - 1; i++)
{
int min = i;
for (int j = i+1; j <len ; j++)
{
if (arr[min]> arr[j])
{
min = j;
}
}
if (i != min)
{
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
}
int main()
{
int a[] = { 6,3,1,5,7,9,2,8,4 };
//int a[] = { 9,8,7,6,5,4,3,2,1 };
int length = sizeof(a) / sizeof(int);
cout << "这是选择排序：" << endl;
printArry(a, length);
selectionsort(a, length);
printArry(a, length);
return 0;
}2.4 插入排序（Insertion Sort）
原理：将数据中的元素逐一和排好序的数据进行比较，再将元素插入到合适的位置。
详细过程如下：插入排序又叫直接插入排序（straight Insertion Sort），其基本操作是将一个元素插入到已经拍好序的有序表中，从而得到一个新的、元素数增1的有序表。
假定现在有序表中已经有多个元素了，我们取数组中的第i个元素，往0~i-1的有序表中进行插入。插入的过程如下：跟有序表中的最大值arr[i-1]比较，发现比最大值小，将最大值arr[i-1]往后挪一位，继续和有序表中的第二大值arr[i-2]进行比较，如果发现比它还小，有序表中的第二大值arr[i-2]继续往后挪一位。。。。。
直到找到有序表中第j个元素比当前元素要小或者将有序表找完了，就扎到合适的位置，进行插入位置。
算法分析：
时间复杂度：比较次数为1+2+3.。。。。+(n-2)+(n-1)=n(n-1)/2，时间复杂度为O(n^2^)；;空间复杂度为O(1)；
稳定性：判断的条件式待插入元素小于已经排好序的元素，因此，不小于是不会移动的，是稳定的排序算法。
#include <iostream>
using namespace std;
void printArry(int arr[], int len)
{
for (int i = 0; i < len; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
void insertionSort(int arr[], int len)
{
for (int i = 1; i < len; i++)
{
int j = i - 1;
int temp = arr[i];
while (j >= 0 && arr[j] > temp)
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
int main()
{
int a[] = { 6,3,1,5,7,9,2,8,4 };
//int a[] = { 9,8,7,6,5,4,3,2,1 };
int length = sizeof(a) / sizeof(int);
cout << "这是插入排序：" << endl;
printArry(a, length);
insertionSort(a, length);
printArry(a, length);
return 0;
}2.5希尔排序（Shell Sort）
希尔排序算法又叫缩小增量排序算法，是一种更高效的插入排序算法。和普通的直接插入排序算法比较，希尔排序算法大大减少了移动元素的次数，从而提高了排序效率。
因为当数组很大时，使用直接插入排序有个弊端，就是如果小值放在末端的时候，直接插入排序需要从末端开始，逐个后移比小值大的这些元素，很低效，而希尔排序通过分组的方式，直接让末端的元素前端元素进行比较，可以吧这些小值很快的移动到前端。
希尔排序的实现思路：
将待排序列划分成多个子序列，使用普通的直接插入排序对每个子序列进行排序；
按照不同的分组标准，重复执行第一步；
使用普通的直接插入排序算法对整个序列进行排序。
具体方法：先选定一个小于n的整2数gap作为第一增量（n/2）,然后将所有距离为gap 的元素分再同一组，并对同一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述过程。。。。当增量减小到1时，就相当于整个序列被分到同一组，进行一次直接插入排序即可。
算法分析：
时间复杂度：希尔排序的时间复杂度取决于gap序列的设计，一般情况下，其时间复杂度不超过平方阶，平均时减复杂度为O(n1.5)
空间复杂度为：O(1);
稳定性：不稳定的排序算法，只能保证同一组稳定，不能保证其他组。
#include <iostream>
using namespace std;
void printArry(int arr[], int len)
{
for (int i = 0; i < len; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
void shellSort(int arr[], int len)
{
for (int gap = len / 2; gap > 0; gap /= 2)
{
for (int i = gap; i < len; i++)
{
int j = i - gap;
int temp = arr[i];
while (j >= 0 && arr[j] > temp)
{
arr[j + gap] = arr[j];
j-=gap;
}
arr[j + gap] = temp;
}
}
}
int main()
{
int a[] = { 6,3,1,5,7,9,2,8,4 };
//int a[] = { 9,8,7,6,5,4,3,2,1 };
int length = sizeof(a) / sizeof(int);
cout << "这是希尔排序：" << endl;
printArry(a, length);
shellSort(a, length);
printArry(a, length);
return 0;
}2.6快速排序(Quick Sort)
原理：通过一趟排序将待排序列分城独立的两部分，其中一部分的数据都比另外一部分要小，然后再按此方法对这两部分数据进行快速排序，整个排序过程是递归进行的，已达到整个序列有序。
具体方法如下：
受限设定一个分界值，通过改分界值分成左右两部分；将大于或者等于分界值的数据放在数组的右边，小于分界值的数据放在数组的左边，然后，左右两部分再进行处理，左半部分再取一个分界值，将该部分数据再分成左右两部分，右半部分数据也做相同处理。。。。重复上述过程，可以看出，这是一个递归定义。通过递归将左半部分的数据排序，再递归排好右半部分数据。当左右两个部分的数据排序好后，整个数组就排序完成了。
详细过程如下：
假设对 6 1 2 7 9 3 4 5 10 8这十个数进行快速排序，首先在这个序列中找一个数作为基准值（分界值），为了方便起见，就让第一个数6作为基准值，接下里，我们需要用某种方法将这个序列中比基准值小的数放在基准值左边，比基准值大的数放在基准值的右边，类似于这种结果：3 1 2 5 4 6 9 7 10 8
再初始状态下，元素6在第一位，目标是将6挪到中间的某个位置，假设这个位置为k，现在就需要寻找这个k。
分别从数组的两端开始探测，先从右边开始，往左找一个小于6 的数，再从左边往右边找一个大于6的数，然后交换它们。然后再从右到左，找一个小于6的数，从左到右找一个大于6的数。。。可以用两个变量i和j，分别指向序列的最左端和最右端，可以称i和j为哨兵。直到i和j碰头，这时，i或者j的位置就是上述所要找的那个k。
算法分析:
时间复杂度为：O(nlogn)
空间复杂度为：O(logn)
稳定性：不稳定的排序算法
#include <iostream>
using namespace std;
void printArry(int arr[], int len)
{
for (int i = 0; i < len; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
void quickSort(int arr[], int left, int right)
{
int i= left, j = right;
int key = arr[left];
if(i > j)
{
return;
}
while (i < j)
{
while (i < j && arr[j] >= key)
{
j--;
/*if (i == j)
{
break;
}*/
}
/*if (i < j)
{
arr[i] = arr[j];
i++;
}*/
while (i < j && arr[i] <= key)
{
i++;
/*if (i == j)
{
break;
}*/
}
/*if (i < j)
{
arr[j] = arr[i];
j--;
}*/
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
arr[left] = arr[i];
arr[i] = key;
if (left < i - 1)
{
quickSort(arr, left, i - 1);
}
if (right > i + 1)
{
quickSort(arr, i + 1, right);
}
}
int main()
{
int a[] = { 6,3,1,5,7,9,2,8,4 };
//int a[] = { 9,8,7,6,5,4,3,2,1 };
int length = sizeof(a) / sizeof(int);
cout << "这是快速排序：" << endl;
printArry(a, length);
quickSort(a, 0, length -1);
printArry(a, length);
return 0;
}2.7 归并排序（Merge Sort）
归并排序算法有两个基本操作，一个是分，也就是把原始数组划分成两个子数组的过程。另一个就是治，他将两个有序数组合并成一个更大的有序数组。
算法分析：
时间复杂度：O(nlogn)
空间复杂度：因为归并排序过程中需要使用一个和原始数组相同大小的辅助数组，所以，归并排序的空间复杂度为O(n)
稳定性：稳定的排序算法
#include <iostream>
using namespace std;
void printArry(int arr[], int len)
{
for (int i = 0; i < len; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
void merge(int arr[], int left, int mid, int right)
{
int i = left, j = mid + 1, k = 0;
// 1. 建立一个临时数组，大小为right - left + 1
int *temp = new int[right - left + 1];
// 2. 开始循环，把左右两个数组元素小值依次插入到临时数组中
while (i < mid + 1 && j < right + 1)
{
if (arr[i] < arr[j])
{
temp[k++] = arr[i++];
}
else
{
temp[k++] = arr[j++];
}
}
while (i < mid + 1)// j序列结束，如果左半部分还有剩余元素，则依次插入到临时数组中
{
temp[k++] = arr[i++];
}
while (j < right + 1)//i序列结束，如果右半部分还有剩余元素，则依次插入到临时数组中
{
temp[k++] = arr[j++];
}
// 3. 把临时数组中的数据拷贝到原数组中
for (int i = 0; i < k; i++)
{
arr[left + i] = temp[i];
}
// 4. 释放临时数组
delete []temp;
}
void mergeSort(int arr[], int left, int right)
{
int i = left , j = right;
if (i < j)
{
int mid = (i + j) / 2;
mergeSort(arr, i, mid);//递归对左半部分进行排序
mergeSort(arr, mid + 1, j);//递归对右半部分进行排序
merge(arr, i, mid, j);//合并两个有序部分
}
}
int main()
{
int a[] = { 6,3,1,5,7,9,2,8,4 };
//int a[] = { 9,8,7,6,5,4,3,2,1 };
int length = sizeof(a) / sizeof(int);
cout << "这是归并排序：" << endl;
printArry(a, length);
mergeSort(a, 0, length - 1);
printArry(a, length);
return 0;
}2.8 堆排序（Heap Sort）
最大堆积数，又叫大顶堆，所有节点的值都大于或者等于其左右子节点的值，树根就是最大堆积树中的最大值。
最小堆积数，又叫小顶堆，所有节点的值都小于或者等于其左右节点的值，树根就是最小堆积树中的最小值。
堆排序的思路：（这里以升序排序为例，如果是降序排序，则需要构造小顶堆）将待排序列构造成一个大顶堆，此时，整个序列中的最大值就是大顶堆的根节点。将其与末尾元素进行交换，此时末尾元素即为最大值。然后将剩下的n-1个元素重新调整为大顶堆，这样就会得到n个元素中的次大值，再次与末尾元素进行交换。。。。如此，反复执行，最后得到一个有序序列。
堆排序的步骤：
1.建立一个大顶堆：将n个元素组成的无序序列构建成一个大顶堆；
2.将堆顶元素元素与末尾元素进行交换，将最大元素“沉到”数组末端；
3.调整大顶堆：将n-1个元素重新调整为大顶堆；
4.反复执行步骤2和步骤3，直到整个序列有序。
为什么第一个非叶子节点的索引为n/2-1呢？
因为索引为i的节点的父节点索引为(i-1)/2,而最后一个叶子节点索引为n-1,其父结点编号为(n-1-1)/2=n/2-1,恰恰最后一个叶子节点的父节点即为第一个非叶子节点。
通常堆是通过一维数组来实现的。在数组起始位置为0的情形中：
父节点i的左子节点在位置（2i+1）
父节点i的右子节点在位置（2i+2）
#include <iostream>
using namespace std;
void printArry(int arr[], int len)
{
for (int i = 0; i < len; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
void heapify(int arr[], int index, int end)
{
int maxindex = index;
int left = index * 2 + 1;
int right = index * 2 + 2;
if (left < end && arr[left] > arr[maxindex])
{
maxindex = left;
}
if (right < end && arr[right] > arr[maxindex])
{
maxindex = right;
}
if (maxindex != index)
{
int temp = arr[index];
arr[index] = arr[maxindex];
arr[maxindex] = temp;
heapify(arr, maxindex, end);
}
}
void heapSort(int arr[], int len)
{
//从第一个非叶子节点(len/2-1)开始，调整堆，使其称为一个大顶堆
for (int i = len / 2 - 1; i >= 0; i--)
{
heapify(arr, i, len);
}
//将堆顶元素与末尾元素进行交换，重新调整堆，形成一个新的大顶堆
for (int i = len - 1; i > 0; i--)
{
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
heapify(arr, 0, i);
}
}
int main()
{
int a[] = { 6,3,1,5,7,9,2,8,4 };
//int a[] = { 9,8,7,6,5,4,3,2,1 };
int length = sizeof(a) / sizeof(int);
cout << "这是堆排序：" << endl;
printArry(a, length);
heapSort(a, length);
printArry(a, length);
return 0;
}
