算法实现
间接插入排序
public static void insertSort() { for (int i = 1; i < array.length; i++) { int tempdata = array[i]; int j; for (j = i - 1; j >= 0; j--) { if (array[j] > tempdata) { array[j + 1] = array[j]; } else { break; } } array[j + 1] = tempdata; } }希尔排序
public static void shellSort() { int d = array.length; while (true) { d = d / 2; for (int x = 0; x < d; x++) { for (int i = x + d; i < array.length; i = i + d) { int temp = array[i]; int j; for (j = i - d; j >= 0 && array[j] > temp; j = j - d) { array[j + d] = array[j]; } array[j + d] = temp; } } if (d == 1) { break; } } }冒泡排序
public static void bubbleSort() { int temp; int size = array.length; for (int i = 0; i < size - 1; i++) { for (int j = 0; j < size - 1 - i; j++) { if (array[j] > array[j + 1]) //替换两数地位 { temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } } } }简略抉择排序
public static void simpleChooseSort() { //数组长度 int len = array.length; for (int i = 0; i < len; i++) { //记录以后地位 int position = i; //找出最小的数，并用position指向最小数的地位 for (int j = i + 1; j < len; j++) { if (array[position] > (array[j])) { position = j; }//endif }//endfor //替换最小数array[position]和第i位数的地位 int temp = array[i]; array[i] = array[position]; array[position] = temp; }//endfor }疾速排序
public static void quickSort(int[] array, int start, int end) { if (start < end) { int baseNum = array[start];//选基准值 int midNum;//记录两头值 int i = start; int j = end; do { while ((array[i] < baseNum) && i < end) { i++; } while ((array[j] > baseNum) && j > start) { j--; } if (i <= j) { midNum = array[i]; array[i] = array[j]; array[j] = midNum; i++; j--; } } while (i <= j); if (start < j) { quickSort(array, start, j); } if (end > i) { quickSort(array, i, end); } } }归并排序
static class MergSort { private static void merge(int[] a, int low, int mid, int high) { int[] temp = new int[high - low + 1]; int i = low;// 左指针 int j = mid + 1;// 右指针 int k = 0; // 把较小的数先移到新数组中 while (i <= mid && j <= high) { if (a[i] < a[j]) { temp[k++] = a[i++]; } else { temp[k++] = a[j++]; } } // 把右边残余的数移入数组 while (i <= mid) { temp[k++] = a[i++]; } // 把左边边残余的数移入数组 while (j <= high) { temp[k++] = a[j++]; } // 把新数组中的数笼罩nums数组 for (int k2 = 0; k2 < temp.length; k2++) { a[k2 + low] = temp[k2]; } } public static void mergeSort(int[] a, int low, int high) { int mid = (low + high) / 2; if (low < high) { // 右边 mergeSort(a, low, mid); // 左边 mergeSort(a, mid + 1, high); // 左右归并 merge(a, low, mid, high); } } }算法抉择
1.数据规模较小
- 待排序列根本有序的状况下，能够抉择间接插入排序；
- 对稳定性不作要求宜用简略抉择排序，对稳定性有要求宜用插入或冒泡。
2.数据规模不是很大
- 齐全能够用内存空间，序列杂乱无序，对稳定性没有要求，疾速排序，此时要付出log（N）的额定空间；
- 序列自身可能有序，对稳定性有要求，空间容许下，宜用归并排序。
3.数据规模很大
- 对稳定性有求，则可思考归并排序；
- 对稳定性没要求，宜用堆排序。
4.序列初始根本有序（正序），宜用直接插入，冒泡
总结比拟