Data Structure PTA-Sort
7-12 Insertion sort
插入排序
Implement the insertion sort algorithm in descending order.
输入格式:
Input,2 line.
First line means the number of keys (<=20)
The second line means the initial key sequence consisted of several integers divided by common输出格式:
Output, Several lines.
Each line gives the every iteration of insertion sort. Add “\n” to the end of each line.输入样例:
在这里给出一组输入。例如：
2
7,3,1,输出样例:
在这里给出相应的输出。例如：
2
1,3,7,
思想
向有序序列中插入元素
步骤
- 将第一个元素视为有序序列
- 对于有序列后的元素，比较与前一个元素值，不符合序列顺序则交换两元素。
- 步骤2实例解释：对于有序列[4,6,8]，待排元素[5]。5与8，6，4依次比较，得出5应插入4、6中间。在代码中实现途径为依次交换两元素
代码
1 |
|
7-13 Shell sort
希尔排序
Use Shell sort algorithm and Shell Increment Sequence to sort a sequence in descending orders.
输入格式:
2 lines.
The first line means the number(<=20) of keys.
The second line is consisted of several integers divided by comma.输出格式:
Several lines.
Each line shows the middle result of shell sort. Add ‘\n’ to the end of each line输入样例:
在这里给出一组输入。例如：
2
49,38,65,97,76,13,27,50,2,8,输出样例:
在这里给出相应的输出。例如：
2
3
76,97,65,50,49,38,27,13,2,8,
97,76,65,50,49,38,27,13,8,2,
思想
下标按一定增量进行分组，组内使用直接插入排序算法排序；增量逐渐减少，减至1时，整个文件恰被分成一组，排序完成。
步骤
- 算法开始时不妨设gap=len/2，取出第一组序列，进行直接插入排序
- 在直接插入算法中，我们设有序序列的后一位元素索引为
j在比较过程中，j不断与j - 1进行比较，交换后j变为j - 1 - 同理，由于我们取出的序列间隔为
gap，上述过程的j - 1则变为j - gap，同时结束循环后增量缩小一半
代码
1 |
|
7-14 Quick sort
快速排序
According to the basic idea of quick sort algorithm descirbed on class, we will modify a > little bit of this algorithm.
Only the first pivot is given by the input operation. The other pivots will still use > Median-of-Three patitioning method.
The inithial sequence is {49,38,65,97,76,13,27,50,2,8}. We will sort this sequence in ascending > order.
The parameter Cutoff is 3.输入格式:
The index of first pivot in the sequence. The index begins from 0.
输出格式:
Several lines. Each line shows the temporary result of sort.
In each interation, if the quicksort method is used, then add “Qsort:” before the result. The first number in bracket is the left index of sequence processed by quick sort method, and the second number is the right index of this sequence.
If the insertion sort method is used, then add “Insert:” before the result. The first number in brackets is the left index of sequence processed by insertion sort method, and the second number means the amount of the following elements.
Add “\n” to the end of each line.输入样例:
在这里给出一组输入。例如：
输出样例:
在这里给出相应的输出。例如：
2
3
4
5
6
7
Qsort(0,3):2,8,27,13,38,97,65,50,49,76,
insert(0,1):2,8,27,13,38,97,65,50,49,76,
insert(2,2):2,8,13,27,38,97,65,50,49,76,
Qsort(5,9):2,8,13,27,38,50,65,49,76,97,
insert(5,3):2,8,13,27,38,49,50,65,76,97,
insert(9,1):2,8,13,27,38,49,50,65,76,97,
思想
步骤
代码
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void printarr(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d,", arr[i]);
}
printf("\n");
}
void insertsort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int j = i;
while (j > 0 && arr[j] < arr[j - 1]) {
swap(&arr[j], &arr[j - 1]);
j--;
}
}
}
int getpivot(int arr[], int left, int right) {
//less than 3 elements
if (right - left < 2) {
return arr[left];
}
int mid = (left + right) / 2;
if (arr[left] > arr[mid]) {
swap(&arr[left], &arr[mid]);
}
if (arr[left] > arr[right]) {
swap(&arr[left], &arr[right]);
}
if (arr[mid] > arr[right]) {
swap(&arr[mid], &arr[right]);
}
//将pivot放在right-1，同时right必定大于pivot
//只需排序left+1到right-2
swap(&arr[mid], &arr[right - 1]);
return arr[right - 1];
}
int partition_first(int arr[], int left, int right, int pivotval) {
int l = left - 1, r = right;
while (1) {
while (arr[++l] < pivotval) {}
while (arr[--r] > pivotval) {}
if (l < r) {
swap(&arr[l], &arr[r]);
}
else {
break;
}
}
swap(&arr[l], &arr[right]);
return l;
}
int partition(int arr[], int left, int right, int pivotval) {
int l = left, r = right - 1;
while (1) {
while (arr[++l] < pivotval) {}
while (arr[--r] > pivotval) {}
if (l < r) {
swap(&arr[l], &arr[r]);
}
else {
break;
}
}
swap(&arr[l], &arr[right - 1]);
return l;
}
void quicksort(int arr[], int left, int right, int pivotval) {
int offset = 3;
if (left + offset > right) {
insertsort(arr + left, right - left + 1);
printf("insert(%d,%d):", left, right - left + 1);
printarr(arr, 10);
return;
}
int mididx = partition(arr, left, right, pivotval);
printf("Qsort(%d,%d):", left, right);
printarr(arr, 10);
quicksort(arr, left, mididx - 1, getpivot(arr, left, mididx - 1));
quicksort(arr, mididx + 1, right, getpivot(arr, mididx + 1, right));
}
int main() {
int arr[10] = {49, 38, 65, 97, 76, 13, 27, 50, 2, 8};
int initpivot;
scanf("%d", &initpivot);
int pivotval = arr[initpivot];
swap(&arr[9], &arr[initpivot]);
//first time operation
int mididx = partition_first(arr, 0, 9, pivotval);
printf("Qsort(%d,%d):", 0, 9);
printarr(arr, 10);
//recursive operation
quicksort(arr, 0, mididx - 1, getpivot(arr, 0, mididx - 1));
quicksort(arr, mididx + 1, 9, getpivot(arr, mididx + 1, 9));
return 0;
}
1 |
|
7-15 Selection sort
选择排序
Use selection sort algorithm to sort a sequence in ascending orders.
输入格式:
2 lines.
The first line means the number(<=20) keys.
The second line is consisited of several integers divided by comma.输出格式:
Several lines. Each line shows the step result of selection sort.
Add “\n” to the end of each line.输入样例:
在这里给出一组输入。例如：
2
49,38,65,97,76,输出样例:
在这里给出相应的输出。例如：
2
3
4
38,49,65,97,76,
38,49,65,97,76,
38,49,65,76,97,
思想
始终选择最小项放于乱序列首位（与乱序列首位元素交换）
步骤
- 找出乱序列中最小的元素，记录其索引
- 与乱序列首位元素交换位置
- 乱序堆首位元素有序
代码
1 |
|
