使用分治法解决全排列和随机快速排序
# 全排列问题
- 固定数组第一个位置，通过将第一个位置和其他位置的数进行交换保证数组中每个数都能做开头
- 每交换一次开头，就对剩下的元素进行全排列，使用递归让固定位后移，直到只剩一个元素进行全排列，输出数组
- 为了避免重复，输出后将交换过的交换回来，在这个基础上换另一个数做开头，重复操作
#include <stdio.h>
void swap(int a[], int i, int j){
int temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
void perm(int a[], int start, int end){//start为当前固定位, end为数组长度
int i;
if(start == end-1){
for(i=0; i<end; i++){
printf("%d ",a[i]);
}
printf("\n");
}
for(i=start; i<end; i++){
swap(a, start, i);//交换固定位与其他位置的数
perm(a, start+1, end);//递归时固定位往下移一个
swap(a, start, i);//打印后交换回来，防止出现问题
}
}
int main(){
int len, i;
printf("请输入集合中的个数：");
scanf("%d",&len);
int list[len];
printf("请输入集合：");
for(i=0; i<len; i++){
scanf("%d",&list[i]);
}
printf("全排列：\n");
perm(list, 0, len);
return 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
36
37
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
# 随机快速问题
- 让left指针指向数组0位置，right指针指向数组尾部，通过随机数选取一个划分元，该随机数为数组的下标
- 将划分元对应的数存储起来，并将left指针指向的数换到划分元所处的位置，以空出left位置
- 从right指针开始比较，如果right指向的数小于等于划分元对应的数，则换到left位置，否则right指针向前移一个；继续判断如果left指向的数大于等于划分元对应的数，则换到right位置，否则left指针向后移一个，直到left与right重合，则将划分元对应的数放入left位置
- 再分别使用上述方法判断左半部分和右半部分，直到所有部分都只剩一个元素，无需进行比较，输出排序后的数组
/*19 97 9 17 1 8
*/
#include <stdio.h>
#include <stdlib.h>
void quickSort(int arr[], int l, int r){
if(l>=r) return ;
int left = l,right = r;
int p = rand()%(r-l+1)+l;//随机选取划分元，下标
int part = arr[p];//划分元
arr[p] = arr[l];//空出最左边的位置，从r开始如果有小于划分位的数则放入l的位置
while(1){
while(l < r && arr[r] >= part) r--;
if(l < r) arr[l] = arr[r];
while(l < r && arr[l] <= part) l++;
if(l < r) arr[r] = arr[l];
if(l >= r){
arr[l] = part;
break;
}
}
quickSort(arr, left, l-1);
quickSort(arr, l+1, right);
}
int main(){
int n, i;
printf("请输入随机快速排序的个数：");
scanf("%d", &n);
int arr[n];
printf("请输入待排序的数：");
for(i=0; i<n; i++){
scanf("%d", &arr[i]);
}
quickSort(arr, 0, n-1);
printf("排序后：\n");
for(i=0; i<n; i++){
printf("%d ", arr[i]);
}
}
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
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
# 整改博客
刚开始搭建自己的博客时折腾了两天，终于魔改完了配置，勉强也有点样子，结果今天下了个进度条插件，直接回到了解放前...🙄然后意外发现还是原始主题更加简洁美观🤣再根据markdown语法再美化了一下自己的博客，每篇的篇幅也有所减少，终于能让我不那么嫌弃了，是心情变好的一天🍉🍉
秋天到了，要添衣嗷~