各位学长学姐，帮我写几个排序算法吧，对这个不太了解，冒泡排序，和半分查找就不用写了，谢谢啦

选择排序 快速排序 堆排序 希尔排序 归并排序 桶排序。。还有这些排序的n多变种

还有插入排序

好像希尔排序比较高效

很多的。

排序有很多种，如果是初学者，建议先不要去学习。

http://bbs.itheima.com/forum.php ... &extra=page%3D1
看一看这个 也是黑马的学员整理的

Joseph_liuxh 发表于 2015-1-9 16:03
http://bbs.itheima.com/forum.php ... &extra=page%3D1
看一看这个 也是黑马的学员整理的

mark一下

推荐你看算法书，吧各种算法练一练，面试不一定会用，考试不一定会考，工作不一定会用，但至少掌握了算法的思想

希尔排序是最高效的，买一本数据结构的书看看。

1. 
   
2. //插入排序:
   
3. package org.rut.util.algorithm.support;
   
4. import org.rut.util.algorithm.SortUtil;
   
5. public class InsertSort implements SortUtil.Sort{
   
6.     public void sort(int[] data) {
   
7.         int temp;
   
8.         for(int i=1;i<data.length;i++){
   
9.             for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){
   
10.                 SortUtil.swap(data,j,j-1);
    
11.             }
    
12.         }        
    
13.     }
    
14. }
    
15. 
    
16. //选择排序:
    
17. package org.rut.util.algorithm.support;
    
18. import org.rut.util.algorithm.SortUtil;
    
19. public class SelectionSort implements SortUtil.Sort {
    
20.     public void sort(int[] data) {
    
21.         int temp;
    
22.         for (int i = 0; i < data.length; i++) {
    
23.             int lowIndex = i;
    
24.             for (int j = data.length - 1; j > i; j--) {
    
25.                 if (data[j] < data[lowIndex]) {
    
26.                     lowIndex = j;
    
27.                 }
    
28.             }
    
29.             SortUtil.swap(data,i,lowIndex);
    
30.         }
    
31.     }
    
32. }
    
33. //Shell排序:
    
34. package org.rut.util.algorithm.support;
    
35. import org.rut.util.algorithm.SortUtil;
    
36. public class ShellSort implements SortUtil.Sort{
    
37.     public void sort(int[] data) {
    
38.         for(int i=data.length/2;i>2;i/=2){
    
39.             for(int j=0;j<i;j++){
    
40.                 insertSort(data,j,i);
    
41.             }
    
42.         }
    
43.         insertSort(data,0,1);
    
44.     }
    
45.     private void insertSort(int[] data, int start, int inc) {
    
46.         int temp;
    
47.         for(int i=start+inc;i<data.length;i+=inc){
    
48.             for(int j=i;(j>=inc)&&(data[j]<data[j-inc]);j-=inc){
    
49.                 SortUtil.swap(data,j,j-inc);
    
50.             }
    
51.         }
    
52.     }
    
53. }
    
54. //快速排序:
    
55. package org.rut.util.algorithm.support;
    
56. import org.rut.util.algorithm.SortUtil;
    
57. public class QuickSort implements SortUtil.Sort{
    
58.     public void sort(int[] data) {
    
59.         quickSort(data,0,data.length-1);        
    
60.     }
    
61.     private void quickSort(int[] data,int i,int j){
    
62.         int pivotIndex=(i+j)/2;
    
63.         //swap
    
64.         SortUtil.swap(data,pivotIndex,j);
    
65.         int k=partition(data,i-1,j,data[j]);
    
66.         SortUtil.swap(data,k,j);
    
67.         if((k-i)>1) quickSort(data,i,k-1);
    
68.         if((j-k)>1) quickSort(data,k+1,j);
    
69.     }
    
70.     private int partition(int[] data, int l, int r,int pivot) {
    
71.         do{
    
72.            while(data[++l]<pivot);
    
73.            while((r!=0)&&data[--r]>pivot);
    
74.            SortUtil.swap(data,l,r);
    
75.         }
    
76.         while(l<r);
    
77.         SortUtil.swap(data,l,r);        
    
78.         return l;
    
79.     }
    
80. }
    
81. //改进后的快速排序:
    
82. package org.rut.util.algorithm.support;
    
83. import org.rut.util.algorithm.SortUtil;
    
