C語言，c

C語言，c

1、 快速排序算法

 1 #include<stdio.h>
 2 
 3 struct node
 4 {
 5     int key;
 6 };
 7 typedef struct node DataType;
 8 
 9 int Qukpass_sort(DataType Ar[],int s,int t);
10 int Quk_Sort(DataType Ar[],int s,int t);
11 
12 int main(void)
13 {
14 
15     int n,i;
16     DataType array[20];
17 
18     printf("Input the length of the array <<20>:");
19     scanf("%d",&n);
20     for(i=0; i<n; i++)                 //輸入數組
21     {
22         printf("Input %d datas:",i+1);
23         scanf("%d",&array[i]);
24     }
25 
26 
27     printf("\n The array are:");
28     for(i=0; i<n; i++)
29     {
30         printf("%4d",array[i]);              //輸入的數組顯示
31     }
32 
33     Quk_Sort(array,0,n-1);          //調用排序算法
34 
35 
36     printf("\n The array after quicksort are:");
37     for(i=0; i<n; i++)             //輸出排序後的算法結果
38     {
39         printf("%4d",array[i]);
40 
41     }
42     return(0);
43 }
44 
45 
46 int Quk_Sort(DataType Ar[],int s,int t)       //快速排序算法
47 {
48     int i;
49     if(s<t)
50     {
51         i=Qukpass_sort(Ar,s,t);
52         Quk_Sort(Ar,s,i-1);
53         Quk_Sort(Ar,i+1,t);
54 
55     }
56 }
57 
58 
59 int Qukpass_sort(DataType Ar[],int s,int t)          //快速排序一次劃分算法
60 {
61     DataType temp;
62     int low,high;
63 
64     low=s;                   //low為劃分時序列的左邊界
65     high=t;                  //high為劃分時序列的左邊界
66     temp=Ar[s];              //把中軸值暫存於temp
67     while(low<high)
68     {
69         while((low<high)&&(temp.key<Ar[high].key))         //把大於中軸的排序碼留在右邊的子序列
70             high--;
71         if(Ar[high].key<temp.key)                //把小於或等於中軸的排序碼移到左邊
72         {
73             Ar[low]=Ar[high];
74             low++;
75         }
76         while((low<high)&&(Ar[low].key<=temp.key))    //把小於中軸排序碼移到左邊
77             low++;
78         if(temp.key<Ar[low].key)                     //把大於排序碼移到右邊
79         {
80             Ar[high]=Ar[low];
81             high--;
82         }
83     }
84     Ar[low]=temp;             //把中軸值存入正確的位置
85     return(low);
86 }