|
相关术语 稳定性：如果a=b且a在b之前，经排序后a仍在b之前。 时间复杂度：对排序数据的总操作次数。反应排序元素个数n变化时，操作次数呈现什么变化。 空间复杂度：执行算法时所需的存储空间大小。 一、冒泡排序（Bubble Sort） 重复遍历要排序的数列，依次比较相邻的两个元素，调整这两个元素的顺序，直到数列整体有序。 时间复杂度：O(n2)，空间复杂度：O(1)，稳定性：稳定 public void bubble(int arr[]) { for (int i = 0; i < arr.length - 1; i++) { for (int j = i; j < arr.length - i - 1; j++) { if (arr[j] > arr[j + 1]) { int swap = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = swap; } } } } 二、快速排序（Quick Sort） 通过一次排序将待排数列分为两个部分，其中一部分元素值比另一部分小，然后继续对这两部分执行上述操作，以达到整体有序。 时间复杂度：O(nlog2n)，空间复杂度：O(nlog2n)，稳定性：不稳定 class Quick { public void quick(int[] arr, int left, int right) { if (arr == null) { return; } if (left < right) { int index = partition(arr, left, right); quick(arr, left, index - 1); quick(arr, index + 1, right); } } public int partition(int[] arr, int left, int right) { // 选最左边的元素为基准pivot int pivot = left, index = pivot + 1; for (int i = index; i <= right; i++) { if (arr < arr[pivot]) { swap(arr, i, index); index++; } } swap(arr, pivot, index - 1); return index - 1; } public void swap(int[] arr, int i, int j) { int temp = arr; arr = arr[j]; arr[j] = temp; } } 三、选择排序（Selection Sort） 在未排序的数列中找到最小（大）的数，放到已排序数列的最后，直到未排序数列为空。 时间复杂度：O(n2)，空间复杂度：O(1)，稳定性：不稳定 public void select(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { int index = i; for (int j = i + 1; j < arr.length; j++) { if (arr[index] > arr[j]) { int temp = arr[j]; arr[j] = arr; arr = temp; } } } } 四、插入排序（Insertion Sort） 构建有序数列，对于无序数列，从有序数列后面遍历，找到合适的位置插入。 时间复杂度：O(n2)，空间复杂度：O(1)，稳定性：稳定 public void insert(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 1; i < arr.length; i++) { int preIndex = i - 1; int current = arr; while (preIndex >= 0 && arr[preIndex] > current) { arr[preIndex + 1] = arr[preIndex]; preIndex--; } arr[preIndex + 1] = current; } } 五、希尔排序（Shell Sort） 又称缩小增量排序，选取increment作为间隔分为increment个子序列，每个子序列使用直接插入排序，然后缩小increment直到increment=1。 时间复杂度：O(n1.3)，空间复杂度：O(1)，稳定性：不稳定 public void shellSort(int[] arr) { if (arr == null || arr.length < 2) { return; } int increment = arr.length; do { increment = increment / 3 + 1; for (int i = increment; i < arr.length; i++) { int preIndex = i - increment; int current = arr; while (preIndex >= 0 && arr[preIndex] > current) { arr[preIndex + increment] = arr[preIndex]; preIndex -= increment; } arr[preIndex + increment] = current; } } while (increment > 1); } increment的选取规则 increment = n / 2向下取整，但是奇数位置和偶数位置在increment=1时才比较，效率低 increment = n / 3向下取整 + 1 六、堆排序（Heap Sort） 将无序数列转化为最大（小）堆，然后堆顶元素与无序区外汇返佣http://www.fx61.com/最后一个元素替换，重构无序数列为最大（大）堆，继续替换重构直到无序区元素为一个。 时间复杂度：O(nlog2n)，空间复杂度：O(1)，稳定性：不稳定 public void heapSort(int[] arr) { if (arr == null || arr.length < 2) { return; } // 第一步：将数组变为最大堆。从下到上，从右到左构建最大堆 // 最后一个非叶子节点开始构建堆 for (int i = arr.length / 2 - 1; i >= 0; i--) { maxHeap(arr, arr.length - 1, i); } // 第二步：堆顶元素与最后一个元素交换，然后对前n-1个元素进行最大堆化 for (int i = arr.length - 1; i > 0; i--) { swap(arr, 0, i); maxHeap(arr, i - 1, 0); } } public void maxHeap(int[] arr, int size, int index) { int left = index * 2 + 1; int right = left + 1; int max = index; if (left > size) { return; } if (arr[left] > arr[max]) { max = left; } if (right <= size && arr[right] > arr[max]) { max = right; } if (max != index) { swap(arr, max, index); maxHeap(arr, size, max); } } public void swap(int[] arr, int i, int j) { int temp = arr; arr = arr[j]; arr[j] = temp; } 七、计数排序（Counting Sort） 无序数列都为整数，且知道最大数为k。可以创建k+1大小的数组，遍历无序数列，将其值出现的次数记载k+1数组对应的下标中。 时间复杂度：O(n+k)，空间复杂度：O(n+k)，稳定性：稳定。 // arr数组中的最大值 public void countSort(int[] arr, int max) { int[] bucket = new int[max + 1]; for (int i = 0; i < arr.length; i++) { bucket[arr]++; } int index = 0; for (int j = 0; j < bucket.length; j++) { int len = bucket[j]; while (len-- > 0) { arr[index++] = j; } } } 八、桶排序（Bucket Sort） 基于计数排序，按照映射关系f，将待排数列元素放到k个桶的指定位置，桶内排序可使用快排等，然后依次将桶内数据输出。 时间复杂度：O(n+k)空间复杂度：O(n+k)稳定性：稳定 适用于数据均匀分布在某一范围。 public void bucketSort(int[] arr) { // 找出最大值和最小值 int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; for (int i = 0; i < arr.length; i++) { max = Math.max(max, arr); min = Math.min(min, arr); } int bucketSize = (max - min) / arr.length + 1; List<List<Integer>> bucket = new ArrayList<>(bucketSize); // 初始化桶 for (int i = 0; i < bucketSize; i++) { bucket.add(new ArrayList<>()); } // 将数据放入对应桶中 for (int i = 0; i < arr.length; i++) { int num = (arr - min) / arr.length; bucket.get(num).add(arr); } // 将各个桶进行排序 int index = 0; for (int i = 0; i < bucketSize; i++) { if (!bucket.get(i).isEmpty()) { Collections.sort(bucket.get(i)); for (int item : bucket.get(i)) { arr[index++] = item; } } } } 九、基数排序（Radix Sort） 对每个数从最低位开始排序，将其放入【0-9】桶中，直至排到最高位。 时间复杂度：O(n*k)，空间复杂度：O(n+k)，稳定性：稳定。 步骤： 找出数组中最大数，并判断其位数。 创建二维数组，保存从最低位到最高位的排序中间结果。 针对每一趟排序，进行元素的分配和收集。 class RadixSort { 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; } /** * 自动扩容，并保存数据 * * @param arr * @param value */ private int[] arrayAppend(int[] arr, int value) { arr = Arrays.copyOf(arr, arr.length + 1); arr[arr.length - 1] = value; return arr; } } 十、归并排序（Merge Sort） 将序列一直对半分，直到每个子序列只有一个元素，然后在合并。 时间复杂度：O(nlog2n)，空间复杂度：O(n)，稳定性：稳定。 采用分而治之思想。 public void mergeSort(int[] arr, int start, int end) { if (start >= end) { return; } int mid = (start + end) / 2; mergeSort(arr, start, mid); mergeSort(arr, mid + 1, end); merge(arr, start, mid, end); } private void merge(int[] arr, int start, int mid, int end) { int[] tmp = new int[end - start + 1]; int left = start, right = mid + 1, tmpIndex = 0; while (left <= mid && right <= end) { if (arr[left] < arr[right]) { tmp[tmpIndex++] = arr[left++]; } else { tmp[tmpIndex++] = arr[right++]; } } while (left <= mid) { tmp[tmpIndex++] = arr[left++]; } while (right <= end) { tmp[tmpIndex++] = arr[right++]; } for (int i = 0; i < tmp.length; i++) { arr[start + i] = tmp; } }
| 
收藏
淘帖
踩
