算法学习：排序

2018-09-24

字数统计: 696字 | 阅读时长≈ 3分

《算法设计与分析》课程学习总结

0x00 插入排序

pass

0x01 希尔排序

原理：将待排序的数组元素按照下标进行一定的增量分组，分成多个子序列，对这些子序列进行插入排序，然后依次缩减增量再进行排序，直到增量为1，排序结束

具体代码：

package com.example.demo.Algorithm.sort;

import java.util.Arrays;

/**
 * @author lei.X
 * @date 2018/9/23
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] arr = {99, 5, 69, 33, 56, 13, 22, 55, 77, 48, 12, 88, 2,69,99};
        System.out.println("排序之前数组：");
        System.out.println(Arrays.toString(arr));
        //希尔排序
        insertionSort(arr);
        System.out.println("希尔排序后数组：");
        System.out.println(Arrays.toString(arr));

    }

    private static void  insertionSort(int[] arr){
        if(arr == null || arr.length <= 1){
            return;
        }
        int len = arr.length;
        for(int d=len/2;d>0;d/=2){   // 决定子数组的大小（7 ，3， 1）
            for(int i=d;i<len;i++){  //第2个子分组所在的坐标
                for(int j=i-d;j>=0;j -=d){ //每一个子分组所在的坐标
                    if (arr[j] > arr[j+d]){   //这里一定要注意用j+d而不是用i来表示，因为i是一个不会变的值，而j+d会不断变化
                        swap(arr,j+d,j);
                        System.out.println(Arrays.toString(arr));
                    }
                }
            }
        }
    }

    /*
   发现无论什么排序。都需要对满足条件的元素进行位置置换。
   所以可以把这部分相同的代码提取出来，单独封装成一个函数。
   */
    public static void swap(int[] arr,int a,int b)
    {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

}

0x02 Quick Sort

quickSort的核心在于随机找到一个值，然后以这个值为中心，将比这个值小的数放到左边，比这个值大的数放到右边，然后递归进行

下图为partSort的示意图

屏幕快照 2018-09-24 下午7.03.36

(…感觉是一堆废话，直接上代码吧- -‘)

package com.example.demo.Algorithm.sort;

import java.util.Arrays;

/**
 * @author lei.X
 * @date 2018/9/24
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {8, 2, 1, 4,6,7, 3, 5, 9, 6,11,19,13,55,67,32,22};

        quickSort(arr);
//        System.out.println(partSort(arr,0,arr.length-1));

        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr){

        recurPartiton(arr,0,arr.length-1);

    }

//quickSort的核心
    private static int partSort(int[] arr, int low ,int high){
        int base = arr[high];
        int cur = low; //cur代表base最后应该放置的位置
        for(int i=low;i<high;i++){
            if (arr[i]<base){
                swap(arr,cur,i);
                cur++; 
            }
        }
        swap(arr,high,cur); //最后将base放到cur这个坐标上
        return cur;
    }

    private static void recurPartiton(int[] arr,int start,int end){
        if (end-start<1) return; //递归数组只剩一个元素
        int partition = partSort(arr,start,end);
        recurPartiton(arr,start,partition-1);
        recurPartiton(arr,partition+1,end);


    }


    public static void swap(int[] arr,int a,int b)
    {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

}

本文作者： Noisy
本文链接： http://Metatronxl.github.io/2018/09/24/算法学习：排序/
版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！