C语言数据结构(排序算法总结)

目录

算法类型

算法比较

稳定性描述

插入排序

选择排序

冒泡排序

希尔排序

堆排序

快速排序

霍尔排序（递归）

挖坑法（递归）

双指针（递归）

快排(非递归)

归并排序

计数排序

总结（速度比较）

算法类型

插入排序，选择排序，冒泡排序，希尔排序，堆排序，快速排序（递归霍尔，挖坑，双指针，非递归），归并排序（递归，非递归），计数排序

算法比较

稳定性描述

数组相同大小元素顺序是否发生变化

插入排序

// 插入排序
void InsertSort(int* a, int n) {
	int i,tmp,j;
	for (i = 0; i < n - 1; i++) {
		tmp = a[i + 1];
		for (j = i; j >= 0; j--) {
			if (a[j] > tmp)
				a[j + 1] = a[j];
			else
				break;
		}
		a[j + 1] = tmp;
	}
}

特性：

越有序越快，算法稳定

时间复杂度：

O(N^2)

空间复杂度:

O(1)

选择排序

// 选择排序
void SelectSort(int* a, int n) {
	int i, j, max, min,mid=n/2;
	for (i = 0; i < mid; i++) {
		max = min = i;
		for (j = i; j < n - i; j++) {
			if (a[j] > a[max])
				max = j;
			if (a[j] < a[min])
				min = j;
		}
		swap(&a[i], &a[min]);
		if (max == i)
			max = min;
		swap(&a[n - i - 1], &a[max]);
	}
}

特性：

效率比较稳定，算法不稳定(看自己写的算法取值)

时间复杂度：

O(N^2)

空间复杂度:

O(1)

冒泡排序

// 冒泡排序
void BubbleSort(int* a, int n) {
	int i, j;
	for (i = 0; i < n - 1; i++) {
		for (j = 0; j < n - i - 1; j++) {
			if (a[j] > a[j + 1])
				swap(&a[j], &a[j + 1]);
		}
	}
}

特性：

算法稳定，效率一般，有教学意义

时间复杂度：
O(N^2)

空间复杂度:

O(1)

希尔排序

void ShellSort(int* a, int n) {
	int i, j, gap=n, tmp,k;
	while (gap > 1) {
		gap = gap / 3 + 1;
		for (i = 0; i < gap; i++) {
			for (k = i; k < n - gap; k += gap) {
				tmp = a[k + gap];
				for (j = k; j >= 0; j -= gap) {
					if (a[j] > tmp)
						a[j + gap] = a[j];
					else
						break;
				}
				a[j + gap] = tmp;
			}
		}
	}
}

特性:

算法非常不稳定，无法预测

是插入排序的升级版，针对无序情况

时间复杂度:
O(N^1.3)

空间复杂度:

O(1)

堆排序

// 堆排序
void AdjustDown(int* a, int n, int root) {//大堆
	int parent=root,child=parent*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]);
		else
			break;
		parent = child;
		child = child * 2 + 1;
	}
}
void HeapSort(int* a, int n) {
	int i;
	for (i = (n - 1 - 1) / 2; i >= 0; i--)
		AdjustDown(a, n, i);
	for (i = n - 1; i > 0; i--) {
		swap(&a[i], &a[0]);
		AdjustDown(a, i, 0);
	}
}

特性：

排序时间比较稳定，算法不稳定

时间复杂度：

向上整理成堆:O(NlogN)

向下整理成堆堆:O(N)

堆排序：O(NlogN)

空间复杂度:

O(1)

快速排序

特性：

算法不稳定，越有序越慢

时间复杂度：

O(NlogN)

空间复杂度:

O(1)

优化：

越有序越慢，我们可以找到一个值不是最大也不是最小，与首元素进行交换提升效率

在元素个数比较少时使用插入排序

霍尔排序（递归）

// 快速排序递归实现
// 快速排序hoare版本
void PartSort1(int* a, int left, int right) {
	if (left >= right)
		return;
	int begin = left, end = right,key=left;
	while (begin < end) {
		while (begin<end&&a[end] >= a[key])
			end--;
		while (begin<end&&a[begin] <= a[key])
			begin++;
		swap(&a[begin], &a[end]);
	}
	swap(&a[key], &a[end]);
	key = begin;
	PartSort1(a, left, key - 1);
	PartSort1(a, key + 1, right);
}

挖坑法（递归）

