`

选择,插入,冒泡排序

J# 
阅读更多
package algorithm;

public class SortAlgorithm {

	private void bubbleSort(int[] numList){//冒泡排序,从前往后扫描,比较相邻两个数的大小,如果发现逆序进行交换
		int out,in;
		for(out = numList.length-1;out>1;out--){//从后往前
			for(in= 0;in<out;in++){
				if(numList[in]>numList[in+1]){ //当前项大于后一项,交换
					int temp = numList[in];
					numList[in] = numList[in+1];
					numList[in+1] = temp;
					
				}
			}
		}
	}
	
	private void insertSort(int[] numList){//插入排序,将待排序的数据插入到有序数列中
		
		int out,in;
//		从out处分开数列
		for(out=1;out<numList.length;out++){
			int temp = numList[out]; // 待排序的数据
			in = out-1; //待排序数据的有序数列的最后一个数据
			
			while(in>0&&numList[in]>temp){// 当待排序的数据小于数列值时
				numList[in+1]=numList[in]; //数列向右移一位
				--in; //指针向左移一位
			}
			numList[in+1] = temp; //插入待排序的数据
		}
		
	}
	
	private void selectionSort(int[] numList){//选择排序
		int out,in,temp,min;
		
		for(out = 0;out<numList.length-1;out++){
			min = out;
			
			for(in= out+1;in<numList.length;in++){
				if(numList[in]<numList[min]){
					min = in;
				}
//				交换
				temp = numList[out];
				numList[out] = numList[min];
				numList[min] = numList[out];
			}
			
			
		}
		
	}
	private void display(int[] numList){
		for(int j = 0;j<numList.length;j++){
			System.out.print(numList[j]+" ");
		}
		System.out.println();
	}
	
	
	
	public static void main(String[] args){
		SortAlgorithm sort = new SortAlgorithm();
		int[] numList = new int[]{2,3,56,34,23,89,50};
		System.out.print("未排序前的数列");
		sort.display(numList);
		
		long begin =System.currentTimeMillis();
		sort.bubbleSort(numList);
		long end = System.currentTimeMillis();
		System.out.print("冒泡排序用时"+(end-begin)+"排序后:");
		sort.display(numList);
		
		
		begin =System.currentTimeMillis();
		sort.selectionSort(numList);
		end = System.currentTimeMillis();
		System.out.print("选择排序用时"+(end-begin)+"排序后:");
		sort.display(numList);
		
		
		begin =System.currentTimeMillis();
		sort.insertSort(numList);
		end = System.currentTimeMillis();
		System.out.print("插入排序用时"+(end-begin)+"排序后:");
		sort.display(numList);
	}
}



归并算法:
01.import java.util.Arrays;   
02.import java.util.Comparator;   
03.public class MergeSort {   
04.    public static <T> void merge(T[] a, int p, int q, int r,   
05.            Comparator<? super T> c) {   
06.        T[] left = Arrays.copyOfRange(a, p, q);   
07.        T[] right = Arrays.copyOfRange(a, q, r);   
08.        int indexLeft = 0;   
09.        int indexRight = 0;   
10.        for (int i = p; i < r; i++) {   
11.            if (indexLeft >= left.length) {   
12.                break;   
13.            }   
14.            if (indexRight >= right.length) {   
15.                System   
16.                        .arraycopy(left, indexLeft, a, i, left.length   
17.                                - indexLeft);   
18.                break;   
19.            }   
20.            if (c.compare(left[indexLeft], right[indexRight]) < 0) {   
21.                a[i] = left[indexLeft++];   
22.            } else {   
23.                a[i] = right[indexRight++];   
24.            }   
25.        }   
26.    }   
27.    public static <T> void mergeSort(T[] a, int p, int r,   
28.            Comparator<? super T> c) {   
29.        if (p + 1 < r) {   
30.            int q = (p + r) / 2;   
31.            mergeSort(a, p, q, c);   
32.            mergeSort(a, q + 1, r, c);   
33.            merge(a, p, q, r, c);   
34.        }   
35.    }   
36.    public static <T> void mergeSort(T[] a, Comparator<? super T> c) {   
37.        mergeSort(a, 0, a.length, c);   
38.    }   
39.    public static void main(String[] args) {   
40.        // merge's test   
41.        System.out.println("merge method test");   
42.        Integer[] tempMerge = new Integer[] { 1, 4, 7, 11, 14, 17, 2, 4, 6, 8,   
43.                10, 20, 30, 40 };   
44.        merge(tempMerge, 0, 6, tempMerge.length, new Comparator<Integer>() {   
45.            @Override  
46.            public int compare(Integer o1, Integer o2) {   
47.                return o1 - o2;   
48.            }   
49.        });   
50.        for (int i : tempMerge) {   
51.            System.out.print(i + " ");   
52.        }   
53.        System.out.println();   
54.        // mergeSort's test   
55.        System.out.println("mergeSort method test");   
56.        Integer[] tempMergeSoft = new Integer[] { 5, 2, 4, 6, 1, 3, 2, 6 };   
57.        mergeSort(tempMergeSoft, new Comparator<Integer>() {   
58.            @Override  
59.            public int compare(Integer o1, Integer o2) {   
60.                return o1 - o2;   
61.            }   
62.        });   
63.        for (int i : tempMergeSoft) {   
64.            System.out.print(i + " ");   
65.        }   
66.        System.out.println();   
67.    }   
68.}  


另外:判断一个数是完全平方数,使用Math.floor(Math.sqrt(n))==Math.sqrt(n)
如Math.sqrt(9)==Math.floor(Math.sqrt(9)返回true,因为3.0==3.
回文数即对称数字,可以使用栈来判断。入栈和出栈顺序一样,或者直接进行前后数字的比较

判断一个数是否是2的次幂,用if(((d&(d-1))==0)&&(d!=0))

java中有栈Stack的实现,下面是栈的类继承结构;
类 Stack<E>
java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractList<E>
          java.util.Vector<E>
              java.util.Stack<E>
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics