Java中各种排序算法

//插入排序: 

002   

003 package org.rut.util.algorithm.support; 

004   

005 import org.rut.util.algorithm.SortUtil; 

006 /** 

007  * @author treeroot 

008  * @since 2006-2-2 

009  * @version 1.0 

010  */

011 public class InsertSort implements SortUtil.Sort{ 

012   

013     /** (non-Javadoc) 

014      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[]) 

015      */

016     public void sort(int[] data) { 

017         int temp; 

018         for(int i=1;i<data.length;i++){ 

019             for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){ 

020                 SortUtil.swap(data,j,j-1); 

021             } 

022         }         

023     } 

024   

025 } 

026 //冒泡排序: 

027   

028   

029 for(var i=0; i<arr.length; i++) {     

030     for(var j=i+1; j<=arr.length-1; j++) { 

031         if(eval(arr[i]) < eval(arr[j])) {         

032             temp = arr[i];                       

033             arr[i] = arr[j];                         

034             arr[j] = temp;                                               

035         } 

036     } 

037 } 

038   

039   

040   

041 package org.rut.util.algorithm.support; 

042   

043 import org.rut.util.algorithm.SortUtil; 

044   

045 /** 

046  * @author treeroot 

047  * @since 2006-2-2 

048  * @version 1.0 

049  */

050 public class BubbleSort implements SortUtil.Sort{ 

051   

052     /** (non-Javadoc) 

053      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[]) 

054      */

055     public void sort(int[] data) { 

056         int temp; 

057         for(int i=0;i<data.length;i++){ 

058             for(int j=data.length-1;j>i;j--){ 

059                 if(data[j]<data[j-1]){ 

060                     SortUtil.swap(data,j,j-1); 

061                 } 

062             } 

063         } 

064     } 

065   

066 } 

067   

068 //选择排序: 

069   

070 package org.rut.util.algorithm.support; 

071   

072 import org.rut.util.algorithm.SortUtil; 

073   

074 /** 

075  * @author treeroot 

076  * @since 2006-2-2 

077  * @version 1.0 

078  */

079 public class SelectionSort implements SortUtil.Sort { 

080   

081     /** 

082      * (non-Javadoc) 

083      *  

084      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[]) 

085      */

086     public void sort(int[] data) { 

087         int temp; 

088         for (int i = 0; i < data.length; i++) { 

089             int lowIndex = i; 

090             for (int j = data.length - 1; j > i; j--) { 

091                 if (data[j] < data[lowIndex]) { 

092                     lowIndex = j; 

093                 } 

094             } 

095             SortUtil.swap(data,i,lowIndex); 

096         } 

097     } 

098   

099 } 

100   

101 //Shell排序: 

102   

103 package org.rut.util.algorithm.support; 

104   

105 import org.rut.util.algorithm.SortUtil; 

106   

107 /** 

108  * @author treeroot 

109  * @since 2006-2-2 

110  * @version 1.0 

111  */

112 public class ShellSort implements SortUtil.Sort{ 

113   

114     /** (non-Javadoc) 

115      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[]) 

116      */

117     public void sort(int[] data) { 

118         for(int i=data.length/2;i>2;i/=2){ 

119             for(int j=0;j<i;j++){ 

120                 insertSort(data,j,i); 

121             } 

122         } 

123         insertSort(data,0,1); 

124     } 

125   

126     /** 

127      * @param data 

128      * @param j 

129      * @param i 

130      */

131     private void insertSort(int[] data, int start, int inc) { 

132         int temp; 

133         for(int i=start+inc;i<data.length;i+=inc){ 

134             for(int j=i;(j>=inc)&&(data[j]<data[j-inc]);j-=inc){ 

135                 SortUtil.swap(data,j,j-inc); 

136             } 

137         } 

138     } 

139   

140 } 

141   

142 //快速排序: 

143   

144 package org.rut.util.algorithm.support; 

145   

146 import org.rut.util.algorithm.SortUtil; 

147   

148 /** 

149  * @author treeroot 

150  * @since 2006-2-2 

151  * @version 1.0 

152  */

153 public class QuickSort implements SortUtil.Sort{ 

154   

155     /** (non-Javadoc) 

156      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[]) 

157      */

158     public void sort(int[] data) { 

159         quickSort(data,0,data.length-1);         

160     } 

161     private void quickSort(int[] data,int i,int j){ 

162         int pivotIndex=(i+j)/2; 

163         //swap 

164         SortUtil.swap(data,pivotIndex,j); 

165           

166         int k=partition(data,i-1,j,data[j]); 

167         SortUtil.swap(data,k,j); 

168         if((k-i)>1) quickSort(data,i,k-1); 

169         if((j-k)>1) quickSort(data,k+1,j); 

170           

171     } 

172     /** 

173      * @param data 

174      * @param i 

175      * @param j 

176      * @return 

177      */

178     private int partition(int[] data, int l, int r,int pivot) { 

179         do{ 

180            while(data[++l]<pivot); 

181            while((r!=0)&&data[--r]>pivot); 

182            SortUtil.swap(data,l,r); 

183         } 

184         while(l<r); 

185         SortUtil.swap(data,l,r);         

186         return l; 

187     } 

188   

189 } 

