算法分类
算法总结
| 排序算法 | 时间复杂度（最好） | 时间复杂度（最坏） | 时间复杂度（平均） | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | ✔️ |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | ✘ |
| 插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | ✔️ |
| 希尔排序 | O(nlogn) | O(nlog^2 n) | O(nlog^2 n) | O(1) | ✘ |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | ✔️ |
| 快速排序 | O(nlogn) | O(n^2) | O(nlogn) | O(logn) | ✘ |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | ✘ |
| 桶排序 | O(n) | O(n^2) | O(n) | O(n*k) | ✔️ |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(n+k) | ✔️ |
| 基数排序 | O(n*k) | O(n*k) | O(n*k) | O(n+k) | ✔️ |
算法实现
冒泡排序
动图：
代码：
public static void bubbleSort(int [] a) { if(a.length <= 1) { return; } for(int i = 0; i < a.length; i++) { boolean flag = true; // 提前结束循环标志位 for(int j = 0; j < a.length-1-i; j++) { if(a[j] > a[j+1]) { int temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; flag = false; // 此次冒泡有数据交换 } } if(flag) { break; } } }
选择排序
动图：
代码：
public static void selectionSort(int [] a) { if(a.length <= 1) { return; } for(int i=0; i<n-1; i++) { // 查找最小值 int minIndex = i; for(int j = i+1; j < n; j++) { if(a[j] < a[minIndex]) { minIndex = j; } } // 交换 if(minIndex != i) { int temp = a[i]; a[i] = a[minIndex]; a[minIndex] = temp; } } }
插入排序
动图：
代码：
public static void insertionSort(int [] a) { if(a.length <= 1) { return; } for (int i = 1; i < arr.length; i++) { int value = a[i]; int j = i - 1; // 查找要插入的位置并移动数据 for (; j >= 0; j--) { if (a[j] > value) { a[j+1] = a[j]; } else { break; } } if(j+1 != i) { a[j+1] = value; } }
希尔排序
动图：
代码：
public static void shellSort(int [] arr) { if(arr.length <= 1) { return; } int gap = 1; while (gap < arr.length) { gap = gap * 3 + 1; } while (gap > 0) { for (int i = gap; i < arr.length; i++) { int tmp = arr[i]; int j = i - gap; while (j >= 0 && arr[j] > tmp) { arr[j + gap] = arr[j]; j -= gap; } arr[j + gap] = tmp; } gap = (int) Math.floor(gap / 3); } }
归并排序
动图：
代码：
// 归并排序算法, a是数组，n表示数组大小 public static void mergeSort(int[] a, int n) { mergeSortInternally(a, 0, n-1); } // 递归调用函数 private static void mergeSortInternally(int[] a, int p, int r) { // 递归终止条件 if (p >= r) return; // 取p到r之间的中间位置q,防止（p+r）的和超过int类型最大值 int q = p + (r - p)/2; // 分治递归 mergeSortInternally(a, p, q); mergeSortInternally(a, q+1, r); // 将A[p...q]和A[q+1...r]合并为A[p...r] merge(a, p, q, r); } private static void merge(int[] a, int p, int q, int r) { int i = p; int j = q+1; int k = 0; // 初始化变量i, j, k int[] tmp = new int[r-p+1]; // 申请一个大小跟a[p...r]一样的临时数组 while (i<=q && j<=r) { if (a[i] <= a[j]) { tmp[k++] = a[i++]; // i++等于i:=i+1 } else { tmp[k++] = a[j++]; } } // 判断哪个子数组中有剩余的数据 int start = i; int end = q; if (j <= r) { start = j; end = r; } // 将剩余的数据拷贝到临时数组tmp while (start <= end) { tmp[k++] = a[start++]; } // 将tmp中的数组拷贝回a[p...r] for (i = 0; i <= r-p; ++i) { a[p+i] = tmp[i]; } }
快速排序
动图：
代码：
// 快速排序，a是数组，n表示数组的大小 public static void quickSort(int[] a, int n) { quickSortInternally(a, 0, n-1); } // 快速排序递归函数，p,r为下标 private static void quickSortInternally(int[] a, int p, int r) { if (p >= r) return; int q = partition(a, p, r); // 获取分区点 quickSortInternally(a, p, q-1); quickSortInternally(a, q+1, r); } private static int partition(int[] a, int p, int r) { int pivot = a[r]; int i = p; for(int j = p; j < r; ++j) { if (a[j] < pivot) { if (i == j) { ++i; } else { int tmp = a[i]; a[i++] = a[j]; a[j] = tmp; } } } int tmp = a[i]; a[i] = a[r]; a[r] = tmp; System.out.println("i=" + i); return i; }
堆排序
动图：
代码：
public class HeapSort implements IArraySort { @Override public int[] sort(int[] sourceArray) throws Exception { // 对 arr 进行拷贝，不改变参数内容 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); int len = arr.length; buildMaxHeap(arr, len); for (int i = len - 1; i > 0; i--) { swap(arr, 0, i); len--; heapify(arr, 0, len); } return arr; } private void buildMaxHeap(int[] arr, int len) { for (int i = (int) Math.floor(len / 2); i >= 0; i--) { heapify(arr, i, len); } } private void heapify(int[] arr, int i, int len) { int left = 2 * i + 1; int right = 2 * i + 2; int largest = i; if (left < len && arr[left] > arr[largest]) { largest = left; } if (right < len && arr[right] > arr[largest]) { largest = right; } if (largest != i) { swap(arr, i, largest); heapify(arr, largest, len); } } private void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }
桶排序
动图：
代码：
public class BucketSort implements IArraySort { private static final InsertSort insertSort = new InsertSort(); @Override public int[] sort(int[] sourceArray) throws Exception { // 对 arr 进行拷贝，不改变参数内容 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); return bucketSort(arr, 5); } private int[] bucketSort(int[] arr, int bucketSize) throws Exception { if (arr.length == 0) { return arr; } int minValue = arr[0]; int maxValue = arr[0]; for (int value : arr) { if (value < minValue) { minValue = value; } else if (value > maxValue) { maxValue = value; } } int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1; int[][] buckets = new int[bucketCount][0]; // 利用映射函数将数据分配到各个桶中 for (int i = 0; i < arr.length; i++) { int index = (int) Math.floor((arr[i] - minValue) / bucketSize); buckets[index] = arrAppend(buckets[index], arr[i]); } int arrIndex = 0; for (int[] bucket : buckets) { if (bucket.length <= 0) { continue; } // 对每个桶进行排序，这里使用了插入排序 bucket = insertSort.sort(bucket); for (int value : bucket) { arr[arrIndex++] = value; } } return arr; } // 自动扩容，并保存数据 private int[] arrAppend(int[] arr, int value) { arr = Arrays.copyOf(arr, arr.length + 1); arr[arr.length - 1] = value; return arr; } }
计数排序
动图：
代码：
public class CountingSort { // 计数排序，a是数组，n是数组大小。假设数组中存储的都是非负整数。 public static void countingSort(int[] a, int n) { if (n <= 1) return; // 查找数组中数据的范围 int max = a[0]; for (int i = 1; i < n; ++i) { if (max < a[i]) { max = a[i]; } } // 申请一个计数数组c，下标大小[0,max] int[] c = new int[max + 1]; for (int i = 0; i < max + 1; ++i) { c[i] = 0; } // 计算每个元素的个数，放入c中 for (int i = 0; i < n; ++i) { c[a[i]]++; } // 依次累加 for (int i = 1; i < max + 1; ++i) { c[i] = c[i-1] + c[i]; } // 临时数组r，存储排序之后的结果 int[] r = new int[n]; // 计算排序的关键步骤了，有点难理解 for (int i = n - 1; i >= 0; --i) { int index = c[a[i]]-1; r[index] = a[i]; c[a[i]]--; } // 将结果拷贝会a数组 for (int i = 0; i < n; ++i) { a[i] = r[i]; } } }
基数排序
动图：
代码：
public class RadixSort implements IArraySort { @Override public int[] sort(int[] sourceArray) throws Exception { // 对 arr 进行拷贝，不改变参数内容 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); int maxDigit = getMaxDigit(arr); return radixSort(arr, maxDigit); } // 获取最高位数 private int getMaxDigit(int[] arr) { int maxValue = getMaxValue(arr); return getNumLenght(maxValue); } private int getMaxValue(int[] arr) { int maxValue = arr[0]; for (int value : arr) { if (maxValue < value) { maxValue = value; } } return maxValue; } protected int getNumLenght(long num) { if (num == 0) { return 1; } int lenght = 0; for (long temp = num; temp != 0; temp /= 10) { lenght++; } return lenght; } private int[] radixSort(int[] arr, int maxDigit) { int mod = 10; int dev = 1; for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) { // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10) int[][] counter = new int[mod * 2][0]; for (int j = 0; j < arr.length; j++) { int bucket = ((arr[j] % mod) / dev) + mod; counter[bucket] = arrayAppend(counter[bucket], arr[j]); } int pos = 0; for (int[] bucket : counter) { for (int value : bucket) { arr[pos++] = value; } } } return arr; } private int[] arrayAppend(int[] arr, int value) { arr = Arrays.copyOf(arr, arr.length + 1); arr[arr.length - 1] = value; return arr; } }
