快速排序+插入排序

Question

最近小弟遇到个题...是说怎么结合快速排序和插入排序..麻烦哪位大虾帮帮写个..一个数组,比如说是[2,7,3,4,6,9,7,8,6,3,1,4,9]
ps是一个变量,当ps<=4时,意味着前4个数用插入排序.
当ps 大于4时,用插入排序，让左右两边递归到ps<=4的情况。

Answer 1

另：当ps大于4时，需要用快速排序。而不是仅仅递归到ps《=4

Answer 2

刚写的
import java.util.Random;public class Sort { // 快速排序
public static void qsort(int[] data, int left, int right) {
int l = left;
int r = right;
int m = data[left]; while (true) {
while (data[l] < m) {
l++;
}
while (data[r] > m) {
r--;
}
if (l < r) {
int temp = data[l];
data[l] = data[r];
data[r] = temp;
l++;
r--;
} else {
break;
}
} if (left < r) {
// 递归到数组长度小于等于10用插入 否则继续用快速递归
if (r - left + 1 <= 10) {
sort(data, left, l - 1);
} else {
qsort(data, left, l - 1);
}
}
if (right > l) {
// 递归到数组长度小于等于10用插入 否则继续用快速递归
if (right - l + 1 <= 10) {
sort(data, r + 1, right);
} else {
qsort(data, r + 1, right);
}
}
} // 插入排序
public static void sort(int[] data, int left, int right) {
for (int i = left; i <= right; i++) {
for (int j = left; j < i; j++) {
if (data[i] < data[j]) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
}
} // 用户接口
public static void qsort(int[] data) {
if (data.length <= 10) { // ps=10
sort(data, 0, data.length - 1);
} else {
qsort(data, 0, data.length - 1);
}
} // 验证数组是否为升序
public static boolean validate(int[] data) {
for (int i = 0; i < data.length - 1; i++) {
if (data[i + 1] < data[i]) {
return false;
}
}
return true;
} public static void main(String[] args) throws Exception {
Random r = new Random();
int[] data = new int[10000];
for (int i = 0; i < data.length; i++) {
data[i] = r.nextInt(100);
} Sort.qsort(data); for (int i = 0; i < data.length; i++) {
System.out.println(data[i] + " ");
}
System.out.println("数组是否为升序: " + validate(data));
}
}

Answer 3

有点小bug 插入排序被重复调用了
等我改改

Answer 4

去看java 的Arrays里的sort方法实现，那是结合了插入和归并。

Answer 5

jdk的排序写得比较复杂 适用于数据量比较大的情况我测试过的结果是 数据量大约超过二十万的话 jdk的排序很有优势但如果数据量小的话反而不如自己写的一般的快速排序