190 //改进后的快速排序: 

191   

192 package org.rut.util.algorithm.support; 

193   

194 import org.rut.util.algorithm.SortUtil; 

195   

196 /** 

197  * @author treeroot 

198  * @since 2006-2-2 

199  * @version 1.0 

200  */

201 public class ImprovedQuickSort implements SortUtil.Sort { 

202   

203     private static int MAX_STACK_SIZE=4096; 

204     private static int THRESHOLD=10; 

205     /** (non-Javadoc) 

206      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[]) 

207      */

208     public void sort(int[] data) { 

209         int[] stack=new int[MAX_STACK_SIZE]; 

210           

211         int top=-1; 

212         int pivot; 

213         int pivotIndex,l,r; 

214           

215         stack[++top]=0; 

216         stack[++top]=data.length-1; 

217           

218         while(top>0){ 

219             int j=stack[top--]; 

220             int i=stack[top--]; 

221               

222             pivotIndex=(i+j)/2; 

223             pivot=data[pivotIndex]; 

224               

225             SortUtil.swap(data,pivotIndex,j); 

226               

227             //partition 

228             l=i-1; 

229             r=j; 

230             do{ 

231                 while(data[++l]<pivot); 

232                 while((r!=0)&&(data[--r]>pivot)); 

233                 SortUtil.swap(data,l,r); 

234             } 

235             while(l<r); 

236             SortUtil.swap(data,l,r); 

237             SortUtil.swap(data,l,j); 

238               

239             if((l-i)>THRESHOLD){ 

240                 stack[++top]=i; 

241                 stack[++top]=l-1; 

242             } 

243             if((j-l)>THRESHOLD){ 

244                 stack[++top]=l+1; 

245                 stack[++top]=j; 

246             } 

247               

248         } 

249         //new InsertSort().sort(data); 

250         insertSort(data); 

251     } 

252     /** 

253      * @param data 

254      */

255     private void insertSort(int[] data) { 

256         int temp; 

257         for(int i=1;i<data.length;i++){ 

258             for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){ 

259                 SortUtil.swap(data,j,j-1); 

260             } 

261         }        

262     } 

263   

264 } 

265   

266 //归并排序: 

267   

268 package org.rut.util.algorithm.support; 

269   

270 import org.rut.util.algorithm.SortUtil; 

271   

272 /** 

273  * @author treeroot 

274  * @since 2006-2-2 

275  * @version 1.0 

276  */

277 public class MergeSort implements SortUtil.Sort{ 

278   

279     /** (non-Javadoc) 

280      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[]) 

281      */

282     public void sort(int[] data) { 

283         int[] temp=new int[data.length]; 

284         mergeSort(data,temp,0,data.length-1); 

285     } 

286       

287     private void mergeSort(int[] data,int[] temp,int l,int r){ 

288         int mid=(l+r)/2; 

289         if(l==r) return ; 

290         mergeSort(data,temp,l,mid); 

291         mergeSort(data,temp,mid+1,r); 

292         for(int i=l;i<=r;i++){ 

293             temp[i]=data[i]; 

294         } 

295         int i1=l; 

296         int i2=mid+1; 

297         for(int cur=l;cur<=r;cur++){ 

298             if(i1==mid+1) 

299                 data[cur]=temp[i2++]; 

300             else if(i2>r) 

301                 data[cur]=temp[i1++]; 

302             else if(temp[i1]<temp[i2]) 

303                 data[cur]=temp[i1++]; 

304             else

305                 data[cur]=temp[i2++];             

306         } 

307     } 

308   

309 } 

310   

311 //改进后的归并排序: 

312   

313 package org.rut.util.algorithm.support; 

314   

315 import org.rut.util.algorithm.SortUtil; 

316   

317 /** 

318  * @author treeroot 

319  * @since 2006-2-2 

320  * @version 1.0 

321  */

322 public class ImprovedMergeSort implements SortUtil.Sort { 

323   

324     private static final int THRESHOLD = 10; 

325   

326     /** 

327      * (non-Javadoc) 

328      *  

329      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[]) 

330      */

331     public void sort(int[] data) { 

332         int[] temp=new int[data.length]; 

333         mergeSort(data,temp,0,data.length-1); 

334     } 

335   

336     private void mergeSort(int[] data, int[] temp, int l, int r) { 

337         int i, j, k; 

338         int mid = (l + r) / 2; 

339         if (l == r) 

340             return; 

341         if ((mid - l) >= THRESHOLD) 

342             mergeSort(data, temp, l, mid); 

343         else

344             insertSort(data, l, mid - l + 1); 

345         if ((r - mid) > THRESHOLD) 

346             mergeSort(data, temp, mid + 1, r); 

347         else

348             insertSort(data, mid + 1, r - mid); 

349   

350         for (i = l; i <= mid; i++) { 

351             temp[i] = data[i]; 

352         } 

353         for (j = 1; j <= r - mid; j++) { 

354             temp[r - j + 1] = data[j + mid]; 

355         } 

356         int a = temp[l]; 

357         int b = temp[r]; 

358         for (i = l, j = r, k = l; k <= r; k++) { 

359             if (a < b) { 

360                 data[k] = temp[i++]; 

361                 a = temp[i]; 

362             } else { 

363                 data[k] = temp[j--]; 

364                 b = temp[j]; 

365             } 

366         } 

367     } 

368   

369     /** 

370      * @param data 

371      * @param l 

372      * @param i 

373      */

374     private void insertSort(int[] data, int start, int len) { 

375         for(int i=start+1;i<start+len;i++){ 

376             for(int j=i;(j>start) && data[j]<data[j-1];j--){ 

377                 SortUtil.swap(data,j,j-1); 

378             } 

379         } 

380     } 

381   

382 } 

