排序代码
| 算法 | 平均时间复杂度 | 空间复杂度 | 最坏情况 | 排序方式 | 稳定性 |
| 归并排序 | O(n log n) | O(n) | O(n log n) | 外 | 稳定 |
| 选择排序 | O(n^2) | O(1) | O(n log n) | 内 | 不稳定 |
| 堆排序 | O(n log n) | O(1) | O(n log n) | 内 | 不稳定 |
| 插入排序 | O(n^2) | O(1) | O(n^2) | 内 | 稳定 |
| 希尔排序 | O(n log^2 n) | O(1) | | 内 | 不稳定 |
| 快速排序 | O(n log n) | O(log n) | O(n^2) | 内 | 不稳定 |
| 冒泡排序 | O(n^2) | O(1) | O(n^2) | 内 | 稳定 |
| 基数排序k是关键字取值范围 | O(n) | O(k) | | 外 | 稳定 |
bool flag = true;
for (int i = 1; i < zq.size(); ++i) //第一层循环，最多要冒泡数组个数-1次才能排完序
{
flag = false;
for (int j = 0; j < (zq.size() - i); ++j) //第二层循环，循环次数为数组总个数 - 第几个元素。 {
if (zq[j + 1] < zq[j])
{
flag = true;
temp = zq[j + 1];
zq[j + 1] = zq[j];
zq[j] = temp;
}
}
} void quick_sort(vector<int>&zq, int left, int right)
{
if (left > right)
return;
int i = left + 1;
int j = right;
int temp = zq[left]; //界点
while (i <= j)
{
while (zq[i] < temp)
i++;
while (zq[j] > temp)
j--;
if (i < j)
swap(zq[i++], zq[j--]);
else
i++;
}
swap(zq[j], zq[left]); //j就是界点应该的位置
quick_sort(zq,left,j-1); //界点左侧分治
quick_sort(zq,j+1,right);//界点右侧分治
}
void merge(vector<int>&zq, int low, int mid, int high)
{ //low为第一有序区第一元素，mid为第一有序区最后元素
int i = low, j = mid + 1,count=low;
while (i <= mid && j <= high)
{
if (zq[i] <= zq[j])
result[count++] = zq[i++];
else
result[count++] = zq[j++];
}
while (i <= mid)//比较完后，第一区仍有剩余
result[count++] = zq[i++];
while (j <= high)//比较完后，第二区仍有剩余
result[count++] = zq[j++];
for (int i = low; i <= high; i++)
zq[i] = result[i];
}
void mergesort(vector<int>&zq,int low,int high)
{
if (low < high)
{
int mid = (low + high) / 2;
mergesort(zq, low, mid);
mergesort(zq, mid + 1, high);
merge(zq, low, mid, high);
}
} 
