请教一个关于JAVA的排序问题,看看有没有什么简便的算法

HaydnSyx 发布于 2016/09/23 15:01
阅读 480
收藏 0
比如有这样的list
[1, 4, 3, 5, 2]
目的让这个list的分别将最大与最小互换并保持原位(不知道怎么描述),交换后如下:
[5, 2, 3, 1, 4]


又比如:原list为
[1, 1, 5, 2, 3]
则交换后如下:
[5, 5, 1, 3, 2]


大家有没有什么好算法分享一下(想的脑袋都疼了)
加载中
1
H
HaydnSyx

引用来自“fgod”的评论

public static void main(String[] args) {
        List<Integer> baseList = new ArrayList<>();
        baseList.add(1);
        baseList.add(1);
        baseList.add(5);
        baseList.add(2);
        baseList.add(3);
        List<Integer> listWithSort = new ArrayList<>();
        int size = baseList.size();
        for(int i=0;i<baseList.size();i++){
            if(!listWithSort.contains(baseList.get(i))){
                listWithSort.add(baseList.get(i));
            }
        }
        bubbleUpSortList(listWithSort);//升序集合
        System.out.println("原始集合:"+baseList);
        System.out.println("排序后的集合:"+listWithSort);
        Integer max;
        Integer min;
        int sizeSort = listWithSort.size();
        int middle = sizeSort/2;
        List<Integer> tempMinIndex = new ArrayList<>();
        List<Integer> tempMaxIndex = new ArrayList<>();
        List<Integer> replacedIndex = new ArrayList<>();//存储已经替换过的索引值
        if(middle>=1){
            for(int i= 0;i<middle;i++){
                //获取将要替换的值
                min = listWithSort.get(i);
                max = listWithSort.get(sizeSort-1-i);
                tempMaxIndex.clear();
                tempMinIndex.clear();
                for(int j=0;j<=size-1;j++){
                    if(!replacedIndex.contains(j) && baseList.get(j).equals(min)){
                        tempMinIndex.add(j);
                    }
                    if(!replacedIndex.contains(j) && baseList.get(j).equals(max)){
                        tempMaxIndex.add(j);
                    }
                }
                //替换
                if(tempMaxIndex.size()>0&&tempMinIndex.size()>0){
                    for (Integer integer : tempMaxIndex) {
                        baseList.set(integer,min);
                        replacedIndex.add(integer);
                    }
                    for (Integer integer : tempMinIndex) {
                        baseList.set(integer,max);
                        replacedIndex.add(integer);
                    }
                }
            }
        }
//    输出替换后的集合
/*       原始集合:[1, 1, 5, 2, 3]
         排序后的集合:[1, 2, 3, 5]
         替换后的集合:[5, 5, 1, 3, 2]
*/
        System.out.println("替换后的集合:"+baseList);
    }
    //    集合

    /*冒泡升序-集合*/
    public static void bubbleUpSortList(List<Integer> baseList){
        Integer temp;
        for(int i=0;i<baseList.size()-1;i++){
            for(int j = 0; j<baseList.size()-1-i;j++){
                if(baseList.get(j)>baseList.get(j+1)){
                    temp = baseList.get(j);
                    baseList.set(j,baseList.get(j+1));
                    baseList.set(j+1,temp);
                }
            }
        }
    }



public static void main(String[] args) {
	List<Integer> oldList = Arrays.asList(1, 4, 3, 5, 2);

	Set<Integer> set = new HashSet<>();
	set.addAll(oldList);

	List<Integer> sortlist1 = new ArrayList<>(set);
	Collections.sort(sortlist1);// 1,2,3,4,5
	List<Integer> sortlist2 = new ArrayList<>(sortlist1);
	Collections.reverse(sortlist2);// 5,4,3,2,1

	Map<Integer, Integer> m = new HashMap<>();
	for (int i = 0; i < sortlist1.size(); i++) {
		m.put(sortlist1.get(i), sortlist2.get(i));
	}

	List<Integer> finalList = new ArrayList<>();
	for (Integer i : oldList) {
		finalList.add(m.get(i));
	}
	
	System.out.println(finalList.toString());
}



0
求是科技
求是科技

下面一个应该是 

1 1 5 2 3 -->5 1 1 3 2吧?

H
HaydnSyx
回复 @求是科技 : 对,都要替换
求是科技
求是科技
难道是最大值与最小值比较的时候,最小值有多个都要替换?
0
H
HaydnSyx

引用来自“求是科技”的评论

下面一个应该是 

1 1 5 2 3 -->5 1 1 3 2吧?

不不,其实多了一步去重步骤,原list就会变成 1 5 2 3,在替换后就会把所有的1变成5,5变成1,2变成3,3变成2
0
一笑居
一笑居
public static void main(String[] args) {
        long[] array = {1L, 2L, 3L, 5L, 4L};
        long min = Longs.min(array);
        int minIndex = Arrays.binarySearch(array, min);
        long max = Longs.max(array);
        int maxIndex = Arrays.binarySearch(array, max);

        array[minIndex] = max;
        array[maxIndex] = min;
        System.out.println(JSON.toJSON(array));
    }



不考虑复杂度,就这几行代码


