1 #include <stdio.h>
2 // print the array
3 int printArr(
int* arr,
int length)
4 {
5 int i =
0;
6 for(i=
0;i<length;i++
)
7 printf(
"%d\t",arr[i]);
8 printf(
"\n");
9 }
10 // swap 2 value
11 void swapValue(
int *a,
int *
b)
12 {
13 int temp =
0;
14 temp = *
a;
15 *a = *
b;
16 *b =
temp;
17 }
18 // check whether the array is sorted
19 int isDone(
int * arr,
int length)
20 {
21 while(--length>=
1)
22 {
23 if(arr[length]>arr[length-
1])
24 return 0;
25 }
26 return 1;
27 }
28 // find the biggest value's index
29 int findMaxIndex(
int* arr,
int length)
30 {
31 int i =
0;
32 int standBy = arr[
0];
33 while(length--
)
34 {
35 if(standBy <
arr[length])
36 {
37 standBy =
arr[length];
38 i =
length;
39 }
40 }
41 return i;
42 }
43 // reverse the part of the array from the start position
44 int reversePart(
int* arr,
int start,
int length)
45 {
46 int end = length-
1;
47 while(start<=
end)
48 {
49 swapValue(&arr[start],&
arr[end]);
50 start++
;
51 end--
;
52 }
53 }
54 // core algorithm
55 // 1. find the biggest value's index
56 // 2. check if the index is at the head of the array
57 // true : enter the next loop
58 // false : go to 3 step
59 // 3. check if the index is at the end of the array
60 // true : go to 4 step
61 // false : reverse the part -- get the biggest value to the end of the array
62 // 4. reverse the selected part of the array
63 // 5. check whether the array is sorted
64 // true : break the loop
65 // false : enter the next loop
66 void biscuitSort(
int* arr,
int length)
67 {
68 int start =
0;
69 int maxIndex =
0;
70 for(start =
0; start < length; start++
)
71 {
72 maxIndex = findMaxIndex(arr+start,length-
start);
73 if(maxIndex !=
0)
74 {
75 if(maxIndex != length-start-
1)
76 {
77 reversePart(arr+start,maxIndex,length-
start);
78 printArr(arr,length);
79 }
80 reversePart(arr+start,
0,length-
start);
81 printArr(arr,length);
82 if(isDone(arr,length))
83 break;
84 }
85 }
86 }
87
88 int main()
89 {
90 int arr[]= {
7,
1,
2,
5,
4};
91 printArr(arr,
sizeof(arr)/
sizeof(
int));
92 biscuitSort(arr,
sizeof(arr)/
sizeof(
int));
93 return 0;
94 }
转载于:https://www.cnblogs.com/warnet/p/3862532.html
相关资源：数据结构—成绩单生成器
