十大排序算法-快排-希尔-堆排-归并-冒泡-桶排-选择-插入-计数-基数-1_大排算法

1. 排序算法

1.1 算法的之间的比较

1.2 冒泡排序

算法思想

1. 比较相邻的元素，如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从第一对开始，一直到最后一对，做完后，最后的元素会是最大的元素。
3. 针对所有的元素重复上面的步骤，除排序好的。
4. 持续对越来越少的元素重复上述步骤，直到哪次没有任何一对数字需要比较或者是交换。

图解

代码

void bubbleSort(int a[], int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		for (int j = 0; j < n - i - 1; ++j)
		{
			if (a[j] > a[j + 1])
			{
				swap(a[j], a[j + 1]);
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

1.3 选择排序

算法思想

1. 在未排序的序列中找到最小（大）元素，存放到排序序列的起始位置。
2. 从剩下未排序元素中继续寻找最小（大）元素，然后放到自己已排序的序列的末尾。
3. 以此类推，直到所有元素排序完毕。

图解

代码

void selectionSort(int a[], int len)
{
	int min;
	for (int i = 0; i < len - 1; i++)
	{
		min = i;
		for (int j = i + 1; j < len; j++)
		{
			if (a[j] < a[min])
			{
				min = j;
			}
		}
		swap(a[i], a[min]);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1.4 插入排序

算法思想

1. 从第一个元素开始，该元素可以认为已经被排序。
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描。
3. 如果该元素（已排序）大于新元素，该元素移到下一个位置。
4. 重复步骤3，直到找到已排序的元素小于或者等于新的元素的位置。
5. 将元素插入到对应位置。
6. 重复2~5。

图解

代码

void InsertSort(int a[], int n)
{
	for (int i = 1; i < n; i++)
	{
		if (a[i] < a[i - 1])
		{
			int val = a[i];
			int j = i - 1;
			a[j + 1] = a[j];
			while (j > 0 && val < a[j - 1])
			{
				a[j] = a[j - 1];
				j--;
			}
			a[j] = val;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1.5 快速排序

算法思想

1. 选第一个数为标准。
2. 将比基准小的数据交换到前面，比基准大的交换到后面
3. 对左边的空间和右边的空间重复，直到各区间只有一个数字

图解

代码

void QuickSort(int a[], int left, int right)
{
	if (left >= right)
		return;
	int begin = left;
	int end = right;
	//keyi定在右边，需要从左边开始找
	int keyi = end;
	int key = a[keyi];

	while (begin < end)
	{
		//因为我们从小往大排 
		//从左边开始找 找大
		while (begin < end && a[begin] <= key)
			begin++;
		a[end] = a[begin];

		//从右边开始找 找小
		while (begin < end && a[end] >= key)
			end--;
		a[begin] = a[end];
	}
	a[end] = key;

	QuickSort(a, left, end - 1);
	QuickSort(a, end + 1, right);
}
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

1.6 堆排序

算法思想

1. 如果要从小到大排序，建立大堆，根节点大于左右子树。
2. 将根结和最后一个元素交换，并且树的元素个数减1。
3. 重复1~2，直到只剩一个元素。

图解

代码

void AdjustDown(int* a, int n, int root)//n是大小，root是根节点的下标
{
	int parent = root;
	int child = parent * 2 + 1;

	while (child < n)
	{
		//child指向左右孩子中最小的那个
		if (child + 1 < n && a[child + 1] < a[child])
		{
			child++;
		}
		if (a[child] < a[parent])
		{
			swap(a[child], a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapPop(Heap* php)
{
	assert(php);
	assert(php->size > 0);

	swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;

	AdjustDown(php->a, php->size, 0);
}
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
34
35

1.7 计数排序

算法思想

1. 找出待排序的数组最大和最小的元素
2. 统计数组中每个值为i的元素出现的个数，存入数组c的第i-min项
3. 将下标+min的值根据在数组c中的个数存到原数组中。

图解

代码

void CountSort(int a[], int len)
{
	int max = a[0];
	int min = a[0];
	for (int i = 0; i < len; i++)
	{
		if (a[i] > max)
			max = a[i];
		if (a[i] < min)
			min = a[i];
	}
	int l = max - min;//计算数组最大最小值的差
	int* count_a = new int[l + 1];
	for (int i = 0; i < l + 1; i++)
	{
		count_a[i] = 0;
	}

	for (int i = 0; i < len; i++)
	{
		count_a[a[i] - min]++;//统计元素个数
	}

	int j = 0;
	for (int i = 0; i < len; i)
	{
		while (j <= l && count_a[j])
		{
			count_a[j]--;
			a[i] = j + min;
			i++;
		}
		j++;
	}
}
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
34
35

1.8 桶排序

算法思想

1. 设置一个定量的数组当作空桶；
2. 遍历输入数据，并且把数据一个一个放到对应的桶里去；
3. 对每个不是空的桶进行排序；
4. 从不是空的桶里把排好序的数据拼接起来。

图解

1.9 基数排序

算法思想

1. 取得数组中的最大数，并取得位数。
2. arr为原始数组，从最低位开始取每个位组成radix数组。
3. 对radix进行计数排序（利用计数排序适用于小范围数的特点）。

图解

1.10 希尔排序

算法思想

1. 选择一个增量序列t1,t2,…,tk,其中ti>tj,tk = 1。
2. 按照增量序列个数k，对序列进行k趟排序
3. 每趟排序根据对应的增量ti，将待排序的序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。

图解

代码

void ShellSort(int* a, int n)
{
	printf("原数组->", gap);
	PrintArray(a, n);

	int gap = n;//间隔
	while (gap > 1)
	{
		gap = gap / 3 + 1;//保证最后一趟一定为1
		for (int i = 0; i < n - gap; i++)
		{
			int end = 0;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}

			a[end + gap] = tmp;
		}
		printf("gap:%d->", gap);
		PrintArray(a, n);
	}
}
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

1.11 归并排序

算法思想

1. 把长度为n的输入序列分成两个长度为n/2的子序列；
2. 对这两个子序列分别采用归并排序；
3. 将两个排序好的子序列合并成一个最终的排序序列。

图解

代码

void _MergeSort(int* a, int left, int right, int* tmp)
{
	if (left == right)
		return;

	//int mid = (left + right) >> 1;//有溢出风险
	int mid = left + ((right - left) >> 1);

	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid + 1, right, tmp);

	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int i = begin1;

	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++];
	}

	//拷回原数组
	int j = left;
	while (j <= right)
	{
		a[j] = tmp[j];
		j++;
	}
}

void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int)*n);
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
}
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52