1 /*希爾排序：對插入排序的改進，其排序是按照一個增量序列來進行
2 *增量序列的個數就是排序的趟數。在任意增量K下，保證a[i]<=a[i+k]
3 *該算法的效率和增量需序列的選擇有很大關系。
4 *增量序列一般規則：h = 3h + 1;
5 *希爾排序的效率總體比簡單排序的好。
6 * */
7 public class ShellSort {
8
9 public static void main(String[] args) {
10 int[] list = {6,9,2,3,5,50,30,8,7,4,23,12};
11 displayList(list);
12 shellSort(list);
13 displayList(list);
14 }
15
16 public static void shellSort(int[] arr){
17 int inner,outer;
18 int temp;
19 int h = 1;
20 while(h <= arr.length / 3){
21 h = h * 3 + 1;
22 }
23 //外循環控制排序趟數
24 while(h > 0){
25 //控制每個增量的循環
26 for(outer = h; outer < arr.length; outer++){
27 temp = arr[outer];
28 inner = outer;
29
30 while(inner > h - 1 && arr[inner - h] >= temp){
31 arr[inner] = arr[inner - h];
32 inner = inner - h;
33 }
34 arr[inner] = temp;
35 }
36 h = (h - 1) / 3;
37 }
38 }
39
40 public static void displayList(int[] arr){
41 for(int i = 0; i < arr.length;i++){
42 System.out.print(arr[i] + " ");
43 }
44 System.out.println();
45 }
46
47 }
1 /*快速排序：将一個數組劃分為兩個子數組，遞歸調用自身為每個子數組進行快速排序。
2 * 注意：确定好遞歸終止條件right - left <= 0
3 * 每次劃分組：是根據劃分的思想确定出下次組的邊界
4 *2.劃分思想：按照序列中的某個值将序列劃分為兩部分，右邊值全部小于該值左邊的部分全部大于該值，
5 *該值的選擇盡量接近該組序列的平均值.通過在設定兩個指針，分别從相反的方向找到比中間值大的
6 *和比中間值小的，交換，最後将中間值放在其位置上。
7 *3.快速排序：通常來說是效率比較好的排序算法O(NlogN)
8 *4.中樞值選擇關鍵，最好兩邊長度差不多比較好，假如兩邊差的多，将導緻多的一邊過多的劃分
9 * 效率降低，序列無序度高效果會好點--對于随機選擇的中樞值
10 * */
11 public class QuickSort {
12
13 public static void main(String[] args) {
14 int[] list = {3,2,5,7,5,38,20,18,27,39,12};
15 displayList(list);
16 quickSort(list);
17 displayList(list);
18 }
19
20 public static void quickSort(int[] arr){
21 recQuickSort(0,arr.length-1,arr);
22 }
23
24 private static void recQuickSort(int left, int right,int[] arr) {
25 if(right - left <= 0){//size<=1.遞歸基準條件
26 return;
27 }
28 else{
29 int pivot = arr[right];
30 //整理一次小的在一邊大的在一邊,并獲得下次分組的邊界
31 int partition = partitionIt(left,right,pivot,arr);
32 recQuickSort(left, partition - 1, arr);
33 recQuickSort(partition + 1, right, arr);
34 }
35
36 }
37
38 public static int partitionIt(int left,int right,int pivot,int[] arr){
39 int lefter = left - 1; //第一個元素的左邊
40 int righter = right; //最後一個元素
41
42 while(true){
43 while(arr[++lefter] < pivot);//左邊直到找到比中間值大的一個元素
44
45 while(righter > 0 && arr[--righter] > pivot);//右邊直到找到比中間值小的一個元素
46
47 if(lefter >= righter){
48 break;
49 }
50 else{
51 swap(lefter,righter,arr); //交換兩個元素
52 }
53 }
54 swap(lefter,right,arr); //将標明的中間值放其位置上
55 return lefter;
56
57 }
58
59 private static void swap(int lefter, int righter,int[] list) {
60 int temp = list[lefter];
61 list[lefter] = list[righter];
62 list[righter] = temp;
63 }
64
65 public static void displayList(int[] arr){
66 for(int i = 0; i < arr.length;i++){
67 System.out.print(arr[i] + " ");
68 }
69 System.out.println();
70 }
71
72 }