// 快速排序挖坑法
void PartSort2(int* a, int left, int right) {
	if (left >= right)
		return;
	int begin = left, end = right, tmp = a[left];
	while (begin < end) {
		while (begin<end&&a[end] >= tmp)
			end--;
		a[begin] = a[end];
		tmp = a[end];
		while (begin<end&&a[begin] <= tmp)
			begin++;
		a[end] = a[begin];
		tmp = a[end];
	}
	a[end] = tmp;
	PartSort2(a, left, begin - 1);
	PartSort2(a, end + 1, right);
}

双指针（递归）

void QuickSort(int* a, int left, int right) {
	if (left >= right)
		return;
	int cur = left + 1, pre = left;
	while (cur <= right) {
		if (a[cur] < a[left] && ++pre < cur)
			swap(&a[cur], &a[pre]);
		cur++;
	}
	swap(&a[left], &a[pre]);
	QuickSort(a, pre + 1, right);
	QuickSort(a, left, pre - 1);
}

快排(非递归)

选择一种快排方法，返回修正位置key

int PartSort3(int* a, int left, int right) {
	if (left >= right)
		return -1;
	int cur = left + 1, pre = left;
	while (cur <= right) {
		if (a[cur] < a[left] && ++pre < cur)
			swap(&a[cur], &a[pre]);
		cur++;
	}
	swap(&a[left], &a[pre]);
	return pre;
}
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right) {
	Stack stack;
	StackInit(&stack);
	StackPush(&stack, right);
	StackPush(&stack, left);
	while (!StackEmpty(&stack)) {
		int begin = StackTop(&stack);
		StackPop(&stack);
		int end = StackTop(&stack);
		StackPop(&stack);
		int key = PartSort3(a, begin, end);
		if (key - 1 > begin) {
			StackPush(&stack, key-1);
			StackPush(&stack, begin);
		}
		if (key + 1 < end) {
			StackPush(&stack, end);
			StackPush(&stack, key+1);
		}
	}
}

归并排序

特性：

稳定，时间复杂度也稳定

时间复杂度:

O(NlogN)

空间复杂度:

O(N)

递归

void _merge(int* a, int* tmp, int left, int right) {
	if (left >= right)
		return;
	int mid = (left + right) / 2;
	_merge(a, tmp,left, mid);
	_merge(a, tmp, mid + 1, right);
	int begin1 = left, begin2 = mid + 1,i=left;
	while (begin1 <= mid && begin2 <= right) {
		if (a[begin1] > a[begin2])
			tmp[i++] = a[begin2++];
		else
			tmp[i++] = a[begin1++];
	}
	while(begin1 <= mid)
		tmp[i++] = a[begin1++];
	while (begin2 <= right)
		tmp[i++] = a[begin2++];
	memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));
}
// 归并排序递归实现
void MergeSort(int* a, int n) {
	int* tmp = (int*)malloc(sizeof(int) * n);
	_merge(a, tmp, 0, n - 1);
	free(tmp);
	tmp = NULL;
}

非递归

// 归并排序非递归实现
void MergeSortNonR(int* a, int n) {
	int gap = 1,i,begin,*tmp=(int*)malloc(sizeof(int)*n);
	while (gap < n) {
		for (begin = 0; begin < n - gap; begin+=2*gap) {
			int begin1 = begin,end1=begin+gap-1,begin2=begin+gap,end2=begin2+gap-1;
			if (begin2 >= n)
				break;
			if (end2 >= n)
				end2 = n - 1;
			i = begin;
			while (begin1 <= end1 && begin2 <= end2) {
				if (a[begin1] < a[begin2])
					tmp[i++] = a[begin1++];
				else
					tmp[i++] = a[begin2++];
			}
			while (begin1 <= end1)
				tmp[i++] = a[begin1++];
			while (begin2 <= end2)
				tmp[i++] = a[begin2++];
		}
		memcpy(a, tmp, sizeof(int) * n);
		gap *= 2;
	}
}

计数排序

// 计数排序
void CountSort(int* a, int n) {
	int max, min, i,j=0;
	max = min = a[0];
	for (i = 1; i < n; i++) {
		if (a[i] > max)
			max = a[i];
		if (a[i] < min)
			min = a[i];
	}
	int* arr = (int*)calloc(max - min + 1, sizeof(int));
	for (i = 0; i < n; i++)
		arr[a[i] - min]++;
	for (i = 0; i < max - min + 1; i++) {
		while (arr[i]--)
			a[j++] = min+i;
	}
}

特性：

空间复杂度仅与最大最小数有关，只可用于排列数

数越均衡越快

时间复杂度：

O(N)//均衡的话

总结（速度比较）

先比较插入，选择，冒泡排序，放置1w个随机数

比较剩下几个排序，每个放入1000w个数

由于伪随机数非常均衡，因此相对来说计数排序效率相对来说非常高