383 //堆排序: 

384   

385 package org.rut.util.algorithm.support; 

386   

387 import org.rut.util.algorithm.SortUtil; 

388   

389 /** 

390  * @author treeroot 

391  * @since 2006-2-2 

392  * @version 1.0 

393  */

394 public class HeapSort implements SortUtil.Sort{ 

395   

396     /** (non-Javadoc) 

397      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[]) 

398      */

399     public void sort(int[] data) { 

400         MaxHeap h=new MaxHeap(); 

401         h.init(data); 

402         for(int i=0;i<data.length;i++) 

403             h.remove(); 

404         System.arraycopy(h.queue,1,data,0,data.length); 

405     } 

406   

407   

408      private static class MaxHeap{ 

409            

410           

411         void init(int[] data){ 

412             this.queue=new int[data.length+1]; 

413             for(int i=0;i<data.length;i++){ 

414                 queue[++size]=data[i]; 

415                 fixUp(size); 

416             } 

417         } 

418            

419         private int size=0; 

420   

421         private int[] queue; 

422                   

423         public int get() { 

424             return queue[1]; 

425         } 

426   

427         public void remove() { 

428             SortUtil.swap(queue,1,size--); 

429             fixDown(1); 

430         } 

431         //fixdown 

432         private void fixDown(int k) { 

433             int j; 

434             while ((j = k << 1) <= size) { 

435                 if (j < size && queue[j]<queue[j+1]) 

436                     j++;  

437                 if (queue[k]>queue[j]) //不用交换 

438                     break; 

439                 SortUtil.swap(queue,j,k); 

440                 k = j; 

441             } 

442         } 

443         private void fixUp(int k) { 

444             while (k > 1) { 

445                 int j = k >> 1; 

446                 if (queue[j]>queue[k]) 

447                     break; 

448                 SortUtil.swap(queue,j,k); 

449                 k = j; 

450             } 

451         } 

452   

453     } 

454   

455 } 

456   

457    

458   

459 //SortUtil: 

460   

461 package org.rut.util.algorithm; 

462   

463 import org.rut.util.algorithm.support.BubbleSort; 

464 import org.rut.util.algorithm.support.HeapSort; 

465 import org.rut.util.algorithm.support.ImprovedMergeSort; 

466 import org.rut.util.algorithm.support.ImprovedQuickSort; 

467 import org.rut.util.algorithm.support.InsertSort; 

468 import org.rut.util.algorithm.support.MergeSort; 

469 import org.rut.util.algorithm.support.QuickSort; 

470 import org.rut.util.algorithm.support.SelectionSort; 

471 import org.rut.util.algorithm.support.ShellSort; 

472   

473 /** 

474  * @author treeroot 

475  * @since 2006-2-2 

476  * @version 1.0 

477  */

478 public class SortUtil { 

479     public final static int INSERT = 1; 

480   

481     public final static int BUBBLE = 2; 

482   

483     public final static int SELECTION = 3; 

484   

485     public final static int SHELL = 4; 

486   

487     public final static int QUICK = 5; 

488   

489     public final static int IMPROVED_QUICK = 6; 

490   

491     public final static int MERGE = 7; 

492   

493     public final static int IMPROVED_MERGE = 8; 

494   

495     public final static int HEAP = 9; 

496   

497     public static void sort(int[] data) { 

498         sort(data, IMPROVED_QUICK); 

499     } 

500     private static String[] name={ 

501             "insert","bubble","selection","shell","quick","improved_quick","merge","improved_merge","heap"

502     }; 

503       

504     private static Sort[] impl=new Sort[]{ 

505             new InsertSort(), 

506             new BubbleSort(), 

507             new SelectionSort(), 

508             new ShellSort(), 

509             new QuickSort(), 

510             new ImprovedQuickSort(), 

511             new MergeSort(), 

512             new ImprovedMergeSort(), 

513             new HeapSort() 

514     }; 

515   

516     public static String toString(int algorithm){ 

517         return name[algorithm-1]; 

518     } 

519       

520     public static void sort(int[] data, int algorithm) { 

521         impl[algorithm-1].sort(data); 

522     } 

523   

524     public static interface Sort { 

525         public void sort(int[] data); 

526     } 

527   

528     public static void swap(int[] data, int i, int j) { 

529         int temp = data[i]; 

530         data[i] = data[j]; 

531         data[j] = temp; 

532     } 

533 }