0
f
fgod
public class ReplaceList {
//    集合大小排序后替换对应位置元素,最大最小替换,依次替换
    public static void main(String[] args) {
        List<Integer> baseList = new ArrayList<>();
        baseList.add(1);
        baseList.add(4);
        baseList.add(2);
        baseList.add(5);
        baseList.add(1);
        baseList.add(8);
        List<Integer> listWithSort = new ArrayList<>();
        int size = baseList.size();
        for(int i=0;i<baseList.size();i++){
            listWithSort.add(baseList.get(i));
        }
        bubbleUpSortList(listWithSort);//升序集合
        System.out.println("原始集合:"+baseList);
        System.out.println("排序后的集合:"+listWithSort);
        Integer max;
        Integer min;

        int middle = size/2;
        boolean getMin;
        boolean getMax;
        int tempMinIndex = 0;
        int tempMaxIndex = 0;
        List<Integer> replacedIndex = new ArrayList<>();//存储已经替换过的索引值
        if(size>=2){
            for(int i= 0;i<middle;i++){
                //获取将要替换的值
                min = listWithSort.get(i);
                max = listWithSort.get(size-1-i);
                getMax = false;
                getMin = false;
               //获取索引
               for(int j=0;j<=size-1;j++){
                   if(!replacedIndex.contains(j) && !getMin
                           && baseList.get(j).equals(min)){
                       getMin = true;
                       tempMinIndex = j;
                   }
                   if(!replacedIndex.contains(j)&& !getMax
                           && baseList.get(j).equals(max)){
                       getMax = true;
                       tempMaxIndex = j;
                   }
               }//替换 
               baseList.set(tempMinIndex,max);
               baseList.set(tempMaxIndex,min);
               replacedIndex.add(tempMaxIndex);
               replacedIndex.add(tempMinIndex);
            }
        }
//    输出替换后的集合
/*       原始集合:[1, 4, 2, 5, 1, 8]
        排序后的集合:[1, 1, 2, 4, 5, 8]
        替换后的集合:[8, 2, 4, 1, 5, 1]
        ? [5, 2, 4, 1, 8, 1] 这个看起来也满足
*/
        System.out.println("替换后的集合:"+baseList);
    }
    //    集合

    /*冒泡升序-集合*/
    public static void bubbleUpSortList(List<Integer> baseList){
        Integer temp;
        for(int i=0;i<baseList.size()-1;i++){
            for(int j = 0; j<baseList.size()-1-i;j++){
                if(baseList.get(j)>baseList.get(j+1)){
                    temp = baseList.get(j);
                    baseList.set(j,baseList.get(j+1));
                    baseList.set(j+1,temp);
                }
            }
        }
    }
}



f
fgod
我擦,写完才看到 1,1,5替换成5,5,1,,尼玛。。。
0
f
fgod
public static void main(String[] args) {
        List<Integer> baseList = new ArrayList<>();
        baseList.add(1);
        baseList.add(1);
        baseList.add(5);
        baseList.add(2);
        baseList.add(3);
        List<Integer> listWithSort = new ArrayList<>();
        int size = baseList.size();
        for(int i=0;i<baseList.size();i++){
            if(!listWithSort.contains(baseList.get(i))){
                listWithSort.add(baseList.get(i));
            }
        }
        bubbleUpSortList(listWithSort);//升序集合
        System.out.println("原始集合:"+baseList);
        System.out.println("排序后的集合:"+listWithSort);
        Integer max;
        Integer min;
        int sizeSort = listWithSort.size();
        int middle = sizeSort/2;
        List<Integer> tempMinIndex = new ArrayList<>();
        List<Integer> tempMaxIndex = new ArrayList<>();
        List<Integer> replacedIndex = new ArrayList<>();//存储已经替换过的索引值
        if(middle>=1){
            for(int i= 0;i<middle;i++){
                //获取将要替换的值
                min = listWithSort.get(i);
                max = listWithSort.get(sizeSort-1-i);
                tempMaxIndex.clear();
                tempMinIndex.clear();
                for(int j=0;j<=size-1;j++){
                    if(!replacedIndex.contains(j) && baseList.get(j).equals(min)){
                        tempMinIndex.add(j);
                    }
                    if(!replacedIndex.contains(j) && baseList.get(j).equals(max)){
                        tempMaxIndex.add(j);
                    }
                }
                //替换
                if(tempMaxIndex.size()>0&&tempMinIndex.size()>0){
                    for (Integer integer : tempMaxIndex) {
                        baseList.set(integer,min);
                        replacedIndex.add(integer);
                    }
                    for (Integer integer : tempMinIndex) {
                        baseList.set(integer,max);
                        replacedIndex.add(integer);
                    }
                }
            }
        }
//    输出替换后的集合
/*       原始集合:[1, 1, 5, 2, 3]
         排序后的集合:[1, 2, 3, 5]
         替换后的集合:[5, 5, 1, 3, 2]
*/
        System.out.println("替换后的集合:"+baseList);
    }
    //    集合

    /*冒泡升序-集合*/
    public static void bubbleUpSortList(List<Integer> baseList){
        Integer temp;
        for(int i=0;i<baseList.size()-1;i++){
            for(int j = 0; j<baseList.size()-1-i;j++){
                if(baseList.get(j)>baseList.get(j+1)){
                    temp = baseList.get(j);
                    baseList.set(j,baseList.get(j+1));
                    baseList.set(j+1,temp);
                }
            }
        }
    }



H
HaydnSyx
回复 @fgod : 写在下面了
f
fgod
回复 @HaydnSyx : 大兄弟,介意贴下代码不,学习学习
H
HaydnSyx
太麻烦了,目前还是用set去重,用list进行正序、倒序之后再封装到map中(正序做key,倒序做value),然后再循环原list,用过map找到对应值替代比较简单
0
c
chenjj1213

1.找出所有最小的和所有最大的且未标记已替换的数字,然后替换,然后将此数据标记成已替换。

2.递归步骤1,直到所有的都被标记了,或者只剩下一个数字,则退出递归。

以上只是思路,不知是否可行。

0
万恶的牛牛
万恶的牛牛
没看懂需求 无从下手
0
愉悦混乱
愉悦混乱
用冒泡排序和选择排序
返回顶部
顶部