常用的排序算法

搞了这么久，终于把几种常用的排序算法搞清楚了

时间复杂度为O(n ^ 2)的三个

直接插入排序，选择排序，冒泡排序

时间复杂度为O(N * logN)的排序算法

快速排序，归并排序，希尔排序，堆排序

归并排序空间复杂度为O（n）

其他空间复杂度均为O(1)

直接插入排序

 1 import com.gxf.util.Util;
 2 
 3 /**
 4  * 直接插入排序
 5  * @author GXF
 6  *
 7  */
 8 public class InsertSort {
 9 
10     public static void main(String[] args) {
11         int array[] = {32, 1, 34, 54, 5, 6};
12         
13         Util.showInArray(array);
14         
15         InsertSort insertSort = new InsertSort();
16         insertSort.insertSort(array);
17         
18         Util.showInArray(array);
19     }
20     
21     public void insertSort(int array[]){
22         if(array == null || array.length == 0)
23             return;
24         
25         for(int i = 1; i < array.length; i++){
26             int temp = array[i];
27             int j = i;
28             while(j >= 1 && array[j - 1] > temp)
29             {
30                 array[j] = array[j - 1];
31                 j--;
32             }//while
33             array[j] = temp;
34         }//for
35     }
36     
37     
38 }

选择排序

 1 import com.gxf.util.Util;
 2 
 3 /**
 4  * 直接选择排序
 5  * @author GXF
 6  *
 7  */
 8 public class SelectSort {
 9 
10     public static void main(String[] args) {
11         SelectSort selectSort = new SelectSort();
12         int array[] = {32, 1, 34, 54, 5, 6};
13         Util.showInArray(array);
14         selectSort.selectSort(array);
15         Util.showInArray(array);
16 
17     }
18     
19     /**
20      * 直接选择排序
21      * @param array
22      */
23     public void selectSort(int array[]){
24         for(int i = 0; i < array.length; i++){
25             int min = i;
26             for(int j = i + 1; j < array.length; j++){
27                 if(array[j] < array[min])
28                     min = j;
29             }//for
30             if(min != i){
31                 int temp = array[i];
32                 array[i] = array[min];
33                 array[min] = temp;
34             }//if
35         }//for
36     }
37 }

冒泡排序

 1 import com.gxf.util.Util;
 2 
 3 /**
 4  * 直接选择排序
 5  * @author GXF
 6  *
 7  */
 8 public class SelectSort {
 9 
10     public static void main(String[] args) {
11         SelectSort selectSort = new SelectSort();
12         int array[] = {32, 1, 34, 54, 5, 6};
13         Util.showInArray(array);
14         selectSort.selectSort(array);
15         Util.showInArray(array);
16 
17     }
18     
19     /**
20      * 直接选择排序
21      * @param array
22      */
23     public void selectSort(int array[]){
24         for(int i = 0; i < array.length; i++){
25             int min = i;
26             for(int j = i + 1; j < array.length; j++){
27                 if(array[j] < array[min])
28                     min = j;
29             }//for
30             if(min != i){
31                 int temp = array[i];
32                 array[i] = array[min];
33                 array[min] = temp;
34             }//if
35         }//for
36     }
37 }

--------------------------------------------------我是分割线---------------------------------------------------

快速排序

 1 /**
 2  * 快速排序
 3  * 先是一次划分
 4  * @author GXF
 5  *
 6  */
 7 public class QuickSort {
 8 
 9 
10     public static void main(String[] args) {
11         QuickSort quickSort = new QuickSort();
12         int array[] = {32, 1, 34, 54, 5, 6};
13         Util.showInArray(array);
14         quickSort.quickSort(array, 0, array.length - 1);
15         Util.showInArray(array);
16 
17     }
18     
19     /**
20      * 快速排序
21      * @param array
22      * @param start
23      * @param end
24      */
25     public void quickSort(int array[], int start, int end){
26         if(start < end){
27             int index = partion(array, start, end);
28             quickSort(array, start, index - 1);
29             quickSort(array, index + 1, end);
30         }
31     }
32     
33     /**
34      * 一次划分
35      * @param array
36      * @param start
37      * @param end
38      * @return
39      */
40     public int partion(int array[], int start, int end){
41         int key = array[start];
42         while(start < end){
43             while(start < end && array[end] > key)            //从后面开始扫描
44                 end--;
45             array[start] = array[end];
46             while(start < end && array[start] < key)
47                 start++;
48             array[end] = array[start];
49         }//while
50         array[start] = key;
51         
52         return start;
53     }
54 
55 }

