这里总结下各种排序算法的java实现
冒泡排序
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | public class BubbleSort { public static int [] bubbleSort( int [] array) { if (array == null ) { return null ; } for ( int i = 0 ; i < array.length; i++) { for ( int j = i + 1 ; j < array.length; j++) { if (array[i] > array[j]) { array[i] = array[i] + array[j]; array[j] = array[i] - array[j]; array[i] = array[i] - array[j]; } } } return array; } } |
插入排序
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | public class InsertSort { public static int [] insertSort( int [] array) { if (array == null ) { return null ; } for ( int i = 1 ; i < array.length; i++) { for ( int j = i; (j > 0 ) && (array[j] < array[j - 1 ]); j--) { SortUtils.swap(array, j, j - 1 ); } } return array; } } |
选择排序
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | public class SelectionSort { public static int [] selectionSort( int [] array) { if (array == null ) { return null ; } for ( int i = 0 ; i < array.length; i++) { int lowIndex = i; for ( int j = array.length - 1 ; j > i; j--) { if (array[j] < array[lowIndex]) { lowIndex = j; } } SortUtils.swap(array, i, lowIndex); } return array; } } |
Shell排序
| 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 | public class ShellSort { public static int [] shellSort( int [] array) { if (array == null ) { return null ; } for ( int i = array.length / 2 ; i > 2 ; i /= 2 ) { for ( int j = 0 ; j < i; j++) { insertSort(array, j, i); } } insertSort(array, 0 , 1 ); return array; } private static void insertSort( int [] array, int start, int inc) { for ( int i = start + inc; i < array.length; i += inc) { for ( int j = i; (j >= inc) && (array[j] < array[j - inc]); j -= inc) { SortUtils.swap(array, j, j - inc); } } } } |
快速排序
| 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 | public class QKSort { public static int [] quickSort( int [] array) { if (array != null ) { return quickSort(array, 0 , array.length - 1 ); } return null ; } private static int [] quickSort( int [] array, int beg, int end) { if (beg >= end || array == null ) { return null ; } int p = partition(array, beg, end); quickSort(array, beg, p - 1 ); quickSort(array, p + 1 , end); return array; } /** * 找到分界点 * array * beg * end * */ private static int partition( int [] array, int beg, int end) { int last = array[end]; int i = beg - 1 ; for ( int j = beg; j <= end - 1 ; j++) { if (array[j] <= last) { i++; if (i != j) { array[i] = array[i] ^ array[j]; array[j] = array[i] ^ array[j]; array[i] = array[i] ^ array[j]; } } } if ((i + 1 ) != end) { array[i + 1 ] = array[i + 1 ] ^ array[end]; array[end] = array[i + 1 ] ^ array[end]; array[i + 1 ] = array[i + 1 ] ^ array[end]; } return i + 1 ; } } |
堆排序
| 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 | public class HeapSort { public static int [] heapSort( int [] array) { if (array == null ) { return null ; } MaxHeap h = new MaxHeap(); h.init(array); for ( int i = 0 ; i < array.length; i++) { h.remove(); } System.arraycopy(h.queue, 1 , array, 0 , array.length); return array; } private static class MaxHeap { void init( int [] data) { this .queue = new int [data.length + 1 ]; for ( int i = 0 ; i < data.length; i++) { queue[++size] = data[i]; fixUp(size); } } private int size = 0 ; private int [] queue; public int get() { return queue[ 1 ]; } public void remove() { SortUtils.swap(queue, 1 , size--); fixDown( 1 ); } // fixdown private void fixDown( int k) { int j; while ((j = k << 1 ) <= size) { if (j < size && queue[j] < queue[j + 1 ]) { j++; } // 不用交换 if (queue[k] > queue[j]) { break ; } SortUtils.swap(queue, j, k); k = j; } } private void fixUp( int k) { while (k > 1 ) { int j = k >> 1 ; if (queue[j] > queue[k]) { break ; } SortUtils.swap(queue, j, k); k = j; } } } } |
归并排序
| 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 | public class MergeSort { public static int [] mergeSort( int [] array) { if (array == null ) { return null ; } int [] temp = new int [array.length]; return mergeSort(array, temp, 0 , array.length - 1 ); } private static int [] mergeSort( int [] array, int [] temp, int l, int r) { int mid = (l + r) / 2 ; if (l == r) { return null ; } mergeSort(array, temp, l, mid); mergeSort(array, temp, mid + 1 , r); for ( int i = l; i <= r; i++) { temp[i] = array[i]; } int i1 = l; int i2 = mid + 1 ; for ( int cur = l; cur <= r; cur++) { if (i1 == mid + 1 ) { array[cur] = temp[i2++]; } else if (i2 > r) { array[cur] = temp[i1++]; } else if (temp[i1] < temp[i2]) { array[cur] = temp[i1++]; } else { array[cur] = temp[i2++]; } } return array; } } |
归并排序(改进)
| 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 | public class MergeSortImproved { private static final int THRESHOLD = 10 ; public static int [] mergeSort( int [] array) { if (array == null ) { return null ; } int [] temp = new int [array.length]; return mergeSort(array, temp, 0 , array.length - 1 ); } private static int [] mergeSort( int [] array, int [] temp, int l, int r) { int i, j, k; int mid = (l + r) / 2 ; if (l == r) { return null ; } if ((mid - l) >= THRESHOLD) { mergeSort(array, temp, l, mid); } else { insertSort(array, l, mid - l + 1 ); } if ((r - mid) > THRESHOLD) { mergeSort(array, temp, mid + 1 , r); } else { insertSort(array, mid + 1 , r - mid); } for (i = l; i <= mid; i++) { temp[i] = array[i]; } for (j = 1 ; j <= r - mid; j++) { temp[r - j + 1 ] = array[j + mid]; } int a = temp[l]; int b = temp[r]; for (i = l, j = r, k = l; k <= r; k++) { if (a < b) { array[k] = temp[i++]; a = temp[i]; } else { array[k] = temp[j--]; b = temp[j]; } } return array; } private static void insertSort( int [] array, int start, int len) { for ( int i = start + 1 ; i < start + len; i++) { for ( int j = i; (j > start) && array[j] < array[j - 1 ]; j--) { SortUtils.swap(array, j, j - 1 ); } } } } |