資料結構--排序

----------------

排序

----------------

冒泡排序思想：

“比較相鄰的元素，如果第一個比第二個大,就交換他們兩個， 對每一對相鄰元素做同樣的作業,從開始第一對到結尾的最后一對，在這一點,最后的元素應該會是最大的數， 針對所有的元素重復以上的步驟,除了最后一個， 持續每次對越來越少的元素重復上面的步驟,直到沒有任何一對數字需要比較，”

選擇排序思想：

測驗主函式

 1 #include <stdio.h> 2 #include<stdlib.h> 3 #include <time.h> 4 #include "sort.h" 5  6  7 int main() 8 { 9     ArrayList numlist;10     PtArrayList pt_arraylist;11     pt_arraylist = &numlist;12     while(True){13         Init_Data(pt_arraylist);14         show((char *)"排序前 ", pt_arraylist);15         16 //        BubbleSort_Low(pt_arraylist);17 //        BubbleSort_Mid(pt_arraylist);18 //        BubbleSort_Mid_Opt(pt_arraylist);19 //        SelectSort_Asc(pt_arraylist);    20 //        SelectSort_Desc(pt_arraylist);    21 //        InsertSort(pt_arraylist);22 //        ShellSort(pt_arraylist);23 //        QuickSort(pt_arraylist, 0, pt_arraylist->len-1);24         QuickSort_Opt(pt_arraylist, 0, pt_arraylist->len-1);25         show((char *)"排序后 ", pt_arraylist);26     } 27 28     29     return 0;30 }

