主页»Java WEB»一遍记住Java常用的八种排序算法与代码完成

一遍记住Java常用的八种排序算法与代码完成

来历:KaelQ 发布时刻:2018-05-28 阅览次数:

1.直接刺进排序

常常碰到这样一类排序问题:把新的数据刺进到现已排好的数据列中。

  1. 将榜首个数和第二个数排序,然后构成一个有序序列
  2. 将第三个数刺进进去,构成一个新的有序序列。
  3. 对第四个数、第五个数……直到最终一个数,重复第二步。

怎么写写成代码:

  1. 首要设定刺进次数,即循环次数,for(int i=1;i<length;i++),1个数的那次不必刺进。
  2. 设定刺进数和得到现已排好序列的最终一个数的位数。insertNum和j=i-1。
  3. 从最终一个数开端向前循环,假如刺进数小于当时数,就将当时数向后移动一位。
  4. 将当时数放置到空着的方位,即j+1。

代码完成如下:

public void insertSort(int[] a){
        int length=a.length;//数组长度,将这个提取出来是为了进步速度。
        int insertNum;//要刺进的数
        for(int i=1;i<length;i++){//刺进的次数
            insertNum=a[i];//要刺进的数
            int j=i-1;//现已排序好的序列元素个数
            while(j>=0&&a[j]>insertNum){//序列从后到前循环,将大于insertNum的数向后移动一格
                a[j+1]=a[j];//元素移动一格
                j--;
            }
            a[j+1]=insertNum;//将需求刺进的数放在要刺进的方位。
        }
    }

2.希尔排序

关于直接刺进排序问题,数据量巨大时。

  1. 将数的个数设为n,取奇数k=n/2,将下标差值为k的书分为一组,构成有序序列。
  2. 再取k=k/2 ,将下标差值为k的书分为一组,构成有序序列。
  3. 重复第二步,直到k=1履行简略刺进排序。 

怎么写成代码:

  1. 首要确认分的组数。
  2. 然后对组中元素进行刺进排序。
  3. 然后将length/2,重复1,2步,直到length=0停止。

代码完成如下:

public  void sheelSort(int[] a){
        int d  = a.length;
        while (d!=0) {
            d=d/2;
            for (int x = 0; x < d; x++) {//分的组数
                for (int i = x + d; i < a.length; i += d) {//组中的元素,从第二个数开端
                    int j = i - d;//j为有序序列最终一位的位数
                    int temp = a[i];//要刺进的元素
                    for (; j >= 0 && temp < a[j]; j -= d) {//从后往前遍历。
                        a[j + d] = a[j];//向后移动d位
                    }
                    a[j + d] = temp;
                }
            }
        }
    }

3.简略挑选排序

常用于取序列中最大最小的几个数时。

(假如每次比较都交流,那么便是交流排序;假如每次比较完一个循环再交流,便是简略挑选排序。)

  1. 遍历整个序列,将最小的数放在最前面。
  2. 遍历剩下的序列,将最小的数放在最前面。
  3. 重复第二步,直到只剩下一个数。 

怎么写成代码:

  1. 首要确认循环次数,而且记住当时数字和当时方位。
  2. 将当时方位后边一切的数与当时数字进行比照,小数赋值给key,并记住小数的方位。
  3. 比对完成后,将最小的值与榜首个数的值交流。
  4. 重复2、3步。

代码完成如下:

    public void selectSort(int[] a) {
        int length = a.length;
        for (int i = 0; i < length; i++) {//循环次数
            int key = a[i];
            int position=i;
            for (int j = i + 1; j < length; j++) {//选出最小的值和方位
                if (a[j] < key) {
                    key = a[j];
                    position = j;
                }
            }
            a[position]=a[i];//交流方位
            a[i]=key;
        }
    }

4.堆排序

对简略挑选排序的优化。

  1. 将序列构建成大顶堆。
  2. 将根节点与最终一个节点交流,然后断开最终一个节点。
  3. 重复榜首、二步,直到一切节点断开。 

代码完成如下:

public  void heapSort(int[] a){
        System.out.println("开端排序");
        int arrayLength=a.length;
        //循环建堆  
        for(int i=0;i<arrayLength-1;i++){
            //建堆  

            buildMaxHeap(a,arrayLength-1-i);
            //交流堆顶和最终一个元素  
            swap(a,0,arrayLength-1-i);
            System.out.println(Arrays.toString(a));
        }
    }
    private  void swap(int[] data, int i, int j) {
        // TODO Auto-generated method stub  
        int tmp=data[i];
        data[i]=data[j];
        data[j]=tmp;
    }
    //对data数组从0到lastIndex建大顶堆  
    private void buildMaxHeap(int[] data, int lastIndex) {
        // TODO Auto-generated method stub  
        //从lastIndex处节点(最终一个节点)的父节点开端  
        for(int i=(lastIndex-1)/2;i>=0;i--){
            //k保存正在判别的节点  
            int k=i;
            //假如当时k节点的子节点存在  
            while(k*2+1<=lastIndex){
                //k节点的左子节点的索引  
                int biggerIndex=2*k+1;
                //假如biggerIndex小于lastIndex,即biggerIndex+1代表的k节点的右子节点存在  
                if(biggerIndex<lastIndex){
                    //若果右子节点的值较大  
                    if(data[biggerIndex]<data[biggerIndex+1]){
                        //biggerIndex总是记载较大子节点的索引  
                        biggerIndex++;
                    }
                }
                //假如k节点的值小于其较大的子节点的值  
                if(data[k]<data[biggerIndex]){
                    //交流他们  
                    swap(data,k,biggerIndex);
                    //将biggerIndex赋予k,开端while循环的下一次循环,从头确保k节点的值大于其左右子节点的值  
                    k=biggerIndex;
                }else{
                    break;
                }
            }
        }
    }

