各种数组排序方法总结(转载)

                             各种数组排序方法总结(java)

 

 import java.lang.Math;  

1. import java.util.Random;  
2.   
3. /** 
4.  * 排序 
5.  *  
6.  * @author javajack   
7.  */  
8. public class OrderTest {  
9.   
10.     public static void main(String args[]) {  
11.         OrderTest.ExecOrder(2);  
12.     }  
13.   
14.     /** 
15.      * 交换值，交换数组的两个值 
16.      * @param array 
17.      * @param i 
18.      * @param j 
19.      */  
20.     private static void swap(int[] array,int i, int j)  
21.     {  
22.         int tmp = array[i];  
23.         array[i] = array[j];  
24.         array[j] = tmp;  
25.     }     
26.       
27.     /** 
28.      *  
29.      * @param method 
30.      *            1为升序，2为降序 
31.      */  
32.     public static void ExecOrder(int method) {  
33.         int[] array = null;  
34.         array = initArray(10, 210, 10);  
35.           
36.          //int[] orderarray = bubbleOrder(array,method);  
37.         int[] orderarray = doubleBubbleOrder(array,method);  
38.         //int[] orderarray = insertOrder(array, method);  
39.         //int [] orderarray = quickOrder(array,method);  
40.         //int[] orderarray = selectOrder(array, method);  
41.         for (int i = 0; i < orderarray.length; i++) {  
42.             System.out.println(orderarray[i]);  
43.         }  
44.     }  
45.   
46.     /** 
47.      * 取随机数据，初始化一个数组 
48.      *  
49.      * @param min 
50.      *            随机数的最小值 
51.      * @param max 
52.      *            最大值 
53.      * @param size 
54.      *            取得随机数的数量 
55.      * @return 
56.      */  
57.     public static int[] initArray(int min, int max, int size) {  
58.         int[] init = new int[size];  
59.   
60.         for (int i = 0; i < size; i++) {  
61.             Random ra = new Random();  
62.             init[i] = min + (int) (Math.random() * (max - min + 1));  
63.             System.out.println(i + "-------" + init[i]);  
64.         }  
65.         return init;  
66.     }  
67.   
68.     /** 
69.      * 交换排序方法 
70.      * 原理：依次交换值 
71.      * @param array 
72.      * @return 
73.      */  
74.     public static int[] convertOrder(int[] array, int method) {  
75.         for (int i = 0; i < array.length; i++) {  
76.             for (int j = i + 1; j < array.length; j++)   
77.             {  
78.                 if (method==2)  
79.                 {  
80.                     if (array[i] < array[j])   
81.                         swap(array,i,j);  
82.                 }else if (method == 1) {  
83.                     if (array[i] > array[j])   
84.                         swap(array,i,j);  
85.                 }  
86.             }  
87.         }  
88.         return array;  
89.     }  
90.   
91.     /**冒泡排序方法 
92.      * 原理：从最后一个开始将小的或大的逐渐冒出 
93.      * @param array 
94.      * @param method 
95.      * @return 
96.      */  
97.     public static int[] bubbleOrder(int[] array,int method)  
98.     {  
99.         for(int i=0;i
100.         {  
101.             for (int j=array.length -1 ;j>i;j--)  
102.             {  
103.                 if (method==2)  
104.                 {  
105.                     if (array[i] < array[j])  
106.                         swap(array,i,j);  
107.                 }else if (method==1)  
108.                     if (array[i] > array[j])  
109.                         swap(array,i,j);  
110.             }  
111.         }  
112.         return array;  
113.     }  
114.       
115.     /** 
116.      * 双向冒泡排序 
117.      * 原理：类似于冒泡排序，只不过是双向的 
118.      * @param array 
119.      * @param method 
120.      * @return 
121.      */  
122.     public static int[] doubleBubbleOrder(int[] array,int method)  
123.     {  
124.         int left = 0;  
125.         int right = array.length -1 ;  
126.         while (left < right)  
127.         {  
128.             for(int i=left;i<=right;i++)  
129.             {  
130.                 if (method==1)  
131.                 {  
132.                     if (array[left] > array[i])  
133.                         swap(array,left,i);  
134.                 }else  
135.                 {  
136.                     if (array[left] < array[i])  
137.                         swap(array,left,i);  
138.                 }  
139.             }  
140.               
141.             for (int i=left+1;i<=right;i++)  
142.             {  
143.                 if (method==1)  
144.                 {  
145.                     if (array[right] < array[i])  
146.                         swap(array,right,i);  
147.                 }else  
148.                 {  
149.                     if (array[right] > array[i])  
150.                         swap(array,right,i);  
151.                       
152.                 }  
153.             }  
154.             left++;  
155.             right--;  
156.         }  
157.         return array;  
158.     }  
159.       
160.     /** 
161.      * 快速排序方法，运用到递归 
162.      * 排序原理：随机找到一个值，然后以此值大小进行分为两个数组，大的放左边，小的放右边， 
163.      * 然后再对左右两侧的数据依次排序根据 
164.      * @param array 
165.      * @param method 
166.      * @return 
167.      */  
168.     public static int[] quickOrder(int[] array, int method)   
169.     {  
170.         quickDeal(array,0,array.length - 1,method);  
171.         return array;  
172.     }  
173.   
174.     /** 
175.      *  
176.      * @param array 
177.      * @param begin 
178.      *            开始位置 
179.      * @param end 
180.      *            结束位置 
181.      */  
182.     private static void quickDeal(int[] array, int begin, int end,int method) {  
183.         if (end > begin) {  
184.             int pos = begin + (int) (Math.random() * (end - begin + 1)); // 计算分隔位置  
185.             int posvalue = array[pos]; // 取得分隔位置的值  
186.             swap(array,pos,end); //将posvalue放到最end的位置  
187.             pos=begin; //初始化pos  
188.             for (int i=begin; i < end; i++) {  
189.                 if (method==1)  
190.                 {     
191.                     if (array[i] < posvalue) { //当小于posvalue时，将此值移动到pos位置，也就是向前移动  
192.                         swap(array,pos,i);   
193.                         pos++; //移动后pos增1  
194.                     }  
195.                 }else if(method == 2)  
196.                 {  
197.                     if (array[i] > posvalue) { //当小于posvalue时，将此值移动到pos位置，也就是向前移动  
198.                         swap(array,pos,i);   
199.                         pos++; //移动后pos增1  
200.                     }  
201.                 }  
202.             }  
203.             swap(array,pos,end); //end位置的值前移  
204.             quickDeal(array,begin,pos -1,method);  
205.             quickDeal(array,pos+1,end,method);  
206.         }  
207.   
208.     }  
209.   
210.     /** 
211.      * 插入排序方法 
212.      * 排序原理：抽出一个数，做为排序基序列，然后依次抽出其它数与，与此序列中的数进行比较，放入合适的位置 
213.      * @param array 
214.      * @param method 
215.      * @return 
216.      */  
217.     public static int[] insertOrder(int[] array, int method) {  
218.   
219.         for (int i = 1; i < array.length; i++) {  
220.             if (method == 1) {  
221.                 if (array[i - 1] > array[i]) {  
222.                     int tmp = array[i]; //  
223.                     int j = i - 1;  
224.                     do {  
225.                         array[j + 1] = array[j];  
226.                         j--;  
227.                     } while (j >= 0 && tmp < array[j]); //当j>=0并且 当前值大于数据中j位置的值时移动  
228.                     array[j + 1] = tmp; //插入排序值  
229.                 }  
230.             } else if (method == 2) {  
231.                 if (array[i - 1] < array[i]) {  
232.                     int tmp = array[i];   
233.                     int j = i - 1;  
234.                     do {  
235.                         array[j + 1] = array[j];  
236.                         j--;  
237.                     } while (j >= 0 && tmp > array[j]);  
238.                     array[j + 1] = tmp;  
239.                 }  
240.             }  
241.         }  
242.         return array;  
243.     }  
244.   
245.     /** 
246.      * 选择排序方法 
247.      * 排序原理：每次选择一个最大的或最小的数放到已排序序列中 
248.      * @param array 
249.      * @param method 
250.      * @return 
251.      */  
252.     public static int[] selectOrder(int[] array,int method)  
253.     {  
254.         for (int i=0;i1;i++)   
255.         {  
256.             int tmp = array[i];  
257.             int pos = i+1; //记录大值或小值的位置　  
258.             for (int j=i+1;j
259.             {  
260.                 if (method==1)  
261.                 {  
262.                     if (array[j]
263.                     {  
264.                         tmp = array[j];  
265.                         pos= j ;//记录大值或小值的位置  
266.                     }  
267.                 }else if (method==2)  
268.                 {  
269.                     if (array[j]>tmp)  
270.                     {  
271.                         tmp = array[j];  
272.                         pos= j ;//记录大值或小值的位置  
273.                     }  
274.                 }  
275.             }  
276.             if (tmp != array[i])  
277.                 swap(array,i,pos); //不相同时交换  
278.         }  
279.         return array;  
280.     }  
281.   
282.       
283. }