基本排序算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
        /**
	 * 插入排序法
	 * @param a
	 */
	static void insertionSort( ArrayList<Integer> a){
		int j;
		for( int p = 1; p < a.size(); p++ ){
			Integer tmp = a.get(p);
			for( j = p; j > 0 && tmp.compareTo(a.get(j - 1)) < 0; j-- ) {
				System.out.println("change " + a.get(j) + "  " + a.get(j - 1));
				a.set(j, a.get(j - 1));
			}
			a.set(j, tmp);
			System.out.println(" p = " + p + " change " + a.get(j) + "  " + tmp);
		}
	}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
       /**
	 * 希尔排序
	 * @param a
	 */
	static void shellSort( ArrayList<Integer> a ){
		int j;
		for( int gap = a.size() / 2; gap > 0; gap /= 2 ){
			for( int i = gap; i < a.size(); i++ ){
				Integer tmp = a.get(i);
				for( j = i; j >= gap && tmp.compareTo(a.get(j - gap)) < 0; j-=gap ){
					System.out.println("change " + a.get(j) + "  " + a.get(j - gap));
					a.set(j, a.get(j - gap));
				}
				System.out.println(" i = " + i + " change " + a.get(j) + "  " + tmp);
				a.set(j, tmp);
			}
			System.out.println(" gap  = " + gap);
		}
	}

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
       /**
	 * 归并排序
	 * @param a
	 * @param tmpArray
	 * @param left
	 * @param right
	 */
	static void mergeSort( ArrayList<Integer> a, ArrayList<Integer> tmpArray, int left, int right ){
		if( left < right ){
			int center = ( left + right ) / 2;
			mergeSort(a, tmpArray, left, center);
			mergeSort(a, tmpArray, center + 1, right);
			merge(a, tmpArray, left, center + 1, right);
		}
	}
	
	static void merge( ArrayList<Integer> a, ArrayList<Integer> tmpArray, int leftPos, int rightPos, int rightEnd ){
		int leftEnd = rightPos - 1;
		int tmpPos = leftPos;
		int numElements = rightEnd - leftPos + 1;
		
		while( leftPos <= leftEnd && rightPos <= rightEnd ){
			if( a.get(leftPos).compareTo(a.get(rightPos)) <= 0 ){
				tmpArray.set(tmpPos++, a.get(leftPos++));
			}
			else{
				tmpArray.set(tmpPos++, a.get(rightPos++));
			}
		}
		
		while( leftPos <= leftEnd ){
			tmpArray.set(tmpPos++, a.get(leftPos++));
		}
		
		while( rightPos <= rightEnd ){
			tmpArray.set(tmpPos++, a.get(rightPos++));
		}
		
		for( int i = 0; i < numElements; i++, rightEnd--){
			a.set(rightEnd, tmpArray.get(rightEnd));
		}
	}