首页 > 代码库 > 烙饼排序
烙饼排序
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 value11 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 sorted19 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 index29 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 position44 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 algorithm55 // 1. find the biggest value‘s index56 // 2. check if the index is at the head of the array57 // true : enter the next loop58 // false : go to 3 step59 // 3. check if the index is at the end of the array60 // true : go to 4 step61 // false : reverse the part -- get the biggest value to the end of the array62 // 4. reverse the selected part of the array63 // 5. check whether the array is sorted64 // true : break the loop65 // false : enter the next loop66 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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。