測驗頭檔案

 1 //sort.h 2 #define True 1  3 #define False 0 4 #define NUMSIZE 20 5 typedef struct { 6     int array[NUMSIZE]; 7     int len; 8 }ArrayList, *PtArrayList;  9 10 void swap(int * first, int * second);11 void show(char * info, PtArrayList * pt_arraylist); 12 void Init_Data(PtArrayList pt_arraylist); 13 void BubbleSort_Low(PtArrayList * pt_arraylist);14 void BubbleSort_Mid(PtArrayList * pt_arraylist);15 void BubbleSort_Mid_Opt(PtArrayList pt_arraylist);16 void SelectSort_Asc(PtArrayList pt_arraylist);17 void SelectSort_Desc(PtArrayList pt_arraylist);18 void InsertSort(PtArrayList pt_arraylist);19 void ShellSort(PtArrayList pt_arraylist);20 int FindPos(PtArrayList pt_arraylist, int low, int high);21 void QuickSort(PtArrayList pt_arraylist, int low, int high);22 23 #include "sort_function.cpp"

 函式具體實作

  1 //sort_function.cpp  2 void Init_Data(PtArrayList pt_arraylist)  3 {  4     char s[] = "請輸入不大于20的序列長度";  5     printf("%s___\b\b",s);  6     while(!scanf("%d", &pt_arraylist->len) || (pt_arraylist->len > NUMSIZE))  7     {  8         printf("%s\n",s);  9         if(pt_arraylist->len > NUMSIZE) 10         { 11             printf("當前序列長度為%d 過長\n", pt_arraylist->len); 12             continue; 13         } 14         scanf("%*s"); 15     } 16      17     srand(time(0)); //隨機初始化rand()函式 18     for(int i=0; i<pt_arraylist->len; i++) 19     { 20         pt_arraylist->array[i] = rand()%200-100; 21     } 22      23 } 24  25 void QuickSort_Opt(PtArrayList pt_arraylist, int low, int high) 26 { 27     //快速排序--尾遞回優化  28     int pos; 29     while(low<high) 30     { 31         pos = FindPos(pt_arraylist, low, high); 32         QuickSort(pt_arraylist, low, pos-1); 33         low = pos+1;     34     } 35      36 }  37  38 void QuickSort(PtArrayList pt_arraylist, int low, int high) 39 { 40     //快速排序  41     int pos; 42     if(low<high) 43     { 44         pos = FindPos(pt_arraylist, low, high); 45         QuickSort(pt_arraylist, low, pos-1);     46         QuickSort(pt_arraylist, pos+1, high); 47     } 48      49 }  50  51 int FindPos(PtArrayList pt_arraylist, int low, int high) 52 { 53     if (low > NUMSIZE || low<0) 54     { 55         printf("退出,越界訪問\n"); 56         return -1; 57     } 58      59     int posval = pt_arraylist->array[low]; 60     //降序  61     while(low < high) 62     { 63         //確定pos的同時，對序列進行有序化  64         //=不能少,否則可能low和high永遠不能相遇，死回圈  65         while(low < high && posval>=pt_arraylist->array[high]) 66             high--; 67         swap(&pt_arraylist->array[low], &pt_arraylist->array[high]); 68          69         while(low < high && posval<=pt_arraylist->array[low]) 70             low++; 71         swap(&pt_arraylist->array[low], &pt_arraylist->array[high]); 72     } 73      74     return low; 75 } 76  77 void ShellSort(PtArrayList pt_arraylist) 78 { 79     //希爾排序 分組后進行插入排序，分組  80     int i,pos,tmp; 81     int step = pt_arraylist->len; 82  83     do{ 84         step /= 2; //step為1時 和插入排序一模一樣  85         for(i=step; i<pt_arraylist->len; i++) 86         { 87             tmp = pt_arraylist->array[i]; 88             //與當前資料做比較，注意tmp  89             for(pos=i-step; pos>=0 && tmp<pt_arraylist->array[pos];pos-=step) 90             { 91                 pt_arraylist->array[pos+step] = pt_arraylist->array[pos]; 92             } 93             pt_arraylist->array[pos+step] = tmp; 94         } 95          96     }while(step>=1) ; 97  98 } 99 100 void InsertSort(PtArrayList pt_arraylist)101 {102     //直接插入排序 103     int i, pos, tmp;104     for (i=1; i<pt_arraylist->len; i++)105     {106         tmp = pt_arraylist->array[i];//當前值得臨時變數 騰出i位置空間 107         //前一個元素比當前大，右移（升序），必須為pos-- 108         for(pos = i-1; pos>=0 && pt_arraylist->array[pos]>tmp; pos--)109         {110             pt_arraylist->array[pos+1] = pt_arraylist->array[pos]; //右移111         }112         //通過pos標記位置,插入到空出來的位置 （不移動則直接插入到i位置） 113         pt_arraylist->array[pos+1] = tmp;114 115     }116     117 }118 119 void SelectSort_Asc(PtArrayList pt_arraylist)120 {121     //選擇排序，當前數字和其他當中最小的進行交換 (升序)122     int min;123     //最后一個數不用再做比較，所以len-1，其實不加在后續條件也不影響 124     for (int i=0; i<pt_arraylist->len-1; i++)125     {126         min = i;127         for (int j=i+1; j<pt_arraylist->len; j++)128         {129             //此處min不能為i，篩選出最小的值 130             if(pt_arraylist->array[min] > pt_arraylist->array[j]) 131             {132                 min = j;133             }134         } 135     if(i!=min)136         swap(&pt_arraylist->array[i], &pt_arraylist->array[min]);137     } 138 } 139 140 void SelectSort_Desc(PtArrayList pt_arraylist)141 {142     //選擇排序，當前數字和其他當中最大的進行交換 (降序)143     int max;144     for (int i=0; i<pt_arraylist->len-1; i++)145     {146         max = i;147         for (int j=i+1; j<pt_arraylist->len; j++)148         {149             if(pt_arraylist->array[max] < pt_arraylist->array[j]) 150             {151                 max = j;152             }153         } 154     if(i!=max)155         swap(&pt_arraylist->array[i], &pt_arraylist->array[max]);156     } 157 } 158 159 void BubbleSort_Mid_Opt(PtArrayList pt_arraylist)160 {161     int flag = True;    162     //改進版163     for (int i=0; i<pt_arraylist->len && flag; i++)164     {165         //只有當第二層回圈不出現一次True時，166         //才會有標志位False 167         flag = False; 168         for (int j=0; j<pt_arraylist->len-i-1; j++)169         {170             if(pt_arraylist->array[j] > pt_arraylist->array[j+1]) 171             {172                 swap(&pt_arraylist->array[j], &pt_arraylist->array[j+1]);173                 flag = True;174             }175         } 176     } 177 }178 179 void BubbleSort_Mid(PtArrayList pt_arraylist)180 {181     //對當前數字和其下一個相鄰數字比較，大于則交換182     //冒泡到最后一個數肯定是最大的，所以不需要比較，即len-1-i183     //i進行一次表明有i個數字已經排好 184     for (int i=0; i<pt_arraylist->len; i++)185     {186         for (int j=0; j<pt_arraylist->len-i-1; j++)187         {188             if(pt_arraylist->array[j] > pt_arraylist->array[j+1]) 189                 swap(&pt_arraylist->array[j], &pt_arraylist->array[j+1]);190 //            printf("num[%d] = %d num[%d] = %d\n", j, pt_arraylist->array[j], j+1, pt_arraylist->array[j+1]);191         } 192     } 193 }194 195 void BubbleSort_Low(PtArrayList pt_arraylist)196 {197     //依次將數字位與后續其他位比較，升序，大則交換 198     for (int i=0; i<pt_arraylist->len; i++)199     {200         for (int j=i+1; j<pt_arraylist->len; j++)201         {202             if(pt_arraylist->array[i] > pt_arraylist->array[j]) 203                 swap(&pt_arraylist->array[i], &pt_arraylist->array[j]);204         } 205     } 206 }207 208 void show(char info[], PtArrayList pt_arraylist)209 {210     printf("%s", info);211     for (int i=0; i<pt_arraylist->len; i++)212     {213         printf("%3d ", pt_arraylist->array[i]);214     } 215     putchar('\n');    216 }217 218 void swap(int * first, int * second)219 {220     int tmp;221     tmp = *first;222     *first = *second;223     *second = tmp;224     225 }

標籤：C

上一篇：C語言入門-指標

下一篇：C語言入門-字串