直接插入排序
1.从第一个元素开始，该元素可以认为已经被排序
2.取下一个元素tem，从已排序的元素序列从后往前扫描
3.如果该元素大于tem，则将该元素移到下一位
4.重复步骤3，直到找到已排序元素中小于等于tem的元素
5.tem插入到该元素的后面，如果已排序所有元素都大于tem，则将tem插入到下标为0的位置
例如：从数字5开始排序
时间复杂度：最坏情况下为O(N*N)，此时待排序列为逆序，或者说接近逆序
最好情况下为O(N)，此时待排序列为升序，或者说接近升序。
空间复杂度：O(1)
代码：
public static void main(String[] args) { int[] arr = {5, 2, 8, 3, 1, 6}; System.out.println("Before sorting: " + Arrays.toString(arr)); insertionSort(arr); System.out.println("After sorting: " + Arrays.toString(arr)); } public static void insertionSort(int[] arr) { int n = arr.length; for (int i = 1; i < n; ++i) { int key = arr[i]; for(int j = i -1 ;j>=0;j--){ //如果当前元素小于他前边的那个元素，当前这个元素目前所在位置放置他前一个元素 if(key<arr[j]){ arr[j+1] = arr[j]; arr[j] = key; }else { break; } } } }
希尔排序
1.先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作…
2.当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。
时间复杂度平均：O(N^1.3)
空间复杂度：O(1)
代码：
public static void main(String[] args) { int[] a = {1,2,5,4,3,9}; ShellSort(a); } public static void ShellSort(int[] array) { int n = array.length; int inc;//希尔增量 //这里采用朴素希尔增量，就是每次增量都是原来的一半，直到增量为1为止 for (inc = n / 2; inc >= 1; inc = inc / 2) {//每一次循环都通过不断缩短增量达到排序的效果 //在一次循环内，inc的值是固定的 //下面的内容和插入排序的原理是一样的,只不过每个待排序元素的间隔是inc for (int i = inc; i < n; i++) {//i为什么是从inc开始,而不是从0开始? //因为插入排序中把排序元素分为两组，A组为已排好序的，B组为未排好序要插入的 //A组开始时往往是第一个元素（0），那么B组的第一个元素就是整个待拍序列的第二个元素了（inc） int temp = array[i];//temp存储要插入的值 int j; for (j = i-inc; j >= 0 && array[j] > temp; j = j - inc) {//j从i-inc开始往前遍历，每一步的距离是inc array[j+inc] = array[j];//如果当前遍历到的元素(这里说的遍历到的元素是(array[j])比待插入元素temp小， //这个元素往后移动一位，后边的元素被元素覆盖 //一旦不满足条件，1.说明要么遍历到元素比temp小，这个时候所有比temp大的元素都后移完了 //2.遍历到头了，此时第一个元素就是要插入的地方 } array[j+inc] = temp; //那么此时array[j+inc]也就是要插入的地方，把temp插入进去 System.out.println(Arrays.toString(array)); } } // System.out.println(Arrays.toString(array)); }
直接选择排序
每次从待排序列中选出一个最小值，然后放在序列的起始位置，直到全部待排数据排完即可。
实际上，我们可以一趟选出两个值，一个最大值一个最小值，然后将其放在序列开头和末尾，这样可以使选择排序的效率快一倍。
public static void main(String[] args) { int arrLength = 8; //测试数组的长度 /* * 获得随机arrLength个数的数组 */ int[] arr = new int[arrLength]; for(int i = 0;i < arrLength;i++){ //随机情况 arr[i] = (int) (Math.random() * arrLength); } //排序前的输出 for(int a:arr){ System.out.print(a+" "); } System.out.println(); choiceSort(arr); //排序后的输出 for(int a:arr){ System.out.print(a+" "); } } /** * 直接选择排序，每次选最小的放到最前 */ public static void choiceSort(int[] arr){ if(arr == null || arr.length < 1){ return; } int min = 0; int temp; /*只需要进行 n - 1 轮选择*/ for(int i = 0;i<arr.length - 1;i++){ min = i; //初始化当前最小的 for(int j = i + 1;j<arr.length;j++){ if(arr[min] > arr[j]){ min=j; //记住最小元素下标 } } //一轮后，当最小元素的下标不为i时交换位置 if(min != i){ temp = arr[i]; arr[i] = arr[min]; arr[min] = temp; } System.out.println(Arrays.toString(arr)); } }
堆排序：
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。
public static void heapSort(int[] arr) { if (arr == null || arr.length <= 1) return; // 建堆。 buildHeap(arr); int len = arr.length; while (len > 1) { // 把堆顶和最后一个元素交换。 swap(arr, 0, len - 1); // 交换完之后，逻辑上去掉最后一个元素。 len--; // 重新调整堆的顺序。 heapfy(arr, 0 , len); // 把每一趟排序的结果也输出一下。 print(arr); } } private static void buildHeap(int[] arr) { // 最后一个非叶子结点：2i + 1 >= arr.length --> i >= (arr.length - 1) / 2 for (int i = (arr.length - 1) / 2 - 1; i >= 0; i--) { heapfy(arr, i, arr.length); } } // 调整堆的顺序，保持大顶堆。 private static void heapfy(int[] arr, int i, int len) { while (true) { int maxPostion = i; int leftChild = 2 * i + 1; // 左孩子索引。 int rightChild = 2 * i + 2; // 右孩子索引。 // 若左孩子大于最大值，则更新最大值。 if (leftChild < len && arr[leftChild] > arr[maxPostion]) { maxPostion = leftChild; } // 若右孩子大于最大值，则更新最大值。 if (rightChild < len && arr[rightChild] > arr[maxPostion]) { maxPostion = rightChild; } if (maxPostion == i) { break; // 若已经是大顶堆了，则退出循环。 } else { swap(arr, i, maxPostion); // 若不是大顶堆，则交换位置。 i = maxPostion; } } } private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] =temp; } public static void main(String[] args) { int[] arr = {6, 9, 1, 4, 5, 8, 7, 0, 2, 3}; System.out.print("排序前: "); print(arr); heapSort(arr); System.out.print("排序后: "); print(arr); } // 打印数组 public static void print(int[] arr) { if (arr == null) return; for(int i : arr) { System.out.print(i + " "); } System.out.println(); }
冒泡排序
冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越大\小的元素会经由交换慢慢"浮"到数列的顶端。
算法步骤
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
public static void main(String[] args) throws Exception { int[] arr = {11,44,23,67,88,65,34,48,9,12}; sort(arr); } public static int[] sort(int[] sourceArray) throws Exception { // 对 arr 进行拷贝，不改变参数内容 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); //遍历整个数组 for (int i = 1; i < arr.length; i++) { // 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。 boolean flag = true; for (int j = 0; j < arr.length - i; j++) { if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; flag = false; } } if (flag) { break; } System.out.println(Arrays.toString(arr)); } return arr; }
基数排序
public class BasicData { public static void radixSort(int[] arr) { // 找到数组中的最大值，确定排序的轮数 int max = Arrays.stream(arr).max().getAsInt(); // 对每个位数进行排序 for (int exp = 1; max / exp > 0; exp *= 10) { countingSort(arr, exp); } } private static void countingSort(int[] arr, int exp) { int n = arr.length; int[] output = new int[n]; int[] count = new int[10]; // 统计每个桶中元素的个数 for (int i = 0; i < n; i++) { int index = (arr[i] / exp) % 10; count[index]++; } // 将count[i]更新为该位数小于等于i的元素个数 for (int i = 1; i < 10; i++) { count[i] += count[i - 1]; } // 从后向前遍历原数组，根据当前位数将元素放入对应的桶中 for (int i = n - 1; i >= 0; i--) { int index = (arr[i] / exp) % 10; output[count[index] - 1] = arr[i]; count[index]--; } // 将排序好的数组复制回原数组 System.arraycopy(output, 0, arr, 0, n); } public static void main(String[] args) { int[] arr = {170, 45, 75, 90, 802, 24, 2, 66}; System.out.println("Original array: " + Arrays.toString(arr)); radixSort(arr); System.out.println("Sorted array: " + Arrays.toString(arr)); }
