题目描述
给定N个（长整型范围内的）整数，要求输出从小到大排序后的结果。
本题旨在测试各种不同的排序算法在各种数据情况下的表现。各组测试数据特点如下：
- 数据1：只有1个元素；
- 数据2：11个不相同的整数，测试基本正确性；
- 数据3：103个随机整数；
- 数据4：104个随机整数；
- 数据5：105个随机整数；
- 数据6：105个顺序整数；
- 数据7：105个逆序整数；
- 数据8：105个基本有序的整数；
- 数据9：105个随机正整数，每个数字不超过1000。
输入格式:
输入第一行给出正整数N（≤10^5），随后一行给出N个（长整型范围内的）整数，其间以空格分隔。
输出格式:
在一行中输出从小到大排序后的结果，数字间以1个空格分隔，行末不得有多余空格。
输入样例:
11
4 981 10 -17 0 -20 29 50 8 43 -5
输出样例:
-20 -17 -5 0 4 8 10 29 43 50 981
代码
冒泡排序
最好情况下时间复杂度为O(N)，数组是顺序的时候；最坏情况下时间复杂度为O(N^2)，数组是逆序的时候。具有稳定性。
void bubble_sort(int A[], int N) {
int flag;
for (int i = N - 1; i >= 0; i--) {
flag = 0;
for (int j = 0; j < i; j++) {
if (A[j] > A[j + 1]) {
int temp = A[j];
A[j] = A[j + 1];
A[j + 1] = temp;
flag = 1;
}
}
if (!flag) break;
}
}
插入排序
最好情况下时间复杂度为O(N)，数组是顺序的时候；最坏情况下时间复杂度为O(N^2)，数组是逆序的时候。具有稳定性。
void insert_sort(int A[], int N) {
int temp, i, j;
for (i = 1; i < N; i++) {
temp = A[i];
for (j = i - 1; j >= 0 && A[j] > temp; j--)
A[j + 1] = A[j];
A[j + 1] = temp;
}
}
希尔排序
插入排序的升级版，时间复杂度在O(N)与O(N^2)之间。不具有稳定性。
void shell_sort(int A[], int N) {
int stride = 1, temp, i, j;
while (stride < N / 3)
stride = 3 * stride + 1;
while (stride >= 1) {
for (i = stride; i < N; i++) {
temp = A[i];
for (j = i - stride; j >= 0 && A[j] > temp; j -= stride)
A[j + stride] = A[j];
A[j + stride] = temp;
}
stride /= 3;
}
}
选择排序
时间复杂度为O(N^2)，即使是顺序也是如此。不具有稳定性。很垃圾。
void select_sort(int A[], int N) {
int min_pos, temp;
for (int i = 0; i < N; i++) {
min_pos = i;
for (int j = i; j < N; j++) {
if (A[j] < A[min_pos])
min_pos = j;
}
if (min_pos != i) {
temp = A[i];
A[i] = A[min_pos];
A[min_pos] = temp;
}
}
}
堆排序
选择排序的升级版，时间复杂度为O(NlogN)。不具有稳定性。
void perc_down(int A[], int N, int p) {
int parent, child;
int temp = A[p];
for (parent = p; 2 * parent + 1 < N; parent = child) {
child = 2 * parent + 1;
if (child + 1 < N && A[child + 1] > A[child])
child += 1;
if (temp < A[child])
A[parent] = A[child];
else
break;
}
A[parent] = temp;
}
void heap_sort(int A[], int N) {
int temp;
//O(N)复杂度建大顶堆
for (int i = N / 2 - 1; i >= 0; i--)
perc_down(A, N, i);
//O(NlogN)复杂度排序
for (int i = N - 1; i > 0; i--) {
temp = A[i];
A[i] = A[0];
A[0] = temp;
perc_down(A, i, 0);
}
}
归并排序
时间复杂度O(NlogN)，空间复杂度O(N)，具有稳定性。
void m_sort(int A[], int tempA[], int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
m_sort(A, tempA, low, mid);
m_sort(A, tempA, mid + 1, high);
merge(A, tempA, low, mid, high);
}
}
void merge(int A[], int tempA[], int low, int mid, int high) {
int i = low, j = mid + 1, k = low;
while (i <= mid && j <= high) {
if (A[i] <= A[j])
tempA[k++] = A[i++];
else
tempA[k++] = A[j++];
}
while (i <= mid)
tempA[k++] = A[i++];
while (j <= high)
tempA[k++] = A[j++];
for (int m = low; m <= high; m++)
A[m] = tempA[m];
}
void merge_sort(int A[], int N) {
int *tempA = (int*) malloc(N * sizeof(int));
if (tempA) {
m_sort(A, tempA, 0, N - 1);
} else {
printf("空间不足
");
}
}
快速排序
最好时间情况下时间复杂度为O(NlogN)，数组的顺序很乱的时候；最坏情况下时间复杂度为O(N^2)，数组是顺序或逆序的时候。空间复杂度为O(logN)。不具有稳定性。
void q_sort(int A[], int N, int low, int high) {
if (low >= high) return;
int i = low, j = high;
int temp = A[low];
while (i < j) {
while (i < j && A[j] >= temp) j--;
A[i] = A[j];
while (i < j && A[i] <= temp) i++;
A[j] = A[i];
}
A[i] = temp;
q_sort(A, N, low, i);
q_sort(A, N, i + 1, high);
}
void quick_sort(int A[], int N) {
q_sort(A, N, 0, N - 1);
}