选择排序
从序列中依次选出最小值（或者最大值）放在一侧。这样的排序叫选择排序。
这里我们对选择排序进行优化，一次就选出当前序列的最大值和最小值。分别放在最右端和最左端。然后left++，
right--。使得序列范围缩小，再进行选择最大和最小值。
void SelectSort(int*a, int n)// 3选择排序 { int left = 0; int right = n; int min = left; int max = right - 1; while (left<right) { int min = left; int max = right - 1; for (int i = left; i < right; ++i) { if (a[i] < a[min]) { min = i; } if (a[i]>a[max]) { max = i; } } swap(a[left], a[min]); if (max == left) { max = min; } swap(a[right-1], a[max]); ++left; --right; } }
选择排序任何情况下时间复杂度都是O(N^2),但它是稳定的一种排序算法。
堆排序
如果要从小到大的序列。则我们需要建立大堆-->取堆的TOP和堆最后一个数据交换（最大的数放在了最后面）--->因为交换之后，不再是大堆，进行向下调整算法，继续是大堆---->循环取TOP和最后数交换
void AdjustDown(int* a, int i,int n)// 4 -向下调整算法 { int parent = i; int child = i * 2 + 1; while (child < n) { if (child + 1 < n&&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 Heap(int*a, int n)//4 堆排序 { int i = (n - 2)/2; for (i; i >= 0; --i) { AdjustDown(a, i, n); } int end=n-1; while (end) { swap(a[0], a[end]); AdjustDown(a, 0, end); --end; } } 堆排的时间复杂度是N*logN,是不稳定的排序。
