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;}}}
}