排序算法归纳

• 稳定排序：相等值不交换，包括冒泡、插入、归并和基数
• 不稳定排序：相等值交换，包括选择，快排序，希尔，堆排序

复杂度

思路

• 冒泡
  相邻两个交换，每次循环让当前与前一个比较，如果不满足顺序则交换
• 插入
  前面的已经排序好，把当前的值插入到前面的有序序列中，代码是 从当前逐步向前回溯交换
• 归并
  分割序列，把当前序列平均分割为两个序列，然后分别对这两个序列进行排序，然后合并成一个序列，对于两个有序序列，只需要遍历一遍就可以得到一个有序。递归的执行，最终最小的数组是1个元素或者0个元素，逐步的合并。
• 基数排序
  对数字进行排序，建立0-9数字桶，对于一个数字，把他拆分为为多个数字，从低位到高位逐位放入数字桶中

• 选择排序
  前面是有序的，选择当前值作为后面序列中的最小值。每次循环找到未排序序列的最小值

• 快排序
  分治，对于每一个子序列，选择一个基准，把小于基准的数放到左边，大于基准的数放到右边，快排在于基准的选择，一般采用随机选择。

• 希尔排序
  多路插入排序，对原数组进行分组，这里分组与归并的分组并不相同，归并的每个分组是连续的。这里并不是连续的。
  希尔排序按照隔一段距离gap取一个数作为分组的元素。对每一个分组只执行一次插入排序，认为分组序列除了最后一位都是有序的

• 堆排序
  建立大顶堆，把根移除了并放入到有序数组中，通常放入到数组后面的有序部分，调整大根堆，反复进行。

代码

冒泡

//交换相邻
public static void bubble1(int[] input) {
        for (int i = 0; i < input.length; i++) {
            for (int j = 1; j < input.length; j++) {
                if (input[j] < input[j - 1]) {
                    int temp = input[j - 1];
                    input[j - 1] = input[j];
                    input[j] = temp;
                }
            }
        }
}

插入

//把当前值逐步向前移动到合适位置
public  static void insert1(int[] input) {
        for (int i = 1; i < input.length; i++) {
            int current = input[i]; // 当前值
            int pre = i - 1;
            while (pre >= 0 && input[pre] > current) {
                input[pre + 1] = input[pre]; //把前一个值往后面移动
                pre--;
            }
            input[pre + 1] = current;
        }
    }

归并--递归实现

public static int[] mergeSort(int[] input) {
        if (input.length <= 1) {
            return input;
        }
        int len = input.length / 2; //分割左右数组
        int[] left = Arrays.copyOfRange(input, 0, len);
        int[] right = Arrays.copyOfRange(input, len, input.length);
        left = mergeSort(left);
        right = mergeSort(right);
        return merge(left, right);
    }

    //把左右两边合并起来成为一个数组，左右两边都是有序的
    public static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        //i为left下标，j为right下标
        for (int index = 0, i = 0, j = 0; index < result.length; index++) {
            if (i >= left.length) {
                result[index] = right[j++];
            } else if (j >= right.length) {
                result[index] = left[i++];
            } else if (left[i] <= right[j]) {
                result[index] = left[i++];
            } else {
                result[index] = right[j++];
            }
        }
        return result;
    }

归并--非递归实现

public static void mergetSort(int[] input) {
        if (input.length <= 1) {
            return;
        }
        int len = 1;
        while (len < input.length) {
            int start = 0;
            while (start + 2 * len - 1 < input.length) {
                int mid = start + len - 1;
                int end = start + 2 * len - 1;
                merge(input, start, mid, end);
                start = start + 2 * len;
            }
            //剩余无法构成完整的两组也要进行处理
            if (start + len - 1 < input.length)
                merge(input, start, start + len - 1, input.length - 1);
            len = len * 2;
        }

    }


    public static void merge(int[] arr, int start, int mid, int end) {
        int i = start;
        int j = mid + 1;
        int[] temp = new int[end - start + 1];
        int index = 0;
        while (i <= mid && j <= end) {
            if (arr[i] <= arr[j])
                temp[index++] = arr[i++];
            else
                temp[index++] = arr[j++];
        }
        while (i <= mid)
            temp[index++] = arr[i++];
        while (j <= end)
            temp[index++] = arr[j++];

        for (int k = start; k <= end; k++)
            arr[k] = temp[k - start];
    }

选择排序

public void seclect1(int[] input) {
        for (int i = 0; i < input.length; i++) {
            //当前值
            int index = i;
            //找出从i->n的最小值
            for (int j = i; j < input.length; j++) {
                if (input[j] < input[index]) {
                    index = j;

                }
            }
            //最小值与当前值交换
            int temp = input[index];
            input[index] = input[i];
            input[i] = temp;
        }
    }

快速排序