84. public class ImprovedQuickSort implements SortUtil.Sort {
    
85.     private static int MAX_STACK_SIZE=4096;
    
86.     private static int THRESHOLD=10;
    
87.     public void sort(int[] data) {
    
88.         int[] stack=new int[MAX_STACK_SIZE];
    
89.         int top=-1;
    
90.         int pivot;
    
91.         int pivotIndex,l,r;
    
92.         stack[++top]=0;
    
93.         stack[++top]=data.length-1;
    
94.         while(top>0){
    
95.             int j=stack[top--];
    
96.             int i=stack[top--];
    
97.             pivotIndex=(i+j)/2;
    
98.             pivot=data[pivotIndex];
    
99.             SortUtil.swap(data,pivotIndex,j);
    
100.             //partition
     
101.             l=i-1;
     
102.             r=j;
     
103.             do{
     
104.                 while(data[++l]<pivot);
     
105.                 while((r!=0)&&(data[--r]>pivot));
     
106.                 SortUtil.swap(data,l,r);
     
107.             }
     
108.             while(l<r);
     
109.             SortUtil.swap(data,l,r);
     
110.             SortUtil.swap(data,l,j);
     
111.             if((l-i)>THRESHOLD){
     
112.                 stack[++top]=i;
     
113.                 stack[++top]=l-1;
     
114.             }
     
115.             if((j-l)>THRESHOLD){
     
116.                 stack[++top]=l+1;
     
117.                 stack[++top]=j;
     
118.             }
     
119.         }
     
120.         //new InsertSort().sort(data);
     
121.         insertSort(data);
     
122.     }
     
123.     private void insertSort(int[] data) {
     
124.         int temp;
     
125.         for(int i=1;i<data.length;i++){
     
126.             for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){
     
127.                 SortUtil.swap(data,j,j-1);
     
128.             }
     
129.         }      
     
130.     }
     
131. }
     
132. 
     
133. //归并排序:
     
134. package org.rut.util.algorithm.support;
     
135. import org.rut.util.algorithm.SortUtil;
     
136. public class MergeSort implements SortUtil.Sort{
     
137.     public void sort(int[] data) {
     
138.         int[] temp=new int[data.length];
     
139.         mergeSort(data,temp,0,data.length-1);
     
140.     }
     
141.     private void mergeSort(int[] data,int[] temp,int l,int r){
     
142.         int mid=(l+r)/2;
     
143.         if(l==r) return ;
     
144.         mergeSort(data,temp,l,mid);
     
145.         mergeSort(data,temp,mid+1,r);
     
146.         for(int i=l;i<=r;i++){
     
147.             temp[i]=data[i];
     
148.         }
     
149.         int i1=l;
     
150.         int i2=mid+1;
     
151.         for(int cur=l;cur<=r;cur++){
     
152.             if(i1==mid+1)
     
153.                 data[cur]=temp[i2++];
     
154.             else if(i2>r)
     
155.                 data[cur]=temp[i1++];
     
156.             else if(temp[i1]<temp[i2])
     
157.                 data[cur]=temp[i1++];
     
158.             else
     
159.                 data[cur]=temp[i2++];            
     
160.         }
     
161.     }
     
162. }
     
163. //改进后的归并排序:
     
164. package org.rut.util.algorithm.support;
     
165. import org.rut.util.algorithm.SortUtil;
     
166. public class ImprovedMergeSort implements SortUtil.Sort {
     
167.     private static final int THRESHOLD = 10;
     
168.     public void sort(int[] data) {
     
169.         int[] temp=new int[data.length];
     
170.         mergeSort(data,temp,0,data.length-1);
     
171.     }
     
172.     private void mergeSort(int[] data, int[] temp, int l, int r) {
     
173.         int i, j, k;
     
174.         int mid = (l + r) / 2;
     
175.         if (l == r)
     
176.             return;
     
177.         if ((mid - l) >= THRESHOLD)
     
178.             mergeSort(data, temp, l, mid);
     
179.         else
     
180.             insertSort(data, l, mid - l + 1);
     
181.         if ((r - mid) > THRESHOLD)
     
182.             mergeSort(data, temp, mid + 1, r);
     
183.         else
     
184.             insertSort(data, mid + 1, r - mid);
     
185.         for (i = l; i <= mid; i++) {
     
186.             temp[i] = data[i];
     
187.         }
     
188.         for (j = 1; j <= r - mid; j++) {
     
189.             temp[r - j + 1] = data[j + mid];
     
190.         }
     
191.         int a = temp[l];
     
192.         int b = temp[r];
     
193.         for (i = l, j = r, k = l; k <= r; k++) {
     
194.             if (a < b) {
     
195.                 data[k] = temp[i++];
     
196.                 a = temp[i];
     
197.             } else {
     
198.                 data[k] = temp[j--];
     
199.                 b = temp[j];
     
200.             }
     
201.         }
     
202.     }
     
203.     private void insertSort(int[] data, int start, int len) {
     
204.         for(int i=start+1;i<start+len;i++){
     
205.             for(int j=i;(j>start) && data[j]<data[j-1];j--){
     
206.                 SortUtil.swap(data,j,j-1);
     
207.             }
     
208.         }
     
209.     }
     
210. }
     
