最全的排序

折半插入排序

 1 package sort;
 2 /**
 3  * 折半插入排序
 4  * @author shkstart
 5  * 2013-11-27
 6  */
 7 
 8 public class BinaryInsertSort {
 9     public static void binaryInsertSort(DataWrap[] data) {
10         System.out.println("开始排序");
11         int arrayLength = data.length;
12         for (int i = 1; i < arrayLength; i++) {
13             DataWrap temp = data[i];
14             int low = 0;
15             int high = i - 1;
16             while (low <= high) {
17                 int mid = (low + high) / 2;
18                 if (temp.compareTo(data[mid]) > 0) {
19                     low = mid + 1;
20                 } else {
21                     high = mid - 1;
22                 }
23             }
24             for (int j = i; j > low; j--) {
25                 data[j] = data[j - 1];
26             }
27             data[low] = temp;
28             System.out.println(java.util.Arrays.toString(data));
29         }
30 
31     }
32 
33     public static void main(String[] args) {
34         DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""),
35                 new DataWrap(21, "*"), new DataWrap(23, ""),
36                 new DataWrap(-30, ""), new DataWrap(-49, ""),
37                 new DataWrap(21, ""), new DataWrap(30, "*"),
38                 new DataWrap(30, "")};
39         System.out.println("排序之前：
" + java.util.Arrays.toString(data));
40         binaryInsertSort(data);
41         System.out.println("排序之后：
" + java.util.Arrays.toString(data));
42     }
43 }
View Code

冒泡排序

 1 package sort;
 2 
 3 /**
 4  * 冒泡排序
 5  * @author shkstart
 6  * 2013-11-27
 7  */
 8 public class BubbleSort {
 9     public static void bubbleSort(DataWrap[] data) {
10         System.out.println("开始排序");
11         int arrayLength = data.length;
12         for (int i = 0; i < arrayLength - 1; i++) {
13             boolean flag = false;
14             for (int j = 0; j < arrayLength - 1 - i; j++) {
15                 if (data[j].compareTo(data[j + 1]) > 0) {
16                     DataWrap temp = data[j + 1];
17                     data[j + 1] = data[j];
18                     data[j] = temp;
19                     flag = true;
20                 }
21             }
22             System.out.println(java.util.Arrays.toString(data));
23             if (!flag)
24                 break;
25         }
26     }
27 
28     public static void main(String[] args) {
29         DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""),
30                 new DataWrap(21, "*"), new DataWrap(23, ""),
31                 new DataWrap(-30, ""), new DataWrap(-49, ""),
32                 new DataWrap(21, ""), new DataWrap(30, "*"),
33                 new DataWrap(30, "")};
34         System.out.println("排序之前：
" + java.util.Arrays.toString(data));
35         bubbleSort(data);
36         System.out.println("排序之后：
" + java.util.Arrays.toString(data));
37     }
38 }
View Code