/**
     * 快速排序方法
     *
     * @param array
     * @param start  0 ,调用起始值
     * @param end  len-1 ，调用终止值
     */
    public static void quickSort(int[] array, int start, int end){
        if(start < 0 || end >= array.length || start > end) return;

        int smallIndex = partition(array, start, end);//分治界线

        if(smallIndex > start){
            quickSort(array, start, smallIndex - 1);//分治递归
        }

        if(smallIndex < end){
            //System.out.println("debugright:" + smallIndex);
            quickSort(array, smallIndex + 1, end);
        }

    }

    /**
     * 快速排序算法——partition,寻找分解点
     *
     * @param array
     * @param start
     * @param end
     * @return
     */
    public static int partition(int[] array, int start, int end){
        //基准
        int pivot = (int) (start + Math.random() * (end - start + 1));//在start和end之间随机选择一个值作为标准
        int smallIndex = start - 1; //小于基准的指针，标记基准的左边
        swap(array, pivot, end);//将基准准放在end位置
        for(int i = start; i <= end; i++)
        //如果当前值小于基准值，那么基准指针向右走一步
        {
            if(array[i] <= array[end]){
                smallIndex++;
                // 当前值小于基准，进而判断当前值是否在基准的左边，
                // i>samllIndex 把当前值与边界交换，smallIndex++已经对左边进行扩容
                if(i > smallIndex)
                    swap(array, i, smallIndex);
            }
        }
        return smallIndex;
    }

    /**
     * 交换数组内两个元素
     *
     * @param array
     * @param i
     * @param j
     */
    public static void swap(int[] array, int i, int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

希尔排序

public void shellSort(int[] input) {
        int gap = 1;
        //初始分割间隔，len=9=>gap=4
        while (gap < input.length / 3) {
            gap = gap * 3 + 1;
        }
        System.out.println("input.len="+input.length);
        while (gap >= 1) {
            System.out.println("gap:"+gap);
            //  开始一次插入排序，认为每个分组除了最后一位都是有序的
            for (int i = gap; i < input.length; i++) {

                int tmp = input[i]; //当前值
                int j = i - gap;
                while (j >= 0 && input[j] > tmp) {
                    input[j + gap] = input[j];
                    j -= gap;
                }
                input[j + gap] = tmp;
            }
            gap = gap / 3;
            System.out.println(Arrays.toString(input));
        }

    }

堆排序

public static void heapSort(int[] arr) {
        System.out.println("堆排序");

        //构建大顶堆
        for(int i = arr.length / 2 - 1; i >= 0; i--){
            adjustHeap(arr, i, arr.length);
        }
        //堆调整
        int temp;
        //将root元素与最后交换
        for(int i = arr.length - 1; i > 0; i--){
            //交换
            temp = arr[i];  //i表示大顶堆的叶子结点，arr[0-i]存储这个大顶堆。
            arr[i] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, i);
        }
        System.out.println(Arrays.toString(arr));
    }

    //堆的调整
    public static void adjustHeap(int[] arr, int i, int len) {
        int temp = arr[i];
        // 第i个的左子节点为2i+1
        for(int k = 2 * i + 1; k < len; k = 2 * k + 1){
            //k指针指向左右节点较大的那个子结点
            if(k + 1 < len && arr[k] < arr[k + 1]) {
                k++;
            }
            if(arr[k] > arr[i]) {
                arr[i] = arr[k];
                i = k; //i 指向 k  //注意 ，i
            } else {  //子结点小于父节点
                break; //for循环结束之后，已经将以i为父结点的树的最大值放在的最顶（局部）
            }
        }


        arr[i] = temp;
    }

基数排序

public static  int[] sort(int[] sourceArray) {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int maxDigit = getMaxDigit(arr);
        return radixSort(arr, maxDigit);
    }

    /**
     * 获取最高位数
     */
    private static int getMaxDigit(int[] arr) {
        int maxValue = getMaxValue(arr);
        return getNumLenght(maxValue);
    }
    // 获得最大值
    private static int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            maxValue=Math.max(maxValue,value);
        }
        return maxValue;
    }
    // 获得最大度位数
    protected static int getNumLenght(long num) {
        if (num == 0) {
            return 1;
        }
        int lenght = 0;
        for (long temp = num; temp != 0; temp /= 10) {
            lenght++;
        }
        return lenght;
    }
    //基数排序
    private static int[] radixSort(int[] arr, int maxDigit) {
        int mod = 10;
        int dev = 1;

        for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
            // 考虑负数的情况，这里扩展一倍，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
            int[][] counter = new int[mod * 2][0]; //二维数组，列初始值为0，通Append实现保存并扩容

            for (int j = 0; j < arr.length; j++) {
                int bucket = ((arr[j] % mod) / dev) + mod; //+10是把负数变成正数
                counter[bucket] = arrayAppend(counter[bucket], arr[j]);
            }

            int pos = 0;
            for (int[] bucket : counter) {
                for (int value : bucket) {
                    arr[pos++] = value;
                }
            }
        }

        return arr;
    }

    /**
     * 自动扩容，并保存数据
     *
     * @param arr
     * @param value
     */
    private static int[] arrayAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }