首页 > 代码库 > 烙饼排序

烙饼排序

 图片
 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 }