001 import java.util.ArrayList;
002 import java.util.Arrays;
003 import java.util.Collections;
004 import java.util.List;
005
006 /**
007 * 排序算法
008 * 使用三个：numberSort        stringSort        chineseSort
009 * @author KyLinD http://hi.baidu.com/kylind
010 *
011 */
012 public class SortingAlgorithm {
013     /**
014      * 数字进行排序，使用的选择排序
015      * @param data 待处理数组
016      * @param asc 是否升序
017      * @return 排列好的数组
018      */
019     public static long[] numberSort(long[] data , boolean asc){
020         if(data == null || data.length ==0)
021             return null;       
022         return selectSort(data,asc);
023     }
024     /**
025      * 冒泡排序算法
026      * 说明：相邻的比较，符合条件就调换，每次排好一个剩余的最小/最大数
027      * @param data 待排序的数组
028      * @param asc 是否升序
029      * @return 排序后的数组
030      */
031     protected static long[] bubbleSort(long[] data , boolean asc){
032         for(int i=0 ; i<data.length ; i++)
033             for(int j=data.length-1 ; j>i ; j--)
034                 if(asc){
035                     if(data[j] < data[j-1])
036                         swap(data,j,j-1);
037                 }else{
038                     if(data[j] > data[j-1])
039                         swap(data,j,j-1);
040                 }
041         return data;
042     }
043     /**
044      * 插入排序算法
045      * 说明：经过的数字都已经排好序，每次循环增加一个
046      * @param data 待排序的数组
047      * @param asc 是否升序
048      * @return 排序后的数组
049      */
050     protected static long[] insertSort(long[] data , boolean asc){
051         return insertSortDo(data,0,data.length-1,asc);
052     }
053    
054     /**
055      * 选择排序算法
056      * 说明：查找剩余的最小/最大数排到前面位置
057      * @param data 待排序的数组
058      * @param asc 是否升序
059      * @return 排序后的数组
060      */
061     protected static long[] selectSort(long[] data , boolean asc){
062         for(int i=0 ; i<data.length ; i++){
063             int lowIndex = i;
064             for(int j=data.length-1 ; j>i ; j--){
065                 if(asc){
066                     if(data[j] < data[lowIndex])
067                         lowIndex = j;
068                 }else{
069                     if(data[j] > data[lowIndex])
070                         lowIndex = j;
071                 }
072             }
073             swap(data,i,lowIndex);
074         }
075         return data;
076     }
077     /**
078      * 合并排序算法
079      * 说明：先合并后排序，再合并再排序，实用性很差
080      * @param data 待排序的数组
081      * @param asc 是否升序
082      * @return 排序后的数组
083      */
084     private static final int THRESHOLD =10;    //10个数据分为一份thershold
085     protected static long[] mergeSort(long[] data , boolean asc){
086         return mergeSortDo(data , 0 , data.length-1, asc);
087     }
088     //使用归并算法进行排序
089     private static long[] mergeSortDo(long[] data , int l, int r , boolean asc){
090         int i, j, k;
091         int mid = (l + r) / 2;
092         if(l==r)
093             return data;
094         if ((mid-l+1) > THRESHOLD){
095             data = mergeSortDo(data , l , mid , asc);
096             data = mergeSortDo(data , mid+1 , r ,asc);
097         }
098         data = insertSortDo(data , l , mid , asc);
099         data = insertSortDo(data , mid+1 , r , !asc);   
100         long[] temp = new long[data.length];
101         for(i=l,j=r,k=l ; k<=r ; k++){
102             if(asc){
103                 if(data[i]<data[j])
104                     temp[k] = data[i++];
105                 else
106                     temp[k] = data[j--];
107             }else{
108                 if(data[i]>data[j])
109                     temp[k] = data[i++];
110                 else
111                     temp[k] = data[j--];
112             }
113         }
114         for(int it=l ; it<=r ; it++)
115             data[it] = temp[it];
116         return data;
117     }
118     /**
119      * Shell排序
120      * 说明：不断把待排序的对象分成若干个小组,对同一小组内的对象采用直接插入法排序
121      * @param data 待排序的数组
122      * @param asc 是否升序
123      * @return 排序后的数组
124      */
125     protected static long[] ShellSort(long[] data , boolean asc){
126         long Temp; // 暂存变量
127         int DataLength; // 分割集合的间隔长度
128         int Pointer; // 进行处理的位置
129         DataLength = (data.length) / 2; // 初始集合间隔长度
130         while (DataLength != 0){
131             for (int j = DataLength; j < data.length; j++) {
132                 Temp = data[j];
133                 Pointer = j - DataLength; // 计算进行处理的位置
134                 // 进行集合内数值的比较与交换值
135                 if(asc){
136                     while (Temp < data[Pointer] && Pointer >= 0 && Pointer <= data.length) {
137                         data[Pointer + DataLength] = data[Pointer];
138                         // 计算下一个欲进行处理的位置
139                         Pointer = Pointer - DataLength;
140                         if (Pointer < 0 || Pointer > data.length)
141                             break;
142                     }
143                 }else{
144                     while (Temp > data[Pointer] && Pointer >= 0 && Pointer <= data.length) {
145                         data[Pointer + DataLength] = data[Pointer];
146                         // 计算下一个欲进行处理的位置
147                         Pointer = Pointer - DataLength;
148                         if (Pointer < 0 || Pointer > data.length)
149                             break;
150                     }
151                 }
152                
153                 data[Pointer + DataLength] = Temp;
154             }
155             DataLength = DataLength / 2;
156         }
157         return data;
158     }
159    
160     /**
161      * 快速排序，递归快速排序
162      * 说明：当前最优秀的内部排序方法
163      * @param data 待排序的数组
164      * @param asc 是否升序
165      * @return 排序后的数组
166      */
167     protected static long[] QuickSort(long[] data , boolean asc){
168         return qSort(data,0,data.length-1 , asc);
169     }
170     protected static long[] qSort(long[] data , int left , int right , boolean asc){
171         int pivotIndex = (left + right) / 2;
172         swap(data, pivotIndex, right);
173         int k = partition(data, left - 1, right, data[right] , asc);
174         swap(data, k, right);
175         if ((k - left) > 1)
176             qSort(data, left, k - 1 , asc);
177         if ((right - k) > 1)
178             qSort(data, k + 1, right , asc);
179         return data;
180     }
181     //快速排序调用函数
182     private static int partition(long[] data, int l, int r, long pivot , boolean asc) {
183         do {
184             if(asc){
185                 while (data[++l] < pivot)
186                     ;
187                 while ((r != 0) && data[--r] > pivot)
188                     ;
189             }else{
190                 while (data[++l] > pivot)
191                     ;
192                 while ((r != 0) && data[--r] < pivot)
193                     ;
194             }
195            
196             swap(data, l, r);
197         } while (l < r);
198         swap(data, l, r);
199         return l;
200     }
201     /**
202      * 中文字符串按照拼音排序
203      * @param data 字符串数组
204      * @param asc 是否升序
205      * @return 排序后的字符串
206      */
207     @SuppressWarnings("unchecked")
208     public static String[] chineseSort(String[] data , boolean asc){
209         if(data == null || data.length == 0)
210             return null;
211         String[] result = new String[data.length];
212         Arrays.sort(data,new CnSortComparator());
213         if(asc){
214             for(int i=0 ; i<data.length ; i++)
215                 result[i] = data[data.length-1-i];
216             return result;
217         }else{
218             return data;
219         }
220     }
221     /**
222      * 字符串进行排序
223      * 优先级：数字>特殊字符>字母，小写>大写
224      * @param data 待处理的数组
225      * @param asc 是否升序
226      * @return 排序后的字符串数组
227      */
228     public static String[] stringSort(String[] data , boolean asc){
229         if(data == null || data.length == 0)
230             return null;
231         List<String> list = new ArrayList<String>();
232         for(int i=0 ; i<data.length ; i++)
233             list.add(data[i]);
234         Collections.sort(list, new StringSortComparator());
235         if(asc){
236             for(int i=0 ; i<list.size() ; i++)
237                 data[i] = list.get(i);
238         }else{
239             for(int i=0 ; i<list.size() ; i++)
240                 data[i] = list.get(list.size()-1-i);
241         }
242         return data;
243     }
244    
245     /**
246      * 对指定下标之间的数据进行升降序
247      * @param data 待排序的数组
248      * @param start 开始下标
249      * @param end 结束下标
250      * @param asc 是否升序
251      * @return 排序后的数组
252      */
253     protected static long[] insertSortDo(long[] data, int start, int end , boolean asc) {
254         if(start == end)
255             return data;
256         for(int i=start ; i<end ; i++){
257             if(asc){
258                 for(int j=i+1;j>start;j--)
259                     if(data[j-1]>data[j])
260                         swap(data,j-1,j);
261                     else
262                         break;
263             }else{
264                 for(int j=i+1;j>start;j--)
265                     if(data[j-1]<data[j])
266                         swap(data,j-1,j);
267                     else
268                         break;
269             }
270         }
271         return data;
272     }   
273     private static void swap(long[] data , int i , int j){
274         if(i != j){
275             data[i] = data[i] ^ data[j];
276             data[j] = data[j] ^ data[i];
277             data[i] = data[i] ^ data[j];
278         }
279     }       
280     @SuppressWarnings("unused")
281     public static void main(String[] args) {
282         long[] L_1 = {1,2,23,3,7,6,8,9,34,2,99,14,435,20,3,54,123,35,4};
283         long[] L_2 = {1,2,23,3,7,6,8,9,34,2,99,14,435,20,3,54,123,35,4};
284         long[] L_3 = {1,2,23,3,7,6,8,9,34,2,99,14,435,20,3,54,123,35,4};
285         long[] L_4 = {1,2,23,3,7,6,8,9,34,2,99,14,435,20,3,54,123,35,4};
286         long[] L_5 = {1,2,23,3,7,6,8,9,34,2,99,14,435,20,3,54,123,35,4};
287         long[] L_6 = {1,2,23,3,7,6,8,9,34,2,99,14,435,20,3,54,123,35,4};
288         boolean doFlag = false;
289         //冒泡排序
290         long beginTime1 = System.nanoTime();
291         long[] la1 = bubbleSort(L_1,doFlag);       
292         long endTime1 = System.nanoTime();
293         System.out.println("冒泡排序法消耗时间\t："+(endTime1-beginTime1));
294         //插入排序
295         long beginTime2 = System.nanoTime();
296         long[] la2 = insertSort(L_2,doFlag);       
297         long endTime2 = System.nanoTime();
298         System.out.println("插入排序法消耗时间\t："+(endTime2-beginTime2));
299         //选择排序
300         long beginTime3 = System.nanoTime();       
301         long[] la3 = selectSort(L_3,doFlag);
302         long endTime3 = System.nanoTime();
303         System.out.println("选择排序法消耗时间\t："+(endTime3-beginTime3));
304        
305         //合并排序
306         long beginTime4 = System.nanoTime();
307         long[] la4 = mergeSort(L_4,doFlag);       
308         long endTime4 = System.nanoTime();
309         System.out.println("合并排序法消耗时间\t："+(endTime4-beginTime4));
310        
311         //Shell排序
312         long beginTime5 = System.nanoTime();
313         long[] la5 = ShellSort(L_5,doFlag);       
314         long endTime5 = System.nanoTime();
315         System.out.println("Shell排序法消耗时间\t："+(endTime5-beginTime5));
316        
317         //快速排序
318         long beginTime6 = System.nanoTime();
319         long[] la6 = QuickSort(L_6,doFlag);       
320         long endTime6 = System.nanoTime();
321         System.out.println("快速排序法消耗时间\t："+(endTime6-beginTime6));
322        
323         //中文排序
324         String[] name = {"阿水","云之麒","张三","你们","丁丁"};
325         System.out.println(Arrays.toString(chineseSort(name,doFlag)));
326        
327         //字符串排序
328         String[] str = {"asdg","_zdsgsdg","dgdfg"};
329         System.out.println(Arrays.toString(stringSort(str,doFlag)));
330     }
331 }