Java版排序算法

前提：对int[] 数组 从小到大排序

1、冒泡排序

思想：在待排序的数组中，对当前还未排好序的范围内全部数，自左到右对相邻的两个数进行比较，让较大的数往下沉，较小的数网上冒。
优点：稳定
缺点：慢，时间复杂度 o(n²)

/**
 * @Author: qiweigang
 * @Description: 冒泡排序
 * @Date: Create in 16:17 2019/8/2
 */
public class BubbleSort {

    public static void main(String[] args) {
        int[] array = {10, 2, 5, 8, 1, 6, 7, 8, 9};
        bubbleSort(array);
        System.out.println(Arrays.toString(array));
    }

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

2、快速排序

思想：选择一个基准元素，将比基准元素小的元素放在其前面，比基准元素大的放在后面，然后分别对两个子序列进行此操作，直到整个序列有序。
缺点：不稳定，此算法在序列越乱的时候，效率越高，在数据有序时会退化为冒泡排序
算法优化：在序列长度分割到一定大小后，可以使用插入排序
影响因素：基准的选取，a、取第一个元素 b、随机选取 c、三数取中

package sort;

import java.util.Arrays;

/**
 * @Author: qiweigang
 * @Description: 快速排序
 * @Date: Create in 18:06 2019/8/2
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] array = {10, 2, 5, 8, 1, 6, 7, 8, 9,100,10};
        quickSort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }

    public static void quickSort(int[] array, int begin, int end) {
        if (begin >= end) {
            return;
        }

        int i = begin, j = end;
        int standard = array[begin];
        while (i < j) {
            //因为基准选在最左侧，所以先从右边遍历
            while (i < j && array[j] >= standard) {
                j--;
            }
            while (i < j && array[i] <= standard) {
                i++;
            }

            //左右交换
            if (i < j) {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }

        //和基准交换
        array[begin] = array[i];
        array[i] = standard;

        quickSort(array, begin, i - 1);
        quickSort(array, i + 1, end);
    }

}

3、插入排序

思想：将一个记录插入到已排好的有序序列中，从而得到一个新的记录增1的有序列表。首先将第一个记录看成是有序的，然后从第二个开始逐步插入，直到整个序列有序为止
优点：稳定
缺点：比较次数不一定，比较次数越少，插入点后数据移动越多，越慢

package sort;

import java.util.Arrays;

/**
 * @Author: qiweigang
 * @Description: 插入排序
 * @Date: Create in 17:13 2019/8/8
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] array = {1, 3, 5, 8, 7, 2, 4, 10, 50, 20, 30, 5, 6, 9, 1, 12};
        insertSort(array);
        System.out.println(Arrays.toString(array));
    }

    /**
     * 插入排序算法
     *
     * @param array
     */
    public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            for (int j = i; j > 0; j--) {
                if (array[j] < array[j - 1]) {
                    int temp = array[j];
                    array[j] = array[j - 1];
                    array[j - 1] = temp;
                }
            }
        }
    }

}

4、堆排序

4.1、二叉堆的定义：二叉堆是完全二叉树或近似完全二叉树。满足以下两个特性：
(1)、父结点的值总是大于或者等于任何一个子节点的值 （大顶堆）
(2)、每个结点的左右子树都是一个二叉堆。
使用二叉堆排序思想：
1、先将初始数组构造一个大顶堆，此时数组为无序区。然后将第一个元素和无序区最后一个元素交换。然后再调整数组使其继续满足大顶堆。
算法时间复杂度：o(n*logn)

package sort;

import java.util.Arrays;

/**
 * @Author: qiweigang
 * @Description: 堆排序
 * @Date: Create in 17:23 2019/8/8
 */
public class HeapSort {


    public static void main(String[] args) {
        int[] array = {1, 3, 5, 8, 7, 2, 4, 10, 50, 20, 30, 5, 6, 9, 1, 12};
        heapSort(array);
        System.out.println(Arrays.toString(array));
    }

    /**
     * 堆排序
     *
     * @param array
     */
    public static void heapSort(int[] array) {
        if (array == null || array.length == 1) {
            return;
        }

        buildHeap(array);

        for (int i = array.length - 1; i >= 1; i--) {
            swap(array, 0, i);
            maxHeap(array, i, 0);
        }

    }

    /**
     * 构造大顶堆
     *
     * @param array
     */
    public static void buildHeap(int[] array) {
        int cursor = array.length / 2;
        for (int i = cursor; i >= 0; i--) {
            maxHeap(array, array.length, i);
        }
    }