桶式排序

 1 package sort;
 2 
 3 import java.util.Arrays;
 4 
 5 /**
 6  * 桶式排序
 7  * 
 8  * @author shkstart 
 9  * 2013-11-27
10  */
11 public class BucketSort {
12     public static void bucketSort(DataWrap[] data, int min, int max) {
13         System.out.println("开始排序");
14         int arrayLength = data.length;
15         DataWrap[] temp = new DataWrap[arrayLength];
16         int[] buckets = new int[max - min];
17         for (int i = 0; i < arrayLength; i++) {
18             buckets[data[i].data - min]++;
19         }
20         System.out.println(Arrays.toString(buckets));
21         for (int i = 1; i < max - min; i++) {
22             buckets[i] = buckets[i] + buckets[i - 1];
23         }
24         System.out.println(Arrays.toString(buckets));
25         System.arraycopy(data, 0, temp, 0, arrayLength);
26         for (int k = arrayLength - 1; k >= 0; k--) {
27             data[--buckets[temp[k].data - min]] = temp[k];
28         }
29     }
30 
31     public static void main(String[] args) {
32         DataWrap[] data = { new DataWrap(9, ""), new DataWrap(5, ""),
33                 new DataWrap(-1, ""), new DataWrap(8, ""),
34                 new DataWrap(5, "*"), new DataWrap(7, ""),
35                 new DataWrap(3, ""), new DataWrap(-3, ""),
36                 new DataWrap(1, ""),new DataWrap(3, "*")};
37         System.out.println("排序之前：
" + java.util.Arrays.toString(data));
38         bucketSort(data, -3, 10);
39         System.out.println("排序之后：
" + java.util.Arrays.toString(data));
40     }
41 }
View Code

堆排序

 1 package sort;
 2 
 3 /**
 4  * 堆排序
 5  * @author shkstart
 6  * 2013-11-27
 7  */
 8 public class HeapSort {
 9     public static void heapSort(DataWrap[] data) {
10         System.out.println("开始排序");
11         int arrayLength = data.length;
12         // 循环建堆
13         for (int i = 0; i < arrayLength - 1; i++) {
14             // 建堆
15             builMaxdHeap(data, arrayLength - 1 - i);
16             // 交换堆顶和最后一个元素
17             swap(data, 0, arrayLength - 1 - i);
18             System.out.println(java.util.Arrays.toString(data));
19         }
20     }
21 
22     // 对data数组从0到lastIndex建大顶堆
23     private static void builMaxdHeap(DataWrap[] data, int lastIndex) {
24         // 从lastIndex处节点（最后一个节点）的父节点开始
25         for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
26             // k保存当前正在判断的节点
27             int k = i;
28             // 如果当前k节点的子节点存在
29             while (k * 2 + 1 <= lastIndex) {
30                 // k节点的左子节点的索引
31                 int biggerIndex = 2 * k + 1;
32                 // 如果biggerIndex小于lastIndex，即biggerIndex +1
33                 // 代表k节点的右子节点存在
34                 if (biggerIndex < lastIndex) {
35                     // 如果右子节点的值较大
36                     if (data[biggerIndex].compareTo(data[biggerIndex + 1]) < 0) {
37                         // biggerIndex总是记录较大子节点的索引
38                         biggerIndex++;
39                     }
40                 }
41                 // 如果k节点的值小于其较大子节点的值
42                 if (data[k].compareTo(data[biggerIndex]) < 0) {
43                     // 交换它们
44                     swap(data, k, biggerIndex);
45                     // 将biggerIndex赋给k，开始while循环的下一次循环
46                     // 重新保证k节点的值大于其左、右节点的值
47                     k = biggerIndex;
48                 } else {
49                     break;
50                 }
51             }
52         }
53     }
54 
55     // 交换data数组中i、j两个索引处的元素
56     private static void swap(DataWrap[] data, int i, int j) {
57         DataWrap temp = data[i];
58         data[i] = data[j];
59         data[j] = temp;
60     }
61 
62     public static void main(String[] args) {
63         DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""),
64                 new DataWrap(21, "*"), new DataWrap(23, ""),
65                 new DataWrap(-30, ""), new DataWrap(-49, ""),
66                 new DataWrap(21, ""), new DataWrap(30, "*"),
67                 new DataWrap(30, "")};
68         System.out.println("排序之前：
" + java.util.Arrays.toString(data));
69         heapSort(data);
70         System.out.println("排序之后：
" + java.util.Arrays.toString(data));
71     }
72 }
View Code

直接插入排序

 1 package sort;
 2 
 3 /**
 4  * 直接插入排序
 5  * @author shkstart
 6  * 2013-11-27
 7  */
 8 public class InsertSort {
 9     public static void insertSort(DataWrap[] data){
10         System.out.println("开始排序");
11         int arrayLength = data.length;
12         for(int i = 1;i < arrayLength;i++){
13             DataWrap temp = data[i];
14             if(data[i].compareTo(data[i-1]) < 0){
15                 int j = i -1;
16                 for(;j >= 0 && data[j].compareTo(temp) > 0;j--){
17                     data[j +1] = data[j];
18                 }
19                 data[j + 1] = temp;
20             }
21             System.out.println(java.util.Arrays.toString(data));
22         }
23         
24     }
25     public static void main(String[] args) {
26         DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""),
27                 new DataWrap(21, "*"), new DataWrap(23, ""),
28                 new DataWrap(-30, ""), new DataWrap(-49, ""),
29                 new DataWrap(21, ""), new DataWrap(30, "*"),
30                 new DataWrap(30, "")};
31         System.out.println("排序之前：
" + java.util.Arrays.toString(data));
32         insertSort(data);
33         System.out.println("排序之后：
" + java.util.Arrays.toString(data));
34     }
35 }
View Code

归并排序

 1 package sort;
 2 
 3 /**
 4  * 归并排序
 5  * 
 6  * @author shkstart 
 7  * 2013-11-27
 8  */
 9 public class MergeSort {
10     public static void mergeSort(DataWrap[] data) {
11         // 归并排序
12         sort(data, 0, data.length - 1);
13     }
14 
15     // 将索引从left到right范围的数组元素进行归并排序
16     private static void sort(DataWrap[] data, int left, int right) {
17         if(left < right){
18             //找出中间索引
19             int center = (left + right)/2;
20             sort(data,left,center);
21             sort(data,center+1,right);
22             //合并
23             merge(data,left,center,right);
24         }
25     }
26 
27     // 将两个数组进行归并，归并前两个数组已经有序，归并后依然有序
28     private static void merge(DataWrap[] data, int left, int center, int right) {
29         DataWrap[] tempArr = new DataWrap[data.length];
30         int mid = center + 1;
31         int third = left;
32         int temp = left;
33         while (left <= center && mid <= right) {
34             if (data[left].compareTo(data[mid]) <= 0) {
35                 tempArr[third++] = data[left++];
36             } else {
37                 tempArr[third++] = data[mid++];
38             }
39         }
40         while (mid <= right) {
41             tempArr[third++] = data[mid++];
42         }
43         while (left <= center) {
44             tempArr[third++] = data[left++];
45         }
46         while (temp <= right) {
47             data[temp] = tempArr[temp++];
48         }
49     }
50 
51     public static void main(String[] args) {
52         DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""),
53                 new DataWrap(21, "*"), new DataWrap(23, ""),
54                 new DataWrap(-30, ""), new DataWrap(-49, ""),
55                 new DataWrap(21, ""), new DataWrap(30, "*"),
56                 new DataWrap(30, "") };
57         System.out.println("排序之前：
" + java.util.Arrays.toString(data));
58         mergeSort(data);
59         System.out.println("排序之后：
" + java.util.Arrays.toString(data));
60     }
61 }
View Code

基数排序

 1 package sort;
 2 
 3 import java.util.Arrays;
 4 
 5 /**
 6  * 基数排序
 7  * 
 8  * @author shkstart 2013-11-27
 9  */
10 public class MultiKeyRadixSort {
11     public static void radixSort(int[] data, int radix, int d) {
12         System.out.println("开始排序：");
13         int arrayLength = data.length;
14         int[] temp = new int[arrayLength];
15         int[] buckets = new int[radix];
16         for (int i = 0, rate = 1; i < d; i++) {
17             // 重置count数组，开始统计第二个关键字
18             Arrays.fill(buckets, 0);
19             // 当data数组的元素复制到temp数组中进行缓存
20             System.arraycopy(data, 0, temp, 0, arrayLength);
21             for (int j = 0; j < arrayLength; j++) {
22                 int subKey = (temp[j] / rate) % radix;
23                 buckets[subKey]++;
24             }
25             for (int j = 1; j < radix; j++) {
26                 buckets[j] = buckets[j] + buckets[j - 1];
27             }
28             for (int m = arrayLength - 1; m >= 0; m--) {
29                 int subKey = (temp[m] / rate) % radix;
30                 data[--buckets[subKey]] = temp[m];
31             }
32             System.out.println("对" + rate + "位上子关键字排序："
33                     + java.util.Arrays.toString(data));
34             rate *= radix;
35         }
36     }
37 
38     public static void main(String[] args) {
39         int[] data = { 1100, 192, 221, 12, 13 };
40         System.out.println("排序之前：
" + java.util.Arrays.toString(data));
41         radixSort(data, 10, 4);
42         System.out.println("排序之后：
" + java.util.Arrays.toString(data));
43     }
44 }
View Code

快速排序

 1 package sort;
 2 
 3 /**
 4  * 快速排序
 5  * @author shkstart
 6  * 2013-11-27
 7  */
 8 public class QuickSort {
 9     private static void swap(DataWrap[] data, int i, int j) {
10         DataWrap temp = data[i];
11         data[i] = data[j];
12         data[j] = temp;
13     }
14 
15     private static void subSort(DataWrap[] data, int start, int end) {
16         if (start < end) {
17             DataWrap base = data[start];
18             int i = start;
19             int j = end + 1;
20             while (true) {
21                 while (i < end && data[++i].compareTo(base) <= 0)
22                     ;
23                 while (j > start && data[--j].compareTo(base) >= 0)
24                     ;
25                 if (i < j) {
26                     swap(data, i, j);
27                 } else {
28                     break;
29                 }
30             }
31             swap(data, start, j);
32             subSort(data, start, j - 1);
33             subSort(data, j + 1, end);
34         }
35     }
36     public static void quickSort(DataWrap[] data){
37         subSort(data,0,data.length-1);
38     }
39     public static void main(String[] args) {
40         DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""),
41                 new DataWrap(21, "*"), new DataWrap(23, ""),
42                 new DataWrap(-30, ""), new DataWrap(-49, ""),
43                 new DataWrap(21, ""), new DataWrap(30, "*"),
44                 new DataWrap(30, "") };
45         System.out.println("排序之前：
" + java.util.Arrays.toString(data));
46         quickSort(data);
47         System.out.println("排序之后：
" + java.util.Arrays.toString(data));
48     }
49 }
View Code

直接选择排序

 1 package sort;
 2 
 3 
 4 /**
 5  * 直接选择排序
 6  * @author shkstart
 7  * 2013-11-27
 8  */
 9 public class SelectSort {
10     public static void selectSort(DataWrap[] data) {
11         System.out.println("开始排序");
12         int arrayLength = data.length;
13         for (int i = 0; i < arrayLength - 1; i++) {
14             for (int j = i + 1; j < arrayLength; j++) {
15                 if (data[i].compareTo(data[j]) > 0) {
16                     DataWrap temp = data[i];
17                     data[i] = data[j];
18                     data[j] = temp;
19                 }
20             }
21             System.out.println(java.util.Arrays.toString(data));
22         }
23     }
24 
25     public static void main(String[] args) {
26         DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""),
27                 new DataWrap(21, "*"), new DataWrap(23, ""),
28                 new DataWrap(-30, ""), new DataWrap(-49, ""),
29                 new DataWrap(21, ""), new DataWrap(30, "*"),
30                 new DataWrap(30, "") };
31         System.out.println("排序之前：
" + java.util.Arrays.toString(data));
32         selectSort(data);
33         System.out.println("排序之后：
" + java.util.Arrays.toString(data));
34     }
35 }
View Code

直接选择排序-改进

 1 package sort;
 2 
 3 /**
 4  * 直接选择排序-改进
 5  * @author shkstart
 6  * 2013-11-27
 7  */
 8 public class SelectSort2 {
 9     public static void selectSort(DataWrap[] data) {
10         System.out.println("开始排序");
11         int arrayLength = data.length;
12         for (int i = 0; i < arrayLength - 1; i++) {
13             int minIndex = i;
14             for (int j = i + 1; j < arrayLength; j++) {
15                 if (data[minIndex].compareTo(data[j]) > 0) {
16                     minIndex = j;
17                     
18                 }
19             }
20             if(minIndex != i){
21                 DataWrap temp = data[i];
22                 data[i] = data[minIndex];
23                 data[minIndex] = temp;
24             }
25             System.out.println(java.util.Arrays.toString(data));
26         }
27     }
28 
29     public static void main(String[] args) {
30         DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""),
31                 new DataWrap(21, "*"), new DataWrap(23, ""),
32                 new DataWrap(-30, ""), new DataWrap(-49, ""),
33                 new DataWrap(21, ""), new DataWrap(30, "*"),
34                 new DataWrap(30, "") };
35         System.out.println("排序之前：
" + java.util.Arrays.toString(data));
36         selectSort(data);
37         System.out.println("排序之后：
" + java.util.Arrays.toString(data));
38     }
39 }
View Code

 

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/longc/p/5967902.html