归并排序

 1 import com.gxf.util.Util;
 2 
 3 /**
 4  * 归并排序
 5  * 归并：递归 + 合并
 6  * 时间复杂度O（n * logn）
 7  * 空间复杂度O(N)
 8  * @author GXF
 9  *
10  */
11 public class MergeSort {
12 
13 
14     public static void main(String[] args) {
15         int array[] = {32, 1, 34, 54, 5, 6};
16         MergeSort mergeSort = new MergeSort();
17         Util.showInArray(array);
18         mergeSort.mergeSort(array);
19         Util.showInArray(array);
20 
21     }
22     
23     
24     public void mergeSort(int array[]){
25         if(array == null || array.length == 0)
26             return;
27         mergeSort(array, 0, array.length - 1, new int[array.length]);
28     }
29     
30     /**
31      * 归并排序
32      * 升序排列
33      * @param array
34      * @param start
35      * @param last
36      * @param temp
37      */
38     private void mergeSort(int array[], int start, int last, int temp[]){
39         if(start < last){
40             int middle = (start + last) / 2;
41             mergeSort(array, start, middle, temp);
42             mergeSort(array, middle + 1, last, temp);
43             merge(array, start, middle, last, temp);
44         }
45     }
46     
47     /**
48      * 合并两个数组
49      * @param array
50      * @param start
51      * @param middle
52      * @param last
53      * @param temp
54      */
55     public void merge(int array[], int start, int middle, int last, int temp[]){
56         int first = start;
57         int second = middle + 1;
58         int k = 0;
59         
60         while(first <= middle && second <= last){
61             if(array[first] < array[second])
62                 temp[k++] = array[first++];
63             else
64                 temp[k++] = array[second++];
65         }//while
66         
67         while(first <= middle)
68             temp[k++] = array[first++];
69         while(second <= last)
70             temp[k++] = array[second++];
71         for(int i = 0; i < k; i++)
72             array[start + i] = temp[i];
73     }
74 
75 }

希尔排序

 1 import com.gxf.util.Util;
 2 
 3 /**
 4  * 希尔排序
 5  * 时间复杂度O（n * logn）
 6  * 空间复杂度O（1）
 7  * @author GXF
 8  *
 9  */
10 public class ShellSort {
11 
12 
13     public static void main(String[] args) {
14         int array[] = {32, 1, 34, 54, 5, 6};
15         ShellSort shellSort = new ShellSort();
16         Util.showInArray(array);
17         shellSort.shellSort(array);
18         Util.showInArray(array);
19 
20     }
21     
22     /**
23      * 这段代码整理的确实漂亮
24      * @param array
25      */
26     public void shellSort(int array[]){
27         if(array == null || array.length == 0)
28             return;
29         for(int gap = array.length / 2; gap > 0; gap /= 2){
30             for(int i = gap; i < array.length; i++){
31                 for(int j = i; j >= gap && array[j] < array[j - gap]; j -= gap)
32                     swap(array, j, j - gap);
33             }
34         }
35     }
36     
37     private void swap(int array[], int i, int j){
38         int temp = array[i];
39         array[i] = array[j];
40         array[j] = temp;
41     }
42 
43 }

堆排序

 1 import com.gxf.util.Util;
 2 
 3 /**
 4  * 堆排序
 5  * 时间复杂度O（n * logn）
 6  * 空间复杂度O（1）
 7  * @author GXF
 8  *
 9  */
10 public class HeapSort {
11 
12     public static void main(String[] args) {
13         int array[] = {32, 1, 34, 54, 5, 6};
14         HeapSort heapSort = new HeapSort();
15         Util.showInArray(array);
16         heapSort.heapSort(array);
17         Util.showInArray(array);
18 
19     }
20     
21     /**
22      * 堆排序
23      * 升序排列
24      * 先建立一个大根堆
25      * 用数组最后一个元素和第一个元素交换，调整大根堆
26      * @param array
27      */
28     public void heapSort(int array[]){
29         //建堆
30         for(int i = array.length / 2 - 1; i >= 0; i--){
31             maxHeapFixDown(array, i, array.length);
32         }
33         //调整堆
34         for(int i = array.length - 1; i >= 0; i--){
35             swap(array, 0, i);
36             maxHeapFixDown(array, 0, i);
37         }
38     }
39     
40     /**
41      * 对大根堆中，i节点进行向下调整
42      * @param array
43      * @param i
44      */
45     private void maxHeapFixDown(int array[], int i, int n){
46         int temp = array[i];
47         int j = 2 * i + 1;
48         while(j < n && i < n){
49             //选出子节点中最大的
50             if(j + 1 < n && array[j] < array[j + 1])
51                 j = j + 1;
52             if(array[j] < temp)
53                 break;
54             //子节点中最大的向上移动
55             array[i] = array[j];
56             i = j;
57             j = 2 * i + 1;
58         }//while
59         array[i] = temp;
60     }
61     
62     private void swap(int array[], int i, int j){
63         int temp = array[i];
64         array[i] = array[j];
65         array[j] = temp;
66     }
67 }