选择排序
选择排序
过程图如下：
代码呈现
//时间复杂度：O(N^2) //最好情况下：O(N^2) void SelectSort(int* a, int n) { int begin = 0, end = n - 1; while (begin < end) { int mini = begin, maxi = begin; for (int i = begin + 1; i <= end; i++) { if (a[i] < a[mini]) { mini = i; } if (a[i] > a[maxi]) { maxi = i; } } Swap(&a[begin], &a[mini]); //当max在begin的位置时 if (maxi == begin) { maxi = mini; } Swap(&a[end], &a[maxi]); begin++; end--; } }
分析：开始时，begin指向首元素，end是末尾元素下标。这里的选择排序与上图过程略有差异，这里的选择排序每次选出最大和最小值，分别与头和尾交换。然后begin++和end--来缩小选择的范围。需注意，在同时选最大和最小时，要判断max是否在begin的位置上，如果是，就要把maxi改为mini的值。
堆排序
代码呈现
void AdjustDown(int* a, int size, int parent) { int child = parent * 2 + 1; 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 = parent * 2 + 1; } else { break; } } } //升序 void HeapSort(int* a, int n) { //建大堆 //O(N) for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(a, n, i); } //O(N*logN) int end = n - 1; while (end > 0) { Swap(&a[0], &a[end]); AdjustDown(a, end, 0); end--; } }
堆排序在前面的文章中已经讲解，这里不再介绍。
交换排序
冒泡排序
//时间复杂度：O(N^2) //最好情况：O(N); void BubbleSort(int* a, int n) { for (int j = 0; j < n; j++) { bool exchange = false; for (int i = 1; i < n-j; i++) { if (a[i - 1] > a[i]) { Swap(&a[i - 1], &a[i]); exchange = true; } } if (exchange == false) break; } }
分析：这里简单说下时间复杂度最好情况：O(N)。在第一次外层for循环时，如果内层循环结束后，exchange的值还是false，就说明已经是排序好了的，就可以break掉循环，这时就遍历了一次，时间复杂度就是O(N)。
