데이터 구조 - 기본 정렬 집합

  1 #include <stdio.h>

  2 

  3 #define N 100

  4 

  5 void print1(int a[], int len)

  6 {

  7     int i;

  8 

  9     for(i = 0; i < len; i++)

 10     {

 11         printf("%d ", a[i]);

 12     }

 13 

 14     printf("
");

 15 

 16 }

 17 

 18 void print2(int a[], int len)

 19 {

 20     int i;

 21 

 22     for(i = 1; i <= len; i++)

 23     {

 24         printf("%d ", a[i]);

 25     }

 26 

 27     printf("
");

 28 

 29 }

 30 

 31 int Swap(int *a, int *b)

 32 {



 33     int temp;

 34 

 35     temp = *a;

 36     *a = *b;

 37     *b = temp;

 38 

 39     return 0;

 40 }

 41 

 42 int InsertSort(int a[], int len)

 43 {

 44     int i, j;

 45 

 46     for(i = 1; i < len; i++)

 47     {

 48         for(j = i - 1; j >= 0; j--)

 49         {

 50             if(a[j] > a[j + 1])

 51             {

 52                 Swap(&a[j], &a[j + 1]);

 53             }

 54         }

 55     }

 56 

 57     return 0;

 58 }

 59 

 60 int ShellSort(int a[], int len)

 61 {

 62     int i, j, dt;

 63 

 64     for(dt = len / 2; dt > 0; dt = dt / 2)

 65     {

 66         for(i = dt; i < len; i++)

 67         {

 68             for(j = i - dt; j >= 0; j -= dt)

 69             {

 70                 if(a[j] > a[j + dt])

 71                 {

 72                     Swap(&a[j], &a[j + dt]);

 73                 }

 74             }

 75         }

 76     }

 77 

 78     return 0;

 79 }

 80 

 81 

 82 int SelectSort(int a[], int len)

 83 {

 84     int i, j, min;

 85     

 86     for(i = 0; i < len; i++)

 87     {

 88         min = i;

 89         

 90         for(j = i + 1; j < len; j++)

 91         {

 92             if(a[min] > a[j])

 93             {

 94                 min = j;

 95             }

 96         }

 97 

 98         Swap(&a[min], &a[i]);

 99     }

100 

101     return 0;

102 }

103 

104 int HeapModify(int a[], int i, int len)

105 {

106     int temp = i;

107     int lchild = 2 * i;

108     int rchild = 2 * i + 1;

109 

110     

111     if(a[lchild] > a[temp] && lchild < len)

112     {

113         temp = lchild;

114     }

115 

116     if(a[rchild] > a[temp] && rchild < len)

117     {

118         temp = rchild;            

119     }

120     

121     if(temp != i)

122     {

123         Swap(&a[temp], &a[i]);

124         HeapModify(a, temp, len);

125     }

126 

127     return 0;

128 }

129 

130 

131 int HeapSort(int a[], int len)

132 {

133     int i;

134 

135     for(i = len / 2 - 1; i >= 0; i--)

136     {

137         HeapModify(a, i, len);

138     }

139 

140     for(i = len - 1; i > 0; i--)

141     {

142         Swap(&a[0], &a[i]);

143         HeapModify(a, 0, i);

144 

145         printf("    ：");

146         print1(a, len);

147 

148     }

149     

150 

151     return 0;

152 }

153 

154 int partition(int a[], int low, int high)

155 {

156 

157     int privot = a[low];

158 

159     while(low < high)

160     {

161         while(low < high && a[high] > privot)

162         {

163             high--;

164         }

165 

166         if(low < high)

167         {

168             a[low++] = a[high];

169         }

170 

171         

172 

173         while(low < high && a[low] < privot)

174         {

175             low++;

176         }

177 

178         if(low < high)

179         {

180             a[high--] = a[low];

181         }

182 

183         

184     }

185 

186     a[low] = privot;

187 

188     return low;

189 }

190 

191 int QuickSort(int a[], int low, int high)

192 {

193     int privot;

194 

195     if(low < high)

196     {

197         privot = partition(a, low, high);

198         QuickSort(a, low, privot - 1);

199         QuickSort(a, privot + 1, high);

200     }

201     

202 

203     return 0;

204 }

205 

206 void main()

207 {

208     int a[N];;

209     int i;

210     int len;

211 

212     printf("            ：
");

213     scanf("%d", &len);

214 

215     printf("        ：
");

216     for(i = 0; i < len; i++)

217     {

218         scanf("%d", &a[i]);

219     }

220 

221     printf("    ：
");

222     printf("before:");

223     print1(a, len);

224 

225     

226 //    InsertSort(a, num);

227 //    ShellSort(a, num);

228 //    SelectSort(a, num);

229 //    HeapSort(a, len);

230     QuickSort(a, 0, len - 1);

231 

232     

233     printf("    ：
");

234     printf("after:");

235     print1(a, len);

236 

237 

238 }