排序算法多种多样，在不同的情况下选择正确合适的算法可以使排序的运行达到最优。这里整理常用的排序算法，便于以后查阅。
冒泡、选择、插入排序
三种相似的排序方式，易理解。拥有相同的特性：
稳定，数组中相同的数在排序后可以不改变先后顺序。
时间复杂度O(n^2)，无法处理较大数组。其中插入排序在数组整体较有序时发挥更佳，最优情况为O(n)。
空间复杂度O(1)，在原有数组上进行操作。
void bubbleSort(vector<int>& nums, int n) {
for(int i = n - 1; i >= 1; i--)
for(int j = 0; j < i; j++)
if(nums[j] > nums[j + 1])
swap(nums[j], nums[j + 1]);
}
void selectionSort(vector<int>& nums, int n) {
for(int i = n - 1; i >= 1; i--) {
int maxi = 0;
for(int j = 1; j <= i; j++)
if(nums[j] >= nums[maxi])
maxi = j;
swap(nums[i], nums[maxi]);
}
}
void insertionSort(vector<int>& nums, int n) {
for(int i = 1; i < n; i++) {
int j = i;
while(j > 0 && nums[j] < nums[j - 1]) {
swap(nums[j], nums[j - 1]);
j--;
}
}
}
希尔排序
将数组按照同一间隔拆分为小的数组，对小数组进行插入排序。随后逐渐缩小间隔，再次对各小数组进行排序。不稳定。时间复杂度取决与间隔的选择与数组内数值的情况，一般高于n^2。
void shellSort(vector<int>& nums, int n) {
int g = n >> 1;
while(g > 0) {
for (int i = 0; i < g; i++) //i作为每个小数组的开头元素
for (int j = i + g; j < n; j += g) { //进行插入排序
int k = j;
while (k > i && nums[k] < nums[k - g]) {
swap(nums[k], nums[k - g]);
k -= g;
}
}
g >>= 1;
}
}
堆排序
首先将原数组构建成最大堆，再将最大堆重构成有序数组。因使用原数组，空间复杂度为O(1)，在构建堆时每个元素都将进行logn的比较，因此时间复杂度为O(n*logn)。堆排序是不稳定排序。
void heapSort(vector<int>& nums) {
heapify(nums);
for(int i = nums.size() - 1; i >= 1; i--) {
//将nums[0] (最大值) 与 nums[i] 交换
swap(nums[0], nums[i]);
//从根节点0到末节点i-1重新构造最大堆
rebuildHeap(nums, 0, i - 1);
}
}
void heapify(vector<int>& nums) {
//若子元素大于父元素，则与父元素交换并继续向上对比
//遍历所有元素以形成最大堆
for(int i = 0; i < nums.size(); i++) {
int par = (i - 1) / 2;
int chi = i;
while(chi > 0 && nums[par] < nums[chi]) {
swap(nums[par], nums[chi]);
chi = par;
par = (par - 1) / 2;
}
}
}
void rebuildHeap(vector<int>& nums, int par, int last) {
int left = par * 2 + 1;
int right = par * 2 + 2;
int maxi = left;
if(right <= last && nums[right] > nums[left]) maxi = right;
if(left <= last && nums[par] < nums[maxi]) {
swap(nums[par], nums[maxi]);
rebuildHeap(nums, maxi, last);
}
}
