首页 > 代码库 > 快速排序与归并排序
快速排序与归并排序
实现原理：
- 快速排序：关键点是从队列中任意取出一个值，将其放在正确的位置（左边小于等于此数，右边大于等于此数），确定每个数自己的位置以后队列便是从小大大依次排序。
- 归并排序：先将队列拆封成两更小的队列，小队列依次排序，让后再将小队列合并，并确保顺序。
代码：
1 public class test { 2 public static void main(String args[]) { 3 int[] aa = { 4, 5, 2, 7, 8, 2, 1, 6, 4, 4, 3 }; 4 //quicksort(aa, 0, aa.length - 1); 5 mergesort(aa, 0, aa.length - 1); 6 for (int i : aa) { 7 System.out.print(i + " "); 8 } 9 }10 11 /**12 * 快速排序13 * 14 * @param aa15 * @param begin16 * @param end17 */18 public static void quicksort(int[] aa, int begin, int end) {19 if (begin < end) {20 int b = begin;21 int e = end;22 int base = aa[begin];23 while (b < e) {24 while (b < e && aa[e] >= base)25 e--;26 aa[b] = aa[e];27 while (b < e && aa[b] <= base)28 b++;29 aa[e] = aa[b];30 };31 //b与e相等，任意取一个32 aa[b] = base;33 quicksort(aa, begin, b - 1);34 quicksort(aa, b + 1, end);35 }36 }37 38 /**39 * 归并排序40 * 41 * @param aa42 * @param begin43 * @param end44 */45 public static void mergesort(int[] aa, int begin, int end) {46 if (begin < end) {47 int middle = (begin + end) / 2;48 mergesort(aa, begin, middle);49 mergesort(aa, middle + 1, end);50 int[] tmpArr = new int[aa.length];51 int mid = middle + 1; // 右边的起始位置52 int tmp = begin;53 int third = begin;54 while (begin <= middle && mid <= end) {55 // 从两个数组中选取较小的数放入中间数组56 if (aa[begin] <= aa[mid]) {57 tmpArr[third++] = aa[begin++];58 } else {59 tmpArr[third++] = aa[mid++];60 }61 }62 // 将剩余的部分放入中间数组63 while (begin <= middle) {64 tmpArr[third++] = aa[begin++];65 }66 while (mid <= end) {67 tmpArr[third++] = aa[mid++];68 }69 // 将中间数组复制回原数组70 while (tmp <= end) {71 aa[tmp] = tmpArr[tmp++];72 }73 }74 }75 }
快速排序与归并排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。