寫程式的基本功-排序演算法(Sorting Algorithm)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
/*
 * 排序法練習
 */
 
import java.util.*;
public class SortPractice{
	public static void main(String[] args){
		int arr[]={4,7,8,2,3,23,15,67,29,13,85,34,53,47,12,64,1,9};
		System.out.println("交換排序(Exchange sort)");
		System.out.println("排序前:" + Arrays.toString(arr));
		System.out.println("遞增排序後:" + Arrays.toString(exchange_sort(arr,true)));
		System.out.println("遞減排序後:" + Arrays.toString(exchange_sort(arr,false)));
 
		System.out.print("nn");
 
		System.out.println("選擇排序(Selection sort)");
		System.out.println("排序前:" + Arrays.toString(arr));
		System.out.println("遞增排序後:" + Arrays.toString(selection_sort(arr,true)));
		System.out.println("遞減排序後:" + Arrays.toString(selection_sort(arr,false)));
 
		System.out.print("nn");
 
		System.out.println("插入排序(Insertion sort)");
		System.out.println("排序前:" + Arrays.toString(arr));
		System.out.println("遞增排序後:" + Arrays.toString(insertion_sort(arr,true)));
		System.out.println("遞減排序後:" + Arrays.toString(insertion_sort(arr,false)));
 
		System.out.print("nn");
 
		System.out.println("氣泡排序(Bubble sort)");
		System.out.println("排序前:" + Arrays.toString(arr));
		System.out.println("遞增排序後:" + Arrays.toString(bubble_sort(arr,true)));
		System.out.println("遞減排序後:" + Arrays.toString(bubble_sort(arr,false)));
 
		System.out.print("nn");
 
		System.out.println("快速排序(Quick sort)");
		System.out.println("排序前:" + Arrays.toString(arr));
		System.out.println("遞增排序後:" + Arrays.toString(quick_sort(arr,true)));
		System.out.println("遞減排序後:" + Arrays.toString(quick_sort(arr,false)));
	}
 
	public static int[] exchange_sort(int[] ori_arr, boolean isIncrease){ //交換排序(Exchange sort)
		int[] arr=ori_arr.clone(); //將arr陣列位址指向新複製出來的ori_arr陣列。確保原始陣列資料不會改變。
		int len=arr.length; //取得陣列長度
		for(int i=0;i<len-1;i++){
			for(int k=i+1;k<len;k++){
				if((isIncrease&&arr[i]>arr[k])||(!isIncrease&&arr[i]<arr[k])){ //遞增遞減判斷
						int buffer=arr[i];
						arr[i]=arr[k];
						arr[k]=buffer;
				}
			}
		}
		return arr;
	}
 
	public static int[] selection_sort(int[] ori_arr, boolean isIncrease){ //選擇排序(Selection sort)
		int[] arr=ori_arr.clone(); //將arr陣列位址指向新複製出來的ori_arr陣列。確保原始陣列資料不會改變。
		int len=arr.length; //取得陣列長度
		for(int i=0;i<len-1;i++){
			int temp=i; //儲存最大或是最小值所指向的索引位置
			for(int k=i+1;k<len;k++){
				if((isIncrease&&arr[temp]>arr[k])||(!isIncrease&&arr[temp]<arr[k])){ //遞增遞減判斷
					temp=k;
				}
			}
			if(i!=temp){ //若索引未改變,則交換陣列值
				int buffer=arr[i];
				arr[i]=arr[temp];
				arr[temp]=buffer;
			}
		}
		return arr;
	}
 
	public static int[] insertion_sort(int[] ori_arr, boolean isIncrease){ //插入排序(Insertion sort)
		int[] arr=ori_arr.clone(); //將arr陣列位址指向新複製出來的ori_arr陣列。確保原始陣列資料不會改變。
		int len=arr.length; //取得陣列長度
 
		for(int i=1;i<len;i++){
			int buffer=arr[i];
			int k=i-1;
			while((isIncrease&&buffer<arr[k])||(!isIncrease&&buffer>arr[k])){ //遞增遞減判斷
				arr[k+1]=arr[k];
				k--;
				if(k<0){
					break;
				}
			}
			arr[k+1]=buffer;
		}
		return arr;
	}
 
	public static int[] bubble_sort(int[] ori_arr, boolean isIncrease){ //氣泡排序(Bubble sort)
		int[] arr=ori_arr.clone(); //將arr陣列位址指向新複製出來的ori_arr陣列。確保原始陣列資料不會改變。
		int len=arr.length; //取得陣列長度
 
		for(int i=len-1;i>0;i--){
			for(int k=0;k<i;k++){
				if((isIncrease&&arr[k]>arr[k+1])||(!isIncrease&&arr[k]<arr[k+1])){ //遞增遞減判斷
					int buffer=arr[k];
					arr[k]=arr[k+1];
					arr[k+1]=buffer;
				}
			}
		}
		return arr;
	}
 
	//---快速排序(Quick sort)---
	public static int[] quick_sort(int[] ori_arr, boolean isIncrease){ //快速排序(Quick sort)
		int[] arr=ori_arr.clone(); //將arr陣列位址指向新複製出來的ori_arr陣列。確保原始陣列資料不會改變。
		int len=arr.length; //取得陣列長度
		quick_sort_main(arr,0,len-1,isIncrease);
		return arr;
	}
 
	private static void quick_sort_main(int[] arr, int left, int right, boolean isIncrease){ //快速排序的主要演算法(分治法)
		if(right>left){ //若右軸索引大於左軸索引
			int i=left,k=right+1;
			while(true){
				while(i+1<arr.length&&(isIncrease&&arr[++i]<arr[left]||(!isIncrease&&arr[++i]>arr[left]))) ;//向右找。如果左軸沒有找到大於(遞減則小於)pivot的數,就一直持續找下去,直到超過右軸極限為止
				while(k-1>-1&&(isIncrease&&arr[--k]>arr[left]||(!isIncrease&&arr[--k]<arr[left]))) ; //向左找。如果右軸沒有找到小於(遞減則大於)pivot的數,就一直持續找下去,直到超過左軸極限為止
 
				if(i>=k){
					break;
				}
 
				//交換左軸右軸的值
				int buffer=arr[i];
				arr[i]=arr[k];
				arr[k]=buffer;
 
			}
			//固定用過的pivot位置
			int buffer=arr[left];
			arr[left]=arr[k];
			arr[k]=buffer;
 
			quick_sort_main(arr,left,k-1,isIncrease); //左軸遞迴
			quick_sort_main(arr,k+1,right,isIncrease); //右軸遞迴
		}
	}
}
文章分類:Java|標籤:, , , , , , , , , , ,
相關文章
目前還沒有相關文章喔!

迴響已關閉