    /**
     * 大顶堆
     *
     * @param array
     * @param heapSize
     * @param index
     */
    public static void maxHeap(int[] array, int heapSize, int index) {
        int left = 2 * index + 1;//左子节点
        int right = 2 * index + 2;//右子节点
        int maxIndex = index;//暂时定index的位置就是最大值

        if (left < heapSize && array[left] > array[maxIndex]) {
            maxIndex = left;
        }

        if (right < heapSize && array[right] > array[maxIndex]) {
            maxIndex = right;
        }

        if (maxIndex != index) {
            swap(array, index, maxIndex);

            //交换完成后还需要判断子节点是否打破了最大堆的性质：两个子节点都比父节点小
            maxHeap(array, heapSize, maxIndex);
        }

    }

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

}

5、选择排序

基本思想：从第一个元素开始，每次找到最小的元素。直到找到最后一个元素
特点：慢，不稳定，时间复杂度还高

package sort;

import java.util.Arrays;

/**
 * @Author: qiweigang
 * @Description: 选择排序
 * @Date: Create in 18:42 2019/8/8
 */
public class SelectSort {

    public static void main(String[] args) {
        int[] array = {1, 3, 5, 8, 7, 2, 4, 10, 50, 20, 30, 5, 6, 9, 1, 12};
        selectSort(array);
        System.out.println(Arrays.toString(array));
    }

    /**
     * 选择排序
     *
     * @param array
     */
    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int tempIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[tempIndex] > array[j]) {
                    tempIndex=j;
                }
            }
            if (tempIndex != i) {
                int temp = array[i];
                array[i] = array[tempIndex];
                array[tempIndex]=temp;
            }
        }
    }

}

6、归并排序

思想：归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用
优点：稳定排序，速度仅次于快速排序

package sort;

import java.util.Arrays;

/**
 * @Author: qiweigang
 * @Description: 归并排序
 * @Date: Create in 18:51 2019/8/8
 */
public class MergeSort {


    public static void main(String[] args) {
        int[] array = {51, 46, 20, 18, 65, 97, 82, 30, 77, 50};
        mergeSort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }

    public static void mergeSort(int[] array, int low, int high) {
        int mid = (low + high) / 2;
        if (low < high) {
            //左边
            mergeSort(array, low, mid);
            //右边
            mergeSort(array, mid + 1, high);
            //左右归并
            merge(array, low, mid, high);
        }
    }

    public static void merge(int[] array, int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int i = low;
        int j = mid + 1;
        int k = 0;

        //把较小的数先移到新数组中
        while (i <= mid && j <= high) {
            if (array[i] < array[j]) {
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }

        // 把左边剩余的数移入数组
        while (i <= mid) {
            temp[k++] = array[i++];
        }
        // 把右边边剩余的数移入数组
        while (j <= high) {
            temp[k++] = array[j++];
        }
        // 把新数组中的数覆盖nums数组
        for (int k2 = 0; k2 < temp.length; k2++) {
            array[k2 + low] = temp[k2];
        }

    }

}


package sort;

import java.util.Arrays;

/**
 * @Author: qiweigang
 * @Description: 归并排序
 * @Date: Create in 10:50 2019/8/9
 */
public class MergeSort1 {

    public static int[] mergeSort(int[] array, int low, int high) {
        if (low == high) {
            return new int[]{array[low]};
        }

        int mid = low + (high - low) / 2;
        int[] leftArr = mergeSort(array, low, mid);//左有序数组
        int[] rightArr = mergeSort(array, mid + 1, high);//右有序数组
        int[] newArrays = new int[leftArr.length + rightArr.length];

        int m = 0, i = 0, j = 0;
        while (i < leftArr.length && j < rightArr.length) {
            newArrays[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];
        }

        while (i < leftArr.length) {
            newArrays[m++] = leftArr[i++];
        }

        while (j < rightArr.length) {
            newArrays[m++] = rightArr[j++];
        }
        return newArrays;
    }

    public static void main(String[] args) {
        int[] array=new int[]{9,8,7,6,5,4,3,2,10,1};
        int[] newArray = mergeSort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(newArray));
    }

}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • （转）八大排序算法
    概述 排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部...
    蚁前阅读 5,223评论 0赞 52
  • 八大排序算法
    概述 排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部...
    闲云清烟阅读 767评论 0赞 6
  • 八大排序算法
    概述 排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部...
    zwb_jianshu阅读 1,229评论 0赞 0
  • 八大排序算法
    概述 排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部...
    printf200阅读 785评论 0赞 0
  • 排序 29
    1.插入排序—直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到已排序好...
    依依玖玥阅读 1,286评论 0赞 2