001 //插入排序:
002
003 package org.rut.util.algorithm.support;
004
005 import org.rut.util.algorithm.SortUtil;
006 /**
007 * @author treeroot
008 * @since 2006-2-2
009 * @version 1.0
010 */
011 public class InsertSort implements SortUtil.Sort{
012
013 /** (non-Javadoc)
014 * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
015 */
016 public void sort(int[] data) {
017 int temp;
018 for(int i=1;i<data.length;i++){
019 for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){
020 SortUtil.swap(data,j,j-1);
021 }
022 }
023 }
024
025 }
026 //冒泡排序:
027
028
029 for(var i=0; i<arr.length; i++) {
030 for(var j=i+1; j<=arr.length-1; j++) {
031 if(eval(arr[i]) < eval(arr[j])) {
032 temp = arr[i];
033 arr[i] = arr[j];
034 arr[j] = temp;
035 }
036 }
037 }
038
039
040
041 package org.rut.util.algorithm.support;
042
043 import org.rut.util.algorithm.SortUtil;
044
045 /**
046 * @author treeroot
047 * @since 2006-2-2
048 * @version 1.0
049 */
050 public class BubbleSort implements SortUtil.Sort{
051
052 /** (non-Javadoc)
053 * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
054 */
055 public void sort(int[] data) {
056 int temp;
057 for(int i=0;i<data.length;i++){
058 for(int j=data.length-1;j>i;j--){
059 if(data[j]<data[j-1]){
060 SortUtil.swap(data,j,j-1);
061 }
062 }
063 }
064 }
065
066 }
067
068 //选择排序:
069
070 package org.rut.util.algorithm.support;
071
072 import org.rut.util.algorithm.SortUtil;
073
074 /**
075 * @author treeroot
076 * @since 2006-2-2
077 * @version 1.0
078 */
079 public class SelectionSort implements SortUtil.Sort {
080
081 /**
082 * (non-Javadoc)
083 *
084 * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
085 */
086 public void sort(int[] data) {
087 int temp;
088 for (int i = 0; i < data.length; i++) {
089 int lowIndex = i;
090 for (int j = data.length - 1; j > i; j--) {
091 if (data[j] < data[lowIndex]) {
092 lowIndex = j;
093 }
094 }
095 SortUtil.swap(data,i,lowIndex);
096 }
097 }
098
099 }
100
101 //Shell排序:
102
103 package org.rut.util.algorithm.support;
104
105 import org.rut.util.algorithm.SortUtil;
106
107 /**
108 * @author treeroot
109 * @since 2006-2-2
110 * @version 1.0
111 */
112 public class ShellSort implements SortUtil.Sort{
113
114 /** (non-Javadoc)
115 * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
116 */
117 public void sort(int[] data) {
118 for(int i=data.length/2;i>2;i/=2){
119 for(int j=0;j<i;j++){
120 insertSort(data,j,i);
121 }
122 }
123 insertSort(data,0,1);
124 }
125
126 /**
127 * @param data
128 * @param j
129 * @param i
130 */
131 private void insertSort(int[] data, int start, int inc) {
132 int temp;
133 for(int i=start+inc;i<data.length;i+=inc){
134 for(int j=i;(j>=inc)&&(data[j]<data[j-inc]);j-=inc){
135 SortUtil.swap(data,j,j-inc);
136 }
137 }
138 }
139
140 }
141
142 //快速排序:
143
144 package org.rut.util.algorithm.support;
145
146 import org.rut.util.algorithm.SortUtil;
147
148 /**
149 * @author treeroot
150 * @since 2006-2-2
151 * @version 1.0
152 */
153 public class QuickSort implements SortUtil.Sort{
154
155 /** (non-Javadoc)
156 * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
157 */
158 public void sort(int[] data) {
159 quickSort(data,0,data.length-1);
160 }
161 private void quickSort(int[] data,int i,int j){
162 int pivotIndex=(i+j)/2;
163 //swap
164 SortUtil.swap(data,pivotIndex,j);
165
166 int k=partition(data,i-1,j,data[j]);
167 SortUtil.swap(data,k,j);
168 if((k-i)>1) quickSort(data,i,k-1);
169 if((j-k)>1) quickSort(data,k+1,j);
170
171 }
172 /**
173 * @param data
174 * @param i
175 * @param j
176 * @return
177 */
178 private int partition(int[] data, int l, int r,int pivot) {
179 do{
180 while(data[++l]<pivot);
181 while((r!=0)&&data[--r]>pivot);
182 SortUtil.swap(data,l,r);
183 }
184 while(l<r);
185 SortUtil.swap(data,l,r);
186 return l;
187 }
188
189 }
190 //改进后的快速排序:
191
192 package org.rut.util.algorithm.support;
193
194 import org.rut.util.algorithm.SortUtil;
195
196 /**
197 * @author treeroot
198 * @since 2006-2-2
199 * @version 1.0
200 */
201 public class ImprovedQuickSort implements SortUtil.Sort {
202
203 private static int MAX_STACK_SIZE=4096;
204 private static int THRESHOLD=10;
205 /** (non-Javadoc)
206 * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
207 */
208 public void sort(int[] data) {
209 int[] stack=new int[MAX_STACK_SIZE];
210
211 int top=-1;
212 int pivot;
213 int pivotIndex,l,r;
214
215 stack[++top]=0;
216 stack[++top]=data.length-1;
217
218 while(top>0){
219 int j=stack[top--];
220 int i=stack[top--];
221
222 pivotIndex=(i+j)/2;
223 pivot=data[pivotIndex];
224
225 SortUtil.swap(data,pivotIndex,j);
226
227 //partition
228 l=i-1;
229 r=j;
230 do{
231 while(data[++l]<pivot);
232 while((r!=0)&&(data[--r]>pivot));
233 SortUtil.swap(data,l,r);
234 }
235 while(l<r);
236 SortUtil.swap(data,l,r);
237 SortUtil.swap(data,l,j);
238
239 if((l-i)>THRESHOLD){
240 stack[++top]=i;
241 stack[++top]=l-1;
242 }
243 if((j-l)>THRESHOLD){
244 stack[++top]=l+1;
245 stack[++top]=j;
246 }
247
248 }
249 //new InsertSort().sort(data);
250 insertSort(data);
251 }
252 /**
253 * @param data
254 */
255 private void insertSort(int[] data) {
256 int temp;
257 for(int i=1;i<data.length;i++){
258 for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){
259 SortUtil.swap(data,j,j-1);
260 }
261 }
262 }
263
264 }
265
266 //归并排序:
267
268 package org.rut.util.algorithm.support;
269
270 import org.rut.util.algorithm.SortUtil;
271
272 /**
273 * @author treeroot
274 * @since 2006-2-2
275 * @version 1.0
276 */
277 public class MergeSort implements SortUtil.Sort{
278
279 /** (non-Javadoc)
280 * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
281 */
282 public void sort(int[] data) {
283 int[] temp=new int[data.length];
284 mergeSort(data,temp,0,data.length-1);
285 }
286
287 private void mergeSort(int[] data,int[] temp,int l,int r){
288 int mid=(l+r)/2;
289 if(l==r) return ;
290 mergeSort(data,temp,l,mid);
291 mergeSort(data,temp,mid+1,r);
292 for(int i=l;i<=r;i++){
293 temp[i]=data[i];
294 }
295 int i1=l;
296 int i2=mid+1;
297 for(int cur=l;cur<=r;cur++){
298 if(i1==mid+1)
299 data[cur]=temp[i2++];
300 else if(i2>r)
301 data[cur]=temp[i1++];
302 else if(temp[i1]<temp[i2])
303 data[cur]=temp[i1++];
304 else
305 data[cur]=temp[i2++];
306 }
307 }
308
309 }
310
|