Java常用排序算法

算法实现 直接插入排序

public static void insertSort() { for (int i = 1; i < array.length; i++) { int tempdata = https://www.it610.com/article/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.数据规模较小
  • 待排序列基本有序的情况下,可以选择直接插入排序;
  • 对稳定性不作要求宜用简单选择排序,对稳定性有要求宜用插入或冒泡。
【Java常用排序算法】2.数据规模不是很大
  • 完全可以用内存空间,序列杂乱无序,对稳定性没有要求,快速排序,此时要付出log(N)的额外空间;
  • 序列本身可能有序,对稳定性有要求,空间允许下,宜用归并排序。
3.数据规模很大
  • 对稳定性有求,则可考虑归并排序;
  • 对稳定性没要求,宜用堆排序。
4.序列初始基本有序(正序),宜用直接插入,冒泡
总结比较
Java常用排序算法
文章图片

    推荐阅读