探索前沿技术
      展示技术风采

java常见排序算法

/**
 * Copyright (C), 2018-2018, https://blog.fundodoo.com
 * Author:   醉探索戈壁
 * Date:     2018/8/29 下午6:54
 * Description: 冒泡排序
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package blog.fundodoo.com.algorithm;

/**
 *
 * @author 醉探索戈壁
 * @create 2018/8/29 下午6:54
 * @since 1.0.0
 */
public class BubbleSort {

    public static void bubbleSort(int[] list){
        int temp = 0;
        int length = list.length;
        for(int i= 0;i<length;i++){
            for(int j = 0;j<length-1-i;j++){
                if(list[j]>list[j+1]){
                    temp = list[j];
                    list[j] = list[j+1];
                    list[j+1] = temp;
                }
            }
        }
    }
}
/**
 * Copyright (C), 2018-2018, https://blog.fundodoo.com
 * Author:   醉探索戈壁
 * Date:     2018/8/29 下午7:04
 * Description: 堆排序
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package blog.fundodoo.com.algorithm;

/**
 *
 * @author 醉探索戈壁
 * @create 2018/8/29 下午7:04
 * @since 1.0.0
 */
public class HeapSort {

    public static void heapSort(int[] list){
        int length = list.length;

        //将无序堆构造一个大根堆,大根堆有length/2个父节点
        for(int i = length/2 - 1;i >= 0;i--){
            headAdjust(list,i,length);
        }

        //逐步将每个最大的根节点和末尾元素交换,并且再调整其为大根堆
        for(int i = length -1; i > 0;i--){
            swap(list,0,i);
            headAdjust(list,0,i);
        }
    }

    public static void headAdjust(int[] list ,int parent,int length){
        //保存当前父节点
        int temp = list[parent];

        //得到左孩子节点
        int leftChild = 2 * parent +1;

        while (leftChild < length){
            //如果parent有右孩子,则判断左孩子是否小于优孩子
            if(leftChild + 1 < length && list[leftChild] < list[leftChild + 1]){
                leftChild ++ ;
            }
            //父节点大于子节点则不交换
            if (temp >= list[leftChild]){
                break;
            }
            //将较大子节点的值赋给父节点
            list[parent] = list[leftChild];
            //然后将子节点作为父节点
            parent = leftChild;
            //找到该父节点较小的左孩子节点
            leftChild = 2 * parent + 1;
        }
        //将temp值赋给较大的子节点,形成两值交换
        list[parent] = temp;
    }

    //交换数组里两个元素的位置
    public static void swap(int[] list , int top ,int last){
        int temp = list[top];
        list[top]  = list[last];
        list[last] = temp;
    }
}
/**
 * Copyright (C), 2018-2018, https://blog.fundodoo.com
 * Author:   醉探索戈壁
 * Date:     2018/8/29 下午7:23
 * Description: 直接插入排序算法
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package blog.fundodoo.com.algorithm;

/**
 *
 * @author 醉探索戈壁
 * @create 2018/8/29 下午7:23
 * @since 1.0.0
 */
public class InsertSort {

    public static void insertSort(int[] list){
        int length = list.length;

        for (int i=0;i<length;i++){
            int temp = list[i];
            int j;

            for (j = i-1;j>=0 && list[j] > temp;j--){
                list[j+1] = list[j];
            }

            list[j+1] = temp;
        }
    }
}
/**
 * Copyright (C), 2018-2018, https://blog.fundodoo.com
 * Author:   醉探索戈壁
 * Date:     2018/8/29 下午7:28
 * Description: 归并排序
 *    归并排序(Merge Sort)与快速排序思想类似:将待排序数据分成两部分,继续将两个子部分进行递归的归并排序;然后将已经有序的两个子部分进行合并,最终完成排序。
 *       其时间复杂度与快速排序均为O(nlogn),但是归并排序除了递归调用间接使用了辅助空间栈,还需要额外的O(n)空间进行临时存储。从此角度归并排序略逊于快速排序,但是归并排序是一种稳定的排序算法,快速排序则不然。
 *    所谓稳定排序,表示对于具有相同值的多个元素,其间的先后顺序保持不变。对于基本数据类型而言,一个排序算法是否稳定,影响很小,但是对于结构体数组,稳定排序就十分重要。例如对于student结构体按照关键字score进行非降序排序:
 *
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package blog.fundodoo.com.algorithm;

/**
 *
 * @author 醉探索戈壁
 * @create 2018/8/29 下午7:28
 * @since 1.0.0
 */
public class MergeSort {

    /**
     * 归并排序算法
     * @param list     待排序的列表
     * @param tempList 临时列表
     * @param head     列表开始位置
     * @param rear     列表结束位置
     */
    public static void mergeSort(int[] list, int[] tempList, int head, int rear) {
        if (head < rear) {
            // 取分割位置
            int middle = (head + rear) / 2;
            // 递归划分列表的左序列
            mergeSort(list, tempList, head, middle);
            // 递归划分列表的右序列
            mergeSort(list, tempList, middle + 1, rear);
            // 列表的合并操作
            merge(list, tempList, head, middle + 1, rear);
        }
    }

