一、排序算法的分类
下图是我掌握的一些排序算法，我将他们做了分类，当然，排序算法远不止这些。
本篇博客主要记录插入，选择，以及交换排序的冒泡排序，因为快排和归并算法相对复杂，所以，下一篇博客再细细讲述。
二、各种算法的基本思想，分析及其代码实现
1.直接插入排序
a>算法思想@H_502_15@：假设第一个数是有序的，那么把后面的数拿出来插入到这个有序数的合适位置，假设是升序（比第一个数小则向后移动第一个数，将数插入到第一个数的前面），插入后有序区间扩大为两个，依次向后，不断拿出新的数插入到有序区间，再扩大这个有序区间直至区间大小等于排序数组的大小。
b>时间复杂度@H_502_15@：时间上，最好情况当序列已经是有序排列了，在这种情况下，需要进行的比较操作需(n-1)次即可，复杂度O(n)。最坏情况,序列与目标序列相反，那么此时需要进行的比较共有n(n-1)/2次，时间复杂度忽略系数，结果为O(n^2)。平均来说插入排序算法复杂度为O(n²)。
c>空间复杂度@H_502_15@：由于插入排序没有进行任何开辟空间或者递归的操作，顾其空间复杂度为O(1).
d>适用场景@H_502_15@：由于插入排序的时间复杂度太大，所以不适合大量数据的排序，如果数据量少，倒是没啥影响。
#pragma once
#include<iostream>
using namespace std;
void InSertSort(int* a,size_t n)
{
int index = 1;
size_t pos = index - 1; //有序区间的最后一个位置
while (pos < n - 1)
{
for (int i = pos; i >= 0; i--)
{
if (a[i]>a[index])
{
swap(a[i],a[index]);
index--;
}
}
pos++;
index = pos + 1;
}
}
void TestInsertSort()
{
int a[] = { 9,5,4,2,3,6,8,7,1,0 };
InSertSort(a,sizeof(a) / sizeof(a[0]));
PrintArr(a,sizeof(a) / sizeof(a[0]));
}
2.希尔排序
a>算法思想@H_502_15@：希尔排序可以认为是对直接插入排序的优化，我们知道，直接插入排序在基本有序时是非常快的，所以希尔排序就是在直接插入排序之前进行多趟预排序(直接插入排序每次只能将数据移动一个位置，希尔的优化就体现在一次可跳跃移动)，使得排序数组接近有序，最后进行一趟直接插入排序。预排序的思想如下：
b>时间复杂度分析@H_502_15@：希尔排序的时间复杂度介于O(n)至O(n^2)之间，相关资料显示其具体复杂度为O(n^1.3)次方，这里我没有深究。
c>空间复杂度@H_502_15@：与直接插入排序一样，O(1)。
#pragma once
#include<iostream>
using namespace std;
void ShellSort(int*a,size_t size)
{
size_t gap = size; //增量
while (gap>1)
{
gap = gap / 3 + 1; //保证最后一次是直接插入排序
int pos = 0;
for (int index = pos + gap; index < size; index++)
{
int tmp = a[index];
pos = index - gap;
while (pos >= 0 && a[pos]>tmp)
{
a[pos + gap] = a[pos];
pos -= gap;
}
a[pos + gap] = tmp;
}
}
}
void TestShellSort()
{
int a[] = { 9,0 };
ShellSort(a,sizeof(a) / sizeof(a[0]));
}注意：希尔排序增量的设置不能为一个定值，要根据排序数组的大小进行调整，同时保证最后一次为1，进行直接插入排序。
3.选择排序
a>算法思想@H_502_15@：选择排序可以一次选一个最大的数，放在数组的最后一位（假设升序），也可以一次选择两个（一个最大，一个最小）分别放在最后和最前，算法思想很简单。
b>时间复杂度分析@H_502_15@：选择排序在最好和最坏的情况下都是O(n^2)，因为，即使有序了，选择排序依然每次要进行固定的选择和比较。
c>空间复杂度分析：@H_502_15@O(1)
#pragma once
#include<iostream>
using namespace std;
void SelectSort(int *a,size_t n)
{
size_t max,min;
size_t left = 0;
size_t right = n - 1;
while (left < right)
{
min = max = left;
for (size_t j = left; j <= right; j++)
{
if (a[j] <= a[min])
min = j;
if (a[j]>=a[max])
max = j;
}
swap(a[left],a[min]);
if (left == max)
{
max = min;
}
swap(a[right],a[max]);
left++;
right--;
}
}
void PrintArr(int* a,size_t n)
{
for (size_t i = 0; i < n; i++)
{
cout << a[i] << " ";
}
cout << endl;
}
void TestSelectSort()
{
int a[] = { 9,0 };
SelectSort(a,sizeof(a) / sizeof(a[0]));
}
4.堆排序
a>算法思想：@H_502_15@若升序，建大堆，每次选择堆顶元素即最大的数，和最后一位交换，再缩小堆的范围（避免刚排好的最后一个位置被调回去），对剩下的进行向下调整（此时只有根节点不对，左右子树都满足大堆）。反复进行直到堆的范围为0.则数据就有序了。
b>时间复杂度@H_502_15@：建堆的时间复杂度近似为O(n*log n)，每次选一个数后进行调整的复杂度也近似为O(n*log n)，时间复杂度忽略系数，结果就近似为O(n*log n).
c>空间复杂度@H_502_15@：O(1)
#pragma once
#include<iostream>
using namespace std;
void AdjustDown(int* a,int root,int size)
{
int parent = root;
int child = 2 * parent + 1; //数组下标是从0开始的，故此处的child是左孩子的下标
while (child < size)
{
if ((child + 1)<size && a[child + 1]>a[child])
++child;
if (a[child]>a[parent])
swap(a[child],a[parent]);
parent = child;
child = 2 * parent + 1;
}
}
void HeapSort(int*a,int size)
{
for (int i = (size-2)/2; i >=0; i--) //建堆
{
AdjustDown(a,i,size);
}
for (int j = 0; j < size; j++)
{
swap(a[0],a[size - 1 - j]);
AdjustDown(a,size - j - 1);
}
}
void TestHeapSort()
{
int a[] = { 9,5 };
HeapSort(a,sizeof(a) / sizeof(a[0]));
}
注意@H_502_15@：堆排序虽然效率很高，但是只适用于随机序列，像链表这些就不行了。
5.冒泡排序
a>算法思想@H_502_15@：从下表为0的数开始，和后面的数依次比较，大的向后移，一趟排序之后，最大的就移动到了最后，再从下标为0的开始将次大的冒到倒数第二位。
b>时间复杂度@H_502_15@：第一趟排序需要经过（n-1）次比较，第二次（n-2），。。。等差数列，最后忽略系数还是O(n^2)。
c>空间复杂度：@H_502_15@O(1)
#pragma once
#include<iostream>
using namespace std;
void BubbleSort(int* a,size_t size)
{
bool flag = false;
for (int i = size; i > 0; i--)
{
flag = false;
for (size_t j = 1; j < i; j++)
{
if (a[j - 1]>a[j])
{
swap(a[j],a[j - 1]);
flag = true;
}
}
if (flag = false)
break;
}
}
void TestBubbleSort()
{
int a[] = { 9,0 };
BubbleSort(a,sizeof(a) / sizeof(a[0]));
}
冒泡排序的优化：若某趟排序没有经过一次交换数据，说明数组已经有序，则跳出循环。
