插入排序：直接插入排序、希尔排序

选择排序：直接选择排序、堆排序

上述排序都是需要掌握的，但原理不会讲解，网上有很多详尽地解释，本文章主要分享一下代码实现上应当注意的事项

1.直接插入排序：

代码实现

void InsertSort(int* arr, int size)
{for (int j = 0; j < size - 1; j++){int end = j;int tmp = arr[end + 1];for (int i = end; i >= 0; i--){if (arr[i] > tmp){arr[i + 1] = arr[i];end--;}elsebreak;}arr[end + 1] = tmp;}
}

a.部分细节注意点：

b.循环逻辑不清：

2.希尔排序：

代码实现

void ShellSort(int* arr, int size)
{int gap = size;while (gap != 1){gap /= 2;for (int j = 0; j < size - gap; j++){int end = j;int tmp = arr[end + gap];for (int i = end; i >= 0; i -= gap){if (arr[i] > tmp){arr[i + gap] = arr[i];end -= gap;}elsebreak;}arr[end + gap] = tmp;}}
}

希尔排序其实是直接插入排序的一种变形。引入gap保证数组更快地变得有序。

a.循环逻辑混乱：

b.和直接插入排序的区别点：

c.时间复杂度简要分析：

3.直接选择排序：

代码实现

void SelectSort(int* arr, int size)
{int maxi = 0, mini = 0;int start = 0, end = size - 1;while (start < end){mini = maxi = start;for (int i = start; i <= end; i++){if (arr[i] < arr[mini])mini = i;if (arr[i] > arr[maxi])maxi = i;}swap(&arr[mini], &arr[start]);if (maxi != start){swap(&arr[maxi], &arr[end]);end--;}start++;}
}

a.细节

4.堆排序

代码实现：

void AdjustDown(int* arr, int size, int parent)
{int child = parent * 2 + 1;if (child + 1 < size && arr[child + 1] > arr[child])child++;while (child < size){if (arr[child] > arr[parent]){swap(&arr[child], &arr[parent]);parent = child, child = parent * 2 + 1;if (child + 1 < size && arr[child + 1] > arr[child])child++;}elsebreak;}
}void HeapSort(int* arr, int size)
{for (int i = (size - 2) / 2; i >= 0; i--){AdjustDown(arr, size, i);//建大堆}while (size > 1){swap(&arr[0], &arr[size - 1]), size--;AdjustDown(arr, size, 0);}}

a.每次选出最大值的代码实现：

b.循环逻辑：