简单的算法问题

2019-08-19 | 阅读：次

算法

有一个数组a，有一个变量n，大于变量n的放到数组的前面，小于变量n的放到数组的后面（不需要排序）？


刚开始有和和简单的思想， 如果采用list来处理就很简单了判断当前的数据是否小于目标， 然后分类， 最后
将集合的数还原到数字里面去；

class Q{
    private static void simpleCategory(int[] arr, int n) {
        List<Integer> left = new ArrayList<>();
        List<Integer> center = new ArrayList<>();
        List<Integer> right = new ArrayList<>();
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < n) {
                left.add(arr[i]);
            } else if (arr[i] > n) {
                right.add(arr[i]);
            } else {
                center.add(arr[i]);
            }
        }
        result.addAll(left);
        result.addAll(center);
        result.addAll(right);
        for (int i = 0; i < result.size(); i++) {
            arr[i] = result.get(i);
        }
    }
}

但是发现这个算法不够简洁； 
思路：
遍历我们的数组 ， 如果发现 e (element)  e < target 说明需要对当前一段区间的数据进行交换了
那么怎么交换了， 不是所有的数需要交换 
举列子

1, 2, 3, 4, 5, 2, 3, 2, 8, 11, 9, 1, 2, 8, 14
目标为5 
1到4是不会发生任何的交换的， 5也不会发生交换， 那么当e = 2的时候
需要交换5 ，2
==>1, 2, 3, 4, 2, 5, 3, 2, 8, 11, 9, 1, 2, 8, 14
..... 
内部的交换需要一个循环来实现 保证当 e > target 的时候需要交换元素的位置

package com.example.springbootstudy.test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author shenzm
 * @date 2019-8-19
 * @description 作用
 */
public class Q {

    //有一个数组a，有一个变量n，大于变量n的放到数组的前面，小于变量n的放到数组的后面（不需要排序）
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 2, 3, 2, 8, 11, 9, 1, 2, 8, 14};
        int n = 5;
        simpleCategory(arr, n);
        sort(arr, n);
        System.out.println(Arrays.toString(arr));


    }

    /**
     * @param arr 数组
     * @param n   目标数
     */
    private static void sort(int[] arr, int n) {
        //对每个元素进行遍历
        for (int i = 0; i < arr.length; i++) {
            //如果发现当前的元素小于目标数， 就需要将一部分的数字的数据进行交换；
            if (arr[i] <= n) {
                for (int k = 0; k < i; k++) {
                    //这部分数据开始的角标的位置 k (arr[k] >=n)
                    if (arr[k] >= n) {
                        //k 为时大于目标的位置 ， 需要往后进行调整
                        int temp = arr[k];
                        arr[k] = arr[i];
                        arr[i] = temp;
                    }
                }
            }
        }
    }

    private static void simpleCategory(int[] arr, int n) {
        List<Integer> left = new ArrayList<>();
        List<Integer> center = new ArrayList<>();
        List<Integer> right = new ArrayList<>();
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < n) {
                left.add(arr[i]);
            } else if (arr[i] > n) {
                right.add(arr[i]);
            } else {
                center.add(arr[i]);
            }
        }
        result.addAll(left);
        result.addAll(center);
        result.addAll(right);
        for (int i = 0; i < result.size(); i++) {
            arr[i] = result.get(i);
        }
    }
}

ninuxGithub

ninuxGithub

简单的算法问题

算法