1.直接插入排序
原理：从arr[0]开始，每次和后一个数据比大小，然后根据需要的是升序还是降序进行操作。
最差的情况下时间复杂度：O（n²）
最好的情况下时间复杂度：O（1）
所以平均时间复杂度：O（n²）
void InsertSort(int* arr, int n)
{
for (int i = 0; i < n-1; i++)
{
int end = i;
int tmp = arr[end + 1];
while (end >= 0)
{
if (arr[end] > tmp)
{
arr[end + 1] = arr[end];
end--;
}
else
{
break;
}
}
arr[end + 1] = tmp;
}
}2.冒泡排序
时间复杂度：O（n²）
void BubbleSort(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
int exchange = 0;
for (int j = 0;j < n-i-1; j++)
{
if (arr[j] > arr[j + 1])
{
exchange = 1;
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
if (exchange = 0)
{
break;
}
}
}
}3.堆排序
要用到向下调整算法建立大堆（最后产生一个降序效果）。当然如果想升序的话，就向上调整算法建立小堆。
时间复杂度：O（n*logn）
void Swap(int* x, int* y)
{
int temp = *x;
*x = *y;
*y = temp;
}
void ADJustDown(int* arr, int parent, int n)
{
int child = parent * 2 + 1;//左孩子
while (child < n)
{
if (child + 1 < n && arr[child] > arr[child + 1])
{
child++;
}
if (arr[child] < arr[parent])
{
Swap(&arr[child], &arr[parent]);
parent = child;
child = parent * 2 - 1;
}
else
{
break;
}
}
}
void HeapSort(int* arr, int n)
{
//向下调整算法建堆（大堆）
for (int i = (n - 2) / 2; i >= 0; i--)
{
ADJustDown(arr, i, n);
}
//升序（用大堆+向下调整算法）
int end = n - 1;
while (end > 0)
{
Swap(&arr[0], &arr[end]);
ADJustDown(arr, 0, end);
end--;
}
}4.希尔排序
希尔排序法又称缩小增量法。希尔排序法的基本思想：先选定一个整数（通常是gap=n/3 +1），把待排序文件所有记录分成各组，所有的距离相等的记录分在同一组内，并对每一组内的记录进行排序，然后gap=/3 +1得到下一个整数，再将数组分成各组，进行插入排序，当gap=1时，就相当于直接插入排序。
它是在直接插入排序算法的基础上进行改进而来，综合来说它的效率要高于直接插入排序算法。
时间复杂度：O（
）
void ShellSort(int* arr, int n)
{
int gap = n;
while (gap>=1)
{
gap = (gap / 3)+1;
for (int i = 0; i < n - gap; i++)
{
int end = i;
int tmp = arr[end + gap];
while (end >= 0)
{
if (arr[end] > tmp)
{
arr[end + gap] = arr[end];
end -= gap;
}
else
{
break;
}
arr[end + gap] = tmp;
}
}
}
}