内部排序:
-
稳定排序(冒泡、插入、归并):重复的元素一定按原始顺序排列
-
非稳定排序(选择、快排)
外部排序:多路归并排序
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define swap(a, b) { \
__typeof(a) __temp = a; \
a = b; b = __temp; \
}
#define TEST(arr, n, func) { \
int *arr_test = (int *)malloc(sizeof(int) * n); \
memcpy(arr_test, arr, sizeof(int) * n); \
output(arr_test, n); \
printf("%s = ", #func); \
func(arr_test, n); \
output(arr_test, n); \
free(arr_test); \
printf("\n"); \
}
void bubble_sort(int *arr, int n) {
int flag = 1;
for (int i = 0; i < n - 1 && flag; i++) {
flag = 0; //如果flag始终没有被改变过,则证明序列已经是有序的
for (int j = n - 1; j > i; j--) {
if (arr[j] < arr[j - 1]) {
swap(arr[j], arr[j - 1]);
flag = 1;
}
}
}
return;
}
void insert_sort(int *arr, int n) {
for (int i = 1; i < n; i++) {
for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
swap(arr[j], arr[j - 1]);
}
}
return;
}
void merge_sort_recur(int *arr, int l, int r) {
if (r - l <= 1) {
if (r - l == 1 && arr[r] < arr[l]) swap(arr[r], arr[l]);
return;
}
int mid = (l + r) >> 1;
merge_sort_recur(arr, l, mid);
merge_sort_recur(arr, mid + 1, r);
int *temp = (int *)malloc(sizeof(int) * (r - l + 1));
int p1 = l, p2 = mid + 1;
for (int i = 0; p1 <= mid || p2 <= r; i++) {
if (p2 > r || (p1 <= mid && arr[p1] < arr[p2])) {
temp[i] = arr[p1++];
} else {
temp[i] = arr[p2++];
}
}
memcpy(arr + l, temp, sizeof(int) * (r - l + 1));
free(temp);
return;
}
void merge_sort(int *arr, int n) {
merge_sort_recur(arr, 0, n - 1);
return;
}
void select_sort(int *arr, int n) {
for (int i = 0; i < n; i++) {
int index = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[index]) index = j;
}
swap(arr[i], arr[index]);
}
return;
}
void quick_sort_recur(int *arr, int l, int r) {
if (l >= r) return;
int x = l, y = r, base = arr[l];
while (x < y) {
while (x < y && arr[y] >= base) y--;
if (x < y) swap(arr[x], arr[y]);
while (x < y && arr[x] <= base) x++;
if (x < y) swap(arr[x], arr[y]);
}
arr[x] = base;
quick_sort_recur(arr, l, x - 1);
quick_sort_recur(arr, x + 1, r);
return;
}
void quick_sort(int *arr, int n) {
quick_sort_recur(arr, 0, n - 1);
return;
}
void randint(int *arr, int n) {
while (n--) arr[n] = rand() % 100; //判断的时候不减,判断完就已经减了,所以n的范围是[MAX_N - 1, 0]
return;
}
void output(int *arr, int n) {
printf("[");
for (int i = 0; i < n; i++) {
i && printf(" ");
printf("%d", arr[i]);
}
printf("]\n");
}
int main() {
srand(time(0));
#define MAX_N 20
int arr[MAX_N];
randint(arr, MAX_N);
TEST(arr, MAX_N, bubble_sort);
TEST(arr, MAX_N, insert_sort);
TEST(arr, MAX_N, merge_sort);
TEST(arr, MAX_N, select_sort);
TEST(arr, MAX_N, quick_sort);
#undef MAX_N
return 0;
}
快排退化与改进!!!
标签:sort,arr,int,flag,算法,test,排序 From: https://www.cnblogs.com/Kelvin-Wu/p/16795306.html