    /**
     * 合并操作(列表的两两合并)
     * @param list
     * @param tempList
     * @param head
     * @param middle
     * @param rear
     */
    public static void merge(int[] list, int[] tempList, int head, int middle, int rear) {
        // 左指针尾
        int headEnd = middle - 1;
        // 右指针头
        int rearStart = middle;
        // 临时列表的下标
        int tempIndex = head;
        // 列表合并后的长度
        int tempLength = rear - head + 1;

        // 先循环两个区间段都没有结束的情况
        while ((headEnd >= head) && (rearStart <= rear)) {
            // 如果发现右序列大,则将此数放入临时列表
            if (list[head] < list[rearStart]) {
                tempList[tempIndex++] = list[head++];
            } else {
                tempList[tempIndex++] = list[rearStart++];
            }
        }

        // 判断左序列是否结束
        while (head <= headEnd) {
            tempList[tempIndex++] = list[head++];
        }

        // 判断右序列是否结束
        while (rearStart <= rear) {
            tempList[tempIndex++] = list[rearStart++];
        }

        // 交换数据
        for (int i = 0; i < tempLength; i++) {
            list[rear] = tempList[rear];
            rear--;
        }
    }
}
/**
 * Copyright (C), 2018-2018, https://blog.fundodoo.com
 * Author:   醉探索戈壁
 * Date:     2018/8/29 下午7:30
 * Description: 快速排序--通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package blog.fundodoo.com.algorithm;

/**
 *
 * @author 醉探索戈壁
 * @create 2018/8/29 下午7:30
 * @since 1.0.0
 */
public class QuickSort {

    /**
     * 快速排序算法
     */
    public static void quickSort(int[] list, int left, int right) {
        if (left < right) {
            // 分割数组,找到分割点
            int point = partition(list, left, right);

            // 递归调用,对左子数组进行快速排序
            quickSort(list, left, point - 1);
            // 递归调用,对右子数组进行快速排序
            quickSort(list, point + 1, right);
        }
    }

    /**
     * 分割数组,找到分割点
     */
    public static int partition(int[] list, int left, int right) {
        // 用数组的第一个元素作为基准数
        int first = list[left];
        while (left < right) {
            while (left < right && list[right] >= first) {
                right--;
            }
            // 交换
            swap(list, left, right);

            while (left < right && list[left] <= first) {
                left++;
            }
            // 交换
            swap(list, left, right);
        }
        // 返回分割点所在的位置
        return left;
    }

    /**
     * 交换数组中两个位置的元素
     */
    public static void swap(int[] list, int left, int right) {
        int temp;
        if (list != null && list.length > 0) {
            temp = list[left];
            list[left] = list[right];
            list[right] = temp;
        }
    }
}
/**
 * Copyright (C), 2018-2018, https://blog.fundodoo.com
 * Author:   醉探索戈壁
 * Date:     2018/8/29 下午7:31
 * Description: 直接选择排序
 * 所谓选择排序,就是每次找到未排序中最小的(最大的也行)元素的位置,找到后与该位置与未排序序列的第一个元素交换值,直到该序列成为有序序列。
 * 初始状态整个序列为无序序列,每次交换都使有序序列的长度加一,无序序列的起始位置后移一位。选择排序的平均时间复杂度为O(n^2),且选择排序相对不稳定。
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package blog.fundodoo.com.algorithm;

/**
 *
 * @author 醉探索戈壁
 * @create 2018/8/29 下午7:31
 * @since 1.0.0
 */
public class SelectionSort {

    /**
     * 直接选择排序算法
     */
    public static void selectionSort(int[] list) {
        int len = list.length ;
        // 要遍历的次数(length-1次)
        for (int i = 0; i < len - 1; i++) {
            // 将当前下标定义为最小值下标
            int min = i;

            // 遍历min后面的数据
            for (int j = i + 1; j <= len - 1; j++) {
                // 如果有小于当前最小值的元素,将它的下标赋值给min
                if (list[j] < list[min]) {
                    min = j;
                }
            }
            // 如果min不等于i,说明找到真正的最小值
            if (min != i) {
                swap(list, min, i);
            }
        }
    }

    /**
     * 交换数组中两个位置的元素
     */
    public static void swap(int[] list, int min, int i) {
        int temp = list[min];
        list[min] = list[i];
        list[i] = temp;
    }

}
/**
 * Copyright (C), 2018-2018, https://blog.fundodoo.com
 * Author:   醉探索戈壁
 * Date:     2018/8/29 下午7:33
 * Description: 希尔排序
 *  Shellsort是最古老的排序算法之一,该算法以其发明者Donald L. Shell的名字命名(1959)。
 *     在ShellSort排序算法之前的算法时间复杂度基本都是O(n2)O(n2),该算法是突破这个时间复杂度的第一批算法之一。
 *     另外 Shellsort 是快速、易于理解和易于实现的。 然而,其复杂度分析有点复杂。
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package blog.fundodoo.com.algorithm;

/**
 *
 * @author 醉探索戈壁
 * @create 2018/8/29 下午7:33
 * @since 1.0.0
 */
