几种排序算法

1. package hays.algoriths;
   
2. 
   
3. /**
   
4. * 这是一个基于各种排序算法的类,是algorithms包下的第一个类,由hays整理编写,全部是静态的排序方法.
   
5. *
   
6. * @author hays H
   
7. * @version 1.0
   
8. */
   
9. public class Sort {
   
10. 
    
11.         /**
    
12.          * 利用插入排序给数组排序的算法,没有返回值,当执行完方法后,输入数组就a就已经包含了已经排好序的输出序列
    
13.          *
    
14.          * @param a
    
15.          *            接收一个 int 型的数组
    
16.          */
    
17.         public static void insertionSort(int[] a) {
    
18.                 int key, i;
    
19.                 for (int j = 1; j < a.length; j++) {
    
20.                         key = a[j];
    
21.                         i = j - 1;
    
22.                         while (i >= 0 && a[i] > key) {
    
23.                                 a[i + 1] = a[i];
    
24.                                 i = i - 1;
    
25.                         }
    
26.                         a[i + 1] = key;
    
27.                 }
    
28.         }
    
29. 
    
30.         /**
    
31.          * 对int型数组进行排序的方法,利用合并排序算法,利用分治法的思想,不断合并递归
    
32.          *
    
33.          * @param arr
    
34.          *            接收一个int型的数组
    
35.          * @param p
    
36.          *            需要排序的起始元素
    
37.          * @param r
    
38.          *            待排序的 终止元素
    
39.          */
    
40.         public static void mergeSort(int[] arr, int p, int r) {
    
41.                 int q;
    
42.                 if (p < r) {
    
43.                         q = (p + r) / 2;
    
44.                         mergeSort(arr, p, q);
    
45.                         mergeSort(arr, q + 1, r);
    
46.                         merge(arr, p, q, r);
    
47.                 }
    
48.         }
    
49. 
    
50.         // 分治法排序
    
51.         private static void merge(int[] arr, int p, int q, int r) {
    
52.                 int n1 = q - p + 1;
    
53.                 int n2 = r - q;
    
54.                 int[] L = new int[n1 + 1];
    
55.                 int[] R = new int[n2 + 1];
    
56.                 for (int i = 0; i < n1; i++) {
    
57.                         L[i] = arr[p + i];
    
58.                 }
    
59.                 for (int j = 0; j < n2; j++) {
    
60.                         R[j] = arr[q + j + 1];
    
61.                 }
    
62.                 L[n1] = Integer.MAX_VALUE;
    
63.                 R[n2] = Integer.MAX_VALUE;
    
64.                 int i = 0;
    
65.                 int j = 0;
    
66.                 for (int k = p; k < r + 1; k++) {
    
67.                         if (L[i] <= R[j]) {
    
68.                                 arr[k] = L[i];
    
69.                                 i++;
    
70.                         } else {
    
71.                                 arr[k] = R[j];
    
72.                                 j++;
    
73.                         }
    
74.                 }
    
75.         }
    
76. 
    
77.         /**
    
78.          * 冒泡排序,对一个整型数组进行排序
    
79.          *
    
80.          * @param arr
    
81.          *            接收一个整型数组
    
82.          */
    
83.         public static void bubbleSort(int[] arr) {
    
84.                 for(int i=0;i<arr.length;i++){
    
85.                         for(int j=arr.length-1;j>i;j--){
    
86.                                 if(arr[j]<arr[j-1])
    
87.                                 {
    
88.                                         int temp;
    
89.                                         temp = arr[j-1];
    
90.                                         arr[j-1]=arr[j];
    
91.                                         arr[j]=temp;
    
92.                                 }
    
93.                         }
    
94.                 }
    
95.         }
    
96.        
    
97.         /**
    
98.          * 堆排序:对一个整型数组进行排序 堆排序的运行时间为O(nlgn).它是一种原地(in place)排序算法,在任何时候只有常数个元素存储在数组之外
    
99.          * 堆排序引入 堆数据结构  管理算法执行中的信息
    
100.          *           堆数据结构不只是在堆排序中有用,还可以构成一个有效的优先队列.
     
101.          * @param arr 接收一个整型数组
     
102.          *
     
103.          */
     
104.         private static int heap_size;
     
105.         public static void heapSort(int[] arr){
     
106.                
     
107.                 build_MAX_heap(arr);
     
108.                 for (int i = arr.length; i>=2; i--) {
     
109.                         int temp = arr[0];
     
110.                         arr[0] = arr[i-1];
     
111.                         arr[i-1] = temp;
     
112.                         heap_size = heap_size -1;
     
113.                         MAX_heapify(arr, 1);
     
114.                 }
     
115.         }
     
116. 
     
117.         private static void build_MAX_heap(int[] arr) {
     
118.                 heap_size = arr.length;
     
119.                 for (int i = arr.length/2; i>=1; i--) {
     
120.                         MAX_heapify(arr,i);
     
121.                 }
     
122.         }
     
123. 
     
124.         private static void MAX_heapify(int[] arr, int i) {
     
125.                 int largest;
     
126.                 int l = 2*i;    //lift(i)
     
127.                 int r = 2*i +1; //right(i)
     
128.                 if(l<=heap_size && arr[l-1]>arr[i-1]){
     
129.                         largest = l;
     
130.                 }
     
131.                 else{
     
132.                         largest = i;
     
133.                 }
     
134.                 if(r<=heap_size && arr[r-1]>arr[largest-1]){
     
135.                         largest = r;
     
136.                 }
     
137.                 if(largest!=i){
     
138.                         int temp = arr[i-1];
     
139.                         arr[i-1] = arr[largest-1];
     
140.                         arr[largest-1] = temp;
     
141. MAX_heapify(arr, largest);
     
142.                 }       
     
143.         }
     
144.        
     
145. }
     

复制代码

值得学习ing!