记录元素在java排序算法中的比较
嗨，我正在使用下面的插入排序算法，我想记录正在比较的元素。基本上，我希望将比较存储在两个数组列表中，arrList1和arrList2。如果元素位于正确的位置，则两个数组列表将具有相同的元素。如果不是，那么arrList1将拥有所选的元素，而arrayList2将拥有与之进行比较的元素。我目前正在努力做到这一点，所以我想知道是否有人可以帮助我？谢谢
public static ArrayList<Integer> arrList1 = new ArrayList<Integer>();
public static ArrayList<Integer> arrList2 = new ArrayList<Integer>();
...
public static void insertSort(int[] A){
for(int i = 1; i < A.length; i++){
int value = A[i];
int j = i - 1;
while(j >= 0 && A[j] > value){
A[j + 1] = A[j];
j = j - 1;
}
A[j + 1] = value;
}
}编辑:例如:如果我的数组有数字1,3,2,4,6,5，那么在比较时，我希望我的两个数组列表看起来是这样的：
arrList1 arrList2
#1 1 1
#2 3 3
#3 2 3 (As 2 goes before 3 then it must be compared to 3)
#4 4 4
#5 6 6
#6 5 6 (As 5 is lower then 6 then it must be compared to 6)排序数组: 1，2，3，4，5，6
正如你所看到的，arrList1基本上是输入数组的顺序，而arrList2是元素，如果它不在正确的位置，它将与之进行比较。如果它在正确的位置，那么arrList 2将是相同的值。
回答 2
Stack Overflow用户
发布于 2012-02-12 01:09:37
这就是了..。
public class Test {
public static List<Integer> arrList1;
public static ArrayList<Integer> arrList2 = new ArrayList<Integer>();
public static void main (String... args){
Integer[] toSort = {1, 3, 2, 4, 6, 5};
arrList1 = Arrays.asList(Arrays.copyOf(toSort, toSort.length));
insertSort(toSort);
List<Integer> sortedArray = new ArrayList<Integer>();
for(int aux: toSort){
sortedArray.add(aux);
}
System.out.println("Array list 1: " + arrList1);
System.out.println("Array list 2: " + arrList2);
System.out.println("Sorted array: " + sortedArray);
}
public static void insertSort(Integer[] A){
arrList2.add(arrList1.get(0));
for(int i = 1; i < A.length; i++){
int value = A[i];
int j = i - 1;
if ((j >= 0 && A[j] > value)){
arrList2.add(A[j]);
}else{
arrList2.add(A[i]);
}
while(j >= 0 && A[j] > value){
A[j + 1] = A[j];
j = j - 1;
}
A[j + 1] = value;
}
}
}这段代码的输出结果是：
数组列表1: 1，3，2，4，6，5数组列表2: 1，3，3，4，6，6排序数组: 1，2，3，4，5，6
Stack Overflow用户
发布于 2012-02-11 01:55:42
编辑:现在我明白了，这里的问题就是我所建议的。首先请注意，插入排序的复杂度是平方的(O(n^2))，因此相同复杂度的另一次计算不会改变算法的整体复杂度。因此，您要做的是-首先，通过遍历当前元素左侧的所有值并搜索比当前元素大的第一个值来计算arrList2中的值。第二个阶段是简单的排序算法-就像你已经指出的，arrList1保存排序的A。整个事情可以用更好的复杂度来实现，而不是使用插入排序。
public static ArrayList<Integer> arrList1 = new ArrayList<Integer>();
public static ArrayList<Integer> arrList2 = new ArrayList<Integer>();
...
public static void insertSort(int[] A){
for (int i = 0; i < A.length; ++i) {
boolean found_greater = false;
for (int j = i - 1; j >= 0; --j) {
if (A[j] > A[i]) {
found_greater = true;
arrList2.add(A[j]);
break;
}
}
if (!found_greater) {
arrList2.add(A[i]);
}
}
for(int i = 1; i < A.length; i++){
int value = A[i];
int j = i - 1;
while(j >= 0 && A[j] > value){
A[j + 1] = A[j];
j = j - 1;
}
arrList1.add(A[i]);
A[j + 1] = value;
}
}https://stackoverflow.com/questions/9231455
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号