这里总结下各种排序算法的java实现
冒泡排序 public class BubbleSort {publicstaticint[] bubbleSort(int[] array) { if(array == null) { returnnull; } for(inti = 0; i < array.length; i++) { for(intj = 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]; } } } returnarray; } }
插入排序 public class InsertSort {publicstaticint[] insertSort(int[] array) { if(array == null) { returnnull; } for(inti = 1; i < array.length; i++) { for(intj = i; (j > 0) && (array[j] < array[j - 1]); j--) { SortUtils.swap(array, j, j - 1); } } returnarray; } }
选择排序
public class SelectionSort {publicstaticint[] selectionSort(int[] array) { if(array == null) { returnnull; } for(inti = 0; i < array.length; i++) { intlowIndex = i; for(intj = array.length - 1; j > i; j--) { if(array[j] < array[lowIndex]) { lowIndex = j; } } SortUtils.swap(array, i, lowIndex); } returnarray; } }
?
Shell排序 public class ShellSort {publicstaticint[] shellSort(int[] array) { if(array == null) { returnnull; } for(inti = array.length / 2; i > 2; i /= 2) { for(intj = 0; j < i; j++) { insertSort(array, j, i); } } insertSort(array,0,1); returnarray; } privatestaticvoidinsertSort(int[] array, intstart,intinc) { for(inti = start + inc; i < array.length; i += inc) { for(intj = i; (j >= inc) && (array[j] < array[j - inc]); j -= inc) { SortUtils.swap(array, j, j - inc); } } } }
?
快速排序 public class QKSort {publicstaticint[] quickSort(int[] array) { if(array != null) { returnquickSort(array,0, array.length - 1); } returnnull; } privatestaticint[] quickSort(int[] array, intbeg,intend) { if(beg >= end || array == null) { returnnull; } intp = partition(array, beg, end); quickSort(array, beg, p - 1); quickSort(array, p + 1, end); returnarray; } /** * 找到分界点 * @param array * @param beg * @param end * @return */ privatestaticintpartition(int[] array, intbeg,intend) { intlast = array[end]; inti = beg - 1; for(intj = 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]; } returni + 1; } }
堆排序
public class HeapSort {publicstaticint[] heapSort(int[] array) { if(array == null) { returnnull; } MaxHeap h = newMaxHeap(); h.init(array); for(inti = 0; i < array.length; i++) { h.remove(); } System.arraycopy(h.queue,1, array, 0, array.length); returnarray; } privatestaticclassMaxHeap { voidinit(int[] data) { this.queue = newint[data.length + 1]; for(inti = 0; i < data.length; i++) { queue[++size] = data[i]; fixUp(size); } } privateintsize = 0; privateint[] queue; publicintget() { returnqueue[1]; } publicvoidremove() { SortUtils.swap(queue,1, size--); fixDown(1); } // fixdown privatevoidfixDown(intk) { intj; 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; } } privatevoidfixUp(intk) { while(k > 1) { intj = k >> 1; if(queue[j] > queue[k]) { break; } SortUtils.swap(queue, j, k); k = j; } } } }
归并排序
public class MergeSort {publicstaticint[] mergeSort(int[] array) { if(array == null) { returnnull; } int[] temp = newint[array.length]; returnmergeSort(array, temp, 0, array.length - 1); } privatestaticint[] mergeSort(int[] array, int[] temp, intl,intr) { intmid = (l + r) / 2; if(l == r) { returnnull; } mergeSort(array, temp, l, mid); mergeSort(array, temp, mid + 1, r); for(inti = l; i <= r; i++) { temp[i] = array[i]; } inti1 = l; inti2 = mid + 1; for(intcur = l; cur <= r; cur++) { if(i1 == mid + 1) { array[cur] = temp[i2++]; }elseif(i2 > r) { array[cur] = temp[i1++]; }elseif(temp[i1] < temp[i2]) { array[cur] = temp[i1++]; }else{ array[cur] = temp[i2++]; } } returnarray; } }
归并排序(改进)
public class MergeSortImproved {privatestaticfinalint THRESHOLD = 10; publicstaticint[] mergeSort(int[] array) { if(array == null) { returnnull; } int[] temp = newint[array.length]; returnmergeSort(array, temp, 0, array.length - 1); } privatestaticint[] mergeSort(int[] array, int[] temp, intl,intr) { inti, j, k; intmid = (l + r) / 2; if(l == r) { returnnull; } 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]; } inta = temp[l]; intb = 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]; } } returnarray; } privatestaticvoidinsertSort(int[] array, intstart,intlen) { for(inti = start + 1; i < start + len; i++) { for(intj = i; (j > start) && array[j] < array[j - 1]; j--) { SortUtils.swap(array, j, j - 1); } } } }