基本算法
图片名词解释：
n: 数据规模
k:“桶”的个数
In-place: 占用常数内存，不占用额外内存
Out-place: 占用额外内存
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
内排序：所有排序操作都在内存中完成；
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
时间复杂度: 一个算法执行所耗费的时间。
空间复杂度: 运行完一个程序所需内存的大小。
一、冒泡排序
1、原理：
（1）比较相邻的元素。如果第一个比第二个大（小），就交换他们两个。
（2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大（小）的数。
（3）针对所有的元素重复以上的步骤，除了最后已经选出的元素（有序）。
（4）持续每次对越来越少的元素（无序元素）重复上面的步骤，直到没有任何一对数字需要比较，则序列最终有序。
2、示例
3、c++代码实现
void bubble_sort(int arr[], int len) {
int i, j;
for (i = 0; i < len - 1; i++)
for (j = 0; j < len - 1 - i; j++)
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
4、传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。
voidbubble_sort(intarr[],intlen)
{
int low = 0;
int high = len - 1;
inti, j;
while (low < high)
{
for (i = low; i< high; ++i)
{
if (arr[i] >arr[i + 1])
{
swap(arr[i], arr[i + 1]);
}
}
--high;
for (i = high; i> low; --i)
{
if (arr[i] <arr[i - 1])
{
swap(arr[i], arr[i - 1]);
}
}
++low;
}
}
二、选择排序
1、原理：
在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。
2、示例
3、c++代码实现
voidSelectSort(int a[], intlen)
{
for(inti = 0; i<len - 1;i++)
{
intminIndex= i;
for(int j = i + 1; j <len;j++)
{
if(a[j]<a[minIndex])
{
minIndex= j;
}
}
swap(a[i],a[minIndex]);
}
}
三、插入排序
1、原理：
是通过构建有序序列，对未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。
2、示例
3、c++代码实现
voidinsert_sort(int a[], intlen)
{
for(inti = 1; i<len; i++)//从数组中第二个元素开始
{
intkey = a[i];//记录当前的元素
intj = i - 1;
while(j>=0 && a[j]>key)//将当前的元素与之前的已经排序好的序列元素进行挨个比较
{
a[j+ 1] = a[j];//已经排序好的序列整体向后移动
j--;
}
a[j+ 1] = key;//插入当前的元素
}
}
四、希尔排序
1、原理：
2、示例
五、快速排序
1、原理：
（1）选择一个基准元素,通常选择第一个元素或者最后一个元素,
（2）通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。
（3）此时基准元素在其排好序后的正确位置
（4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。
2、示例