【模板】排序模板总结
< 返回列表时间: 2020-06-29来源:OSCHINA
快排 选定一个基准元素 x 分区过程, >= x 的数全放到它的右边, <= x 的数全放到它的左边 交换,如果此时两个指针 i、j 没有相遇过,则 i 一定是遇到了一个 >= x 的数, j 遇到了一个 <= x 的数,此时需要将 a[i]、a[j] 交换 再对左右区间分别重复第二步,直到区间中只有一个数时返回 void quick_sort(int[] a, int l, int r) { if (l >= r) return; int i = l-1, j = r+1, x = a[l + r>>>1]; while (i < j) { while(a[++i] < x); while(a[++j] > x); if (i < j) swap(a, i, j); } quick_sort(a, l, j); quick_sort(a, j+1, r); }
快速选择 :快应用于寻找数组数组中的第 k 小/第 n-k 大的数 int quick_select(int[] a, int l, int r, int k) { if (l >= r) return a[k]; int p = (int)(Math.random() * (r-l+1)) + l, x = a[p], i = l-1, j = r+1; while (i < j) { do i++; while (a[i] < x); do j--; while (a[j] > x); if (i < j) swap(a, i, j); } if (j >= k) return quick_select(a, l, j, k); else return quick_select(a, j+1, r, k); }
归并 取中心点 mid = l + r >>> 1 递归处理左半边 [l, m] 和右半边 [mid+1, r] ,当某一次归并处理完毕后,两个区间内的数分别有序 最后用双指针算法将两个区间合并 void merge_sort(int[] a, int l, int r) { if (l >= r) return; int m = l + r >>> 1; merge_sort(a, l, m); merge_sort(a, m+1,r); int i = l, j = m+1, k = 0, b[] = new int[r-l+1]; while (i <= m && j <= r) { if (a[i] <= a[j]) b[k++] = a[i++]; else b[k++] = a[j++]; } while (i <= m) b[k++] = a[i++]; while (j <= r) b[k++] = a[j++]; for (i = l, j = 0; i <= r; i++, j++) a[i] = b[j]; }
热门排行