qsort

qsort的使用方法如下:

1
2
#include <stdlib.h> 
void qsort( void *buf, size_t num, size_t size, int (*compare)(const void *, const void *));

buf:要排序数组的起始地址
num：数组中元素的个数
size：数组中每个元素所占用的空间大小
compare:比较规则，需要我们传递一个函数名

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdlib.h> 
#include<stdio.h>
typedef int ElemType;
int compare(const void* left, const void* right) {
	//return *(ElemType*)left - *(ElemType*)right;//从小到大
	return *(ElemType*)right - *(ElemType*)left;//从大到小
}
int main() {
	int a[5] = { 3,25,42,12,2 };
	qsort(a, 5, sizeof(ElemType), compare);
	for (int i = 0; i < 5; i++) {
		printf("%3d", a[i]);
	}
}

交换排序

冒泡排序

**冒泡可以是从下往上，**即将元素从前往后，两两比较，最多经过n-1趟，每一趟将一个元素有序地放在后面。

**也可以从上往下。**即将元素从后往前，两两比较，最多经过n-1趟，每一趟将一个元素有序地放在前面面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Bubble_Sort(int a[], int n) {
	bool flag;
	n = n - 1;
	for (int i = 0; i < n; i++)
	{
		flag = false;
		for (int j = n; j > i; j--)
		{
			if (a[j-1] > a[j])
			{
				flag = true;
				swap(a[j-1], a[j]);
			}
		}
		if (flag == false)
		{
			return;
		}
	}
}

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int Partition(int a[], int low, int high) {
	int pivot = a[low];//取出第一个元素作为枢轴
	while (low<high)
	{
		//如果a[high]大于枢轴，high一直向左移动。
		while (low < high && a[high] >= pivot) {
			high--;
		}
		//否则，停止。让a[high]覆盖a[low]
		a[low] = a[high];
		//如果a[low]小于枢轴，low一直向右移动。
		while (low < high && a[low] <= pivot)
		{
			low++;
		}
		//否则，让a[low]覆盖a[high]
		a[high] = a[low];
	}
	//最后再把枢轴覆盖到high与low相遇的地方。
	a[low] = pivot;
	//一趟下来，low的左边都比a[low]小，low的右边都比a[low]大
	return low;
}


void QuickSort(int a[], int low, int high) {
	if (low < high) {
		//切割位
		int pivotpos = Partition(a, low, high);//low,high分别为指针
		QuickSort(a, low, pivotpos - 1);
		QuickSort(a, pivotpos + 1, high);
	}
}

插入排序

直接插入排序

数组的第一个元素a[0]用于存放哨兵，从第2个元素a[1]开始存放序列。

原理：

先将序列分割成前面1个有序序列（一开始元素是1个），后面1个无序序列。后面的无序序列就一个个将元素在前面的有序序列种找到合适位置插入。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void InsertSort(int a[], int n) {
	int i, j;
	for (i = 2; i <= n; i++) {
		if (a[i] < a[i - 1]) {
			a[0] = a[i];
			for (j = i - 1; a[0] < a[j]; j--) {	//在有序序列中从后往前遍历
				a[j + 1] = a[j];
			}
			a[j + 1] = a[0];
		}
	}
}
int c[11];
InsertSort(c, 10);

折半查找 插入

希尔排序

选择排序

简单选择排序

有表L[1 … n]

第i趟排序从L[i...n]中选择关键字最小的元素与L[i]进行交换，这样每一趟排序可以确定一个元素的最终位置，这样通过n-1趟排序，可以使表有序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void SelectSort(int A[], int n) {
	int min;
	for (int i = 1; i <= n-1 ; i++)//共n-1趟
	{
		min = i;
		for (int j = i + 1; j <= n; j++)
		{
			if (A[j] < A[min]) {
				min = j;
			}
		}
		if (min!=i)
		{
			swap(A[min], A[i]);
		}
	}
}

堆排序

堆：把一个一维数组，在逻辑上，用层次建树的方法把它构造成一颗完全二叉树。

大根堆：任何一个父节点的值大于它的两个孩子

小根堆：任何一个父节点的值小于它的两个孩子

  1. 建立堆（先向上调整，再向下调整）
  2. 不断输出根后，向下调整
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

void HeadAdjust(int A[], int k, int len) {
	A[0] = A[k];
	for (int i = 2*k; i <= len; i*=2)
	{
		if (i < len && A[i] < A[i + 1]) {
			i++;
		}
		if (A[0] >= A[i]) {
			break;
		}
		else {
			A[k] = A[i];
			k = i;
		}
	}
	A[k] = A[0];
}

void BuildMaxHeap(int A[], int len) {	//建立大根堆
	for (int i = len / 2; i > 0; i--) {	//从下往上调整
		HeadAdjust(A, i, len);
	}
}

void HeapSort(int A[], int len) {
	BuildMaxHeap(A, len);	//建立大根堆
	for (int i = len; i > 1; i--) {
		swap(A[i], A[1]);
		HeadAdjust(A, 1, i - 1);
	}
}

归并排序