5.冒泡排序

一般不必。

  1. 将序列中一切元素两两比较,将最大的放在最终面。
  2. 将剩下序列中一切元素两两比较,将最大的放在最终面。
  3. 重复第二步,直到只剩下一个数。 

怎么写成代码:

  1. 设置循环次数。
  2. 设置开端比较的位数,和结束的位数。
  3. 两两比较,将最小的放到前面去。
  4. 重复2、3步,直到循环次数结束。

代码完成如下:

public void bubbleSort(int[] a){
        int length=a.length;
        int temp;
        for(int i=0;i<a.length;i++){
            for(int j=0;j<a.length-i-1;j++){
                if(a[j]>a[j+1]){
                    temp=a[j];
                    a[j]=a[j+1];
                    a[j+1]=temp;
                }
            }
        }
    }

6.快速排序

要求时刻最快时。

  1. 挑选榜首个数为p,小于p的数放在左面,大于p的数放在右边。
  2. 递归的将p左面和右边的数都依照榜首步进行,直到不能递归。 

代码完成如下:

public static void quickSort(int[] numbers, int start, int end) {   
    if (start < end) {   
        int base = numbers[start]; // 选定的基准值(榜首个数值作为基准值)   
        int temp; // 记载暂时中心值   
        int i = start, j = end;   
        do {   
            while ((numbers[i] < base) && (i < end))   
                i++;   
            while ((numbers[j] > base) && (j > start))   
                j--;   
            if (i <= j) {   
                temp = numbers[i];   
                numbers[i] = numbers[j];   
                numbers[j] = temp;   
                i++;   
                j--;   
            }   
        } while (i <= j);   
        if (start < j)   
            quickSort(numbers, start, j);   
        if (end > i)   
            quickSort(numbers, i, end);   
    }   
}  

7.归并排序

速度仅次于快排,内存少的时分运用,能够进行并行核算的时分运用。

  1. 挑选相邻两个数组成一个有序序列。
  2. 挑选相邻的两个有序序列组成一个有序序列。
  3. 重复第二步,直到悉数组成一个有序序列。 

代码完成如下:

public static void mergeSort(int[] numbers, int left, int right) {   
    int t = 1;// 每组元素个数   
    int size = right - left + 1;   
    while (t < size) {   
        int s = t;// 本次循环每组元素个数   
        t = 2 * s;   
        int i = left;   
        while (i + (t - 1) < size) {   
            merge(numbers, i, i + (s - 1), i + (t - 1));   
            i += t;   
        }   
        if (i + (s - 1) < right)   
            merge(numbers, i, i + (s - 1), right);   
    }   
}   
private static void merge(int[] data, int p, int q, int r) {   
    int[] B = new int[data.length];   
    int s = p;   
    int t = q + 1;   
    int k = p;   
    while (s <= q && t <= r) {   
        if (data[s] <= data[t]) {   
            B[k] = data[s];   
            s++;   
        } else {   
            B[k] = data[t];   
            t++;   
        }   
        k++;   
    }   
    if (s == q + 1)   
        B[k++] = data[t++];   
    else  
        B[k++] = data[s++];   
    for (int i = p; i <= r; i++)   
        data[i] = B[i];   
}  

8.基数排序

用于很多数,很长的数进行排序时。

  1. 将一切的数的个位数取出,依照个位数进行排序,构成一个序列。
  2. 将新构成的一切的数的十位数取出,依照十位数进行排序,构成一个序列。 

代码完成如下:

public void sort(int[] array) {
        //首要确认排序的趟数;     
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }
        int time = 0;
        //判别位数;     
        while (max > 0) {
            max /= 10;
            time++;
        }
        //树立10个行列;     
        List<ArrayList> queue = new ArrayList<ArrayList>();
        for (int i = 0; i < 10; i++) {
            ArrayList<Integer> queue1 = new ArrayList<Integer>();
            queue.add(queue1);
        }
        //进行time次分配和搜集;     
        for (int i = 0; i < time; i++) {
            //分配数组元素;     
            for (int j = 0; j < array.length; j++) {
                //得到数字的第time+1位数;   
                int x = array[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
                ArrayList<Integer> queue2 = queue.get(x);
                queue2.add(array[j]);
                queue.set(x, queue2);
            }
            int count = 0;//元素计数器;     
            //搜集行列元素;     
            for (int k = 0; k < 10; k++) {
                while (queue.get(k).size() > 0) {
                    ArrayList<Integer> queue3 = queue.get(k);
                    array[count] = queue3.get(0);
                    queue3.remove(0);
                    count++;
                }
            }
        }
    }
QQ群:凯发娱乐官网官方群(515171538),验证音讯:10000
微信群:加小编微信 849023636 邀请您参加,验证音讯:10000
提示:更多精彩内容重视微信大众号:全栈开发者中心(fsder-com)
m88 188bet uedbet 威廉希尔 明升 bwin 明升88 bodog bwin 明升m88.com 18luck 188bet unibet unibet Ladbrokes Ladbrokes casino m88明升 明升 明升 m88.com 188bet m88 明陞 uedbet赫塔菲官网 365bet官网 m88 help
网友谈论(共0条谈论) 正在载入谈论......
沉着谈论文明上网,回绝歹意咒骂 宣布谈论 / 共0条谈论
登录会员中心