public class ShellSort {

    /**
     * 希尔排序算法
     */
    public static void shellSort(int[] list) {
        int len = list.length ;
        // 取增量
        int gap = len / 2;

        while (gap >= 1) {
            // 无序序列
            for (int i = gap; i < len; i++) {
                int temp = list[i];
                int j;

                // 有序序列
                for (j = i - gap; j >= 0 && list[j] > temp; j = j - gap) {
                    list[j + gap] = list[j];
                }
                list[j + gap] = temp;
            }

            // 缩小增量
            gap = gap / 2;
        }
    }

}
/**
 * Copyright (C), 2018-2018, https://blog.fundodoo.com
 * Author:   醉探索戈壁
 * Date:     2018/8/29 下午7:45
 * Description: 测试数组
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package blog.fundodoo.com.algorithm;


/**
 *
 * @author 醉探索戈壁
 * @create 2018/8/29 下午7:45
 * @since 1.0.0
 */
public class AlgorithmTest {

    public static int[] init(){
        int[] list = new int[10000];
        for (int i = 0; i < 10000; i++) {
            list[i] = (int) (Math.random() * 100000);
        }
        return list;
    }

    /**
     * 测试冒泡排序耗费的时间
     */
    public static void testBubble(int[] list) {

        // 冒泡排序
        long start = System.currentTimeMillis();
        BubbleSort.bubbleSort(list);
        long end = System.currentTimeMillis();
        System.out.println("冒泡排序耗费的时间:" + (end - start));
        display(list);
    }

    /**
     * 测试直接插入排序耗费的时间
     */
    public  static void testInsert(int[] list) {

        // 直接插入排序
        long start = System.currentTimeMillis();
        InsertSort.insertSort(list);
        long end = System.currentTimeMillis();
        System.out.println("直接插入排序耗费的时间:" + (end - start));
        display(list);
    }
    /**
     * 测试堆排序排序耗费的时间
     */
    public  static void testHeap(int[] list) {

        long start = System.currentTimeMillis();
        HeapSort.heapSort(list);
        long end = System.currentTimeMillis();
        System.out.println("堆排序排序耗费的时间:" + (end - start));
        display(list);
    }
    /**
     * 测试归并排序排序排序耗费的时间
     */
    public  static void testMerge(int[] list) {

        long start = System.currentTimeMillis();
        MergeSort.mergeSort(list, new int[list.length], 0, list.length - 1);
        long end = System.currentTimeMillis();
        System.out.println("归并排序排序耗费的时间:" + (end - start));
        display(list);
    }
    /**
     * 测试希尔排序耗费的时间
     */
    public  static void testShell(int[] list) {

        // 希尔排序
        long start = System.currentTimeMillis();
        ShellSort.shellSort(list);
        long end = System.currentTimeMillis();
        System.out.println("希尔排序耗费的时间:" + (end - start));
        display(list);
    }
    /**
     * 快速排序耗费的时间
     */
    public  static void testQuick(int[] list) {

        // 快速排序
        long start = System.currentTimeMillis();
        QuickSort.quickSort(list,0, list.length - 1);
        long end = System.currentTimeMillis();
        System.out.println("快速排序耗费的时间:" + (end - start));
        display(list);
    }
    /**
     * 直接选择排序耗费的时间
     */

    public  static void testSelection(int[] list) {

        long start = System.currentTimeMillis();
        SelectionSort.selectionSort(list);
        long end = System.currentTimeMillis();
        System.out.println("直接排序耗费的时间:" + (end - start));
        display(list);
    }
    /**
     * 遍历打印前10个数
     */

    private  static void display(int[] list) {
        System.out.println("********排序之后的前10个数start********");
        if (list != null && list.length > 0) {
            for (int i = 0; i < 10; i++) {
                System.out.print(list[i] + " ");
            }
            System.out.println();
        }
        System.out.println("********排序之后的前10个数end**********");
        System.out.println();
    }

    public static void main(String[] args) {
        int[] list = init();
        testQuick(list);//快速排序
        testShell(list);//希尔排序
        testHeap(list);//堆排序
        testMerge(list);//归并排序
        testSelection(list);//直接排序
        testInsert(list);//直接插入排序
        testBubble(list);//冒泡排序
    }
}
java

java

×

感谢您的支持,我们会一直保持!

扫码支持
请土豪扫码随意打赏

打开支付宝扫一扫,即可进行扫码打赏哦

分享从这里开始,精彩与您同在

赞(0) 打赏
未经允许不得转载:醉探索戈壁 » java常见排序算法
分享到: 更多 (0)
标签:

给戈壁浇点水

支付宝扫一扫打赏

微信扫一扫打赏