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
2
3
4
5
6
7
8
9
10
11
12
13
1.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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1.4 插入排序
算法思想
从第一个元素开始,该元素可以认为已经被排序。
取出下一个元素,在已经排序的元素序列中从后向前扫描。
如果该元素(已排序)大于新元素,该元素移到下一个位置。
重复步骤3,直到找到已排序的元素小于或者等于新的元素的位置。
将元素插入到对应位置。
重复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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1.5 快速排序
算法思想
选第一个数为标准。
将比基准小的数据交换到前面,比基准大的交换到后面
对左边的空间和右边的空间重复,直到各区间只有一个数字
图解
代码
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
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。
重复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
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 计数排序
算法思想
找出待排序的数组最大和最小的元素
统计数组中每个值为i的元素出现的个数,存入数组c的第i-min项
将下标+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++;
}
}
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
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 归并排序
算法思想
把长度为n的输入序列分成两个长度为n/2的子序列;
对这两个子序列分别采用归并排序;
将两个排序好的子序列合并成一个最终的排序序列。
图解
代码
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);
}