211. //堆排序:
     
212. package org.rut.util.algorithm.support;
     
213. import org.rut.util.algorithm.SortUtil;
     
214. public class HeapSort implements SortUtil.Sort{
     
215.     public void sort(int[] data) {
     
216.         MaxHeap h=new MaxHeap();
     
217.         h.init(data);
     
218.         for(int i=0;i<data.length;i++)
     
219.             h.remove();
     
220.         System.arraycopy(h.queue,1,data,0,data.length);
     
221.     }
     
222.      private static class MaxHeap{
     
223.         void init(int[] data){
     
224.             this.queue=new int[data.length+1];
     
225.             for(int i=0;i<data.length;i++){
     
226.                 queue[++size]=data[i];
     
227.                 fixUp(size);
     
228.             }
     
229.         }
     
230.         private int size=0;
     
231.         private int[] queue;
     
232.         public int get() {
     
233.             return queue[1];
     
234.         }
     
235.         public void remove() {
     
236.             SortUtil.swap(queue,1,size--);
     
237.             fixDown(1);
     
238.         }
     
239.         //fixdown
     
240.         private void fixDown(int k) {
     
241.             int j;
     
242.             while ((j = k << 1) <= size) {
     
243.                 if (j < size && queue[j]<queue[j+1])
     
244.                     j++;
     
245.                 if (queue[k]>queue[j]) //不用交换
     
246.                     break;
     
247.                 SortUtil.swap(queue,j,k);
     
248.                 k = j;
     
249.             }
     
250.         }
     
251.         private void fixUp(int k) {
     
252.             while (k > 1) {
     
253.                 int j = k >> 1;
     
254.                 if (queue[j]>queue[k])
     
255.                     break;
     
256.                 SortUtil.swap(queue,j,k);
     
257.                 k = j;
     
258.             }
     
259.         }
     
260.     }
     
261. }
     
262. //SortUtil:
     
263. package org.rut.util.algorithm;
     
264. import org.rut.util.algorithm.support.BubbleSort;
     
265. import org.rut.util.algorithm.support.HeapSort;
     
266. import org.rut.util.algorithm.support.ImprovedMergeSort;
     
267. import org.rut.util.algorithm.support.ImprovedQuickSort;
     
268. import org.rut.util.algorithm.support.InsertSort;
     
269. import org.rut.util.algorithm.support.MergeSort;
     
270. import org.rut.util.algorithm.support.QuickSort;
     
271. import org.rut.util.algorithm.support.SelectionSort;
     
272. import org.rut.util.algorithm.support.ShellSort;
     
273. public class SortUtil {
     
274.     public final static int INSERT = 1;
     
275.     public final static int BUBBLE = 2;
     
276.     public final static int SELECTION = 3;
     
277.     public final static int SHELL = 4;
     
278.     public final static int QUICK = 5;
     
279.     public final static int IMPROVED_QUICK = 6;
     
280.     public final static int MERGE = 7;
     
281.     public final static int IMPROVED_MERGE = 8;
     
282.     public final static int HEAP = 9;
     
283.     public static void sort(int[] data) {
     
284.         sort(data, IMPROVED_QUICK);
     
285.     }
     
286.     private static String[] name={
     
287.             "insert","bubble","selection","shell","quick","improved_quick","merge","improved_merge","heap"
     
288.     };
     
289.     private static Sort[] impl=new Sort[]{
     
290.             new InsertSort(),
     
291.             new BubbleSort(),
     
292.             new SelectionSort(),
     
293.             new ShellSort(),
     
294.             new QuickSort(),
     
295.             new ImprovedQuickSort(),
     
296.             new MergeSort(),
     
297.             new ImprovedMergeSort(),
     
298.             new HeapSort()
     
299.     };
     
300.     public static String toString(int algorithm){
     
301.         return name[algorithm-1];
     
302.     }
     
303.     public static void sort(int[] data, int algorithm) {
     
304.         impl[algorithm-1].sort(data);
     
305.     }
     
306.     public static interface Sort {
     
307.         public void sort(int[] data);
     
308.     }
     
309.     public static void swap(int[] data, int i, int j) {
     
310.         int temp = data[i];
     
311.         data[i] = data[j];
     
312.         data[j] = temp;
     
313.     }
     
314. }

复制代码

这些算法网上很多的，诸如CSDN。