[数据结构与算法]java实现各种排序

/**
 * 冒泡排序
 */
public class BubbleSort {
   /**
    * 冒泡排序，持续比较相邻元素，大的挪到后面，因此大的会逐步往后挪，故称之为冒泡。
    * 复杂度分析：平均情况与最坏情况均为 O(n^2), 使用了 temp 作为临时交换变量，空间复杂度为 O(1).
    */
    public static void main(String[] args) {
        int[] list = {27, 76, 47, 23, 7, 32, 19, 86};
        System.out.println("************冒泡排序************");
        System.out.println("排序前：");
        display(list);
        System.out.println("排序后：");
        bubbleSort(list);
        display(list);
    }

    /**
     * 遍历打印
     */
    public static void display(int[] list) {
        if (list != null && list.length > 0) {
            for (int num :
                    list) {
                System.out.print(num + " ");
            }
            System.out.println("");
        }
    }

    /**
     * 冒泡排序算法
     */
    public static void bubbleSort(int[] list) {
       int len = list.length ;
        // 做多少轮排序（最多length-1轮）
        for (int i = 0; i < len - 1; i++) {
            // 每一轮比较多少个
            for (int j = 0; j < len - 1 - i; j++) {
                if (list[j] > list[j + 1]) {
                    // 交换次序
                   int temp = list[j];
                    list[j] = list[j + 1];
                    list[j + 1] = temp;
                }
            }
        }
    }
}

/**
 * 堆排序
 */
public class HeapSort {
   /**
    * 堆排序的是集合了插入排序的单数组操作，又有归并排序的时间复杂度，完美的结合了2者的优点。
    * 参考：https://www.cnblogs.com/huenchao/p/5906193.html
    */
    public static void main(String[] args) {
       int[] list = {27, 76, 47, 23, 7, 32, 19, 86};
        System.out.println("************堆排序************");
        System.out.println("排序前：");
        display(list);
        System.out.println("排序后：");
        heapSort(list);
        display(list);
    }

    /**
     * 堆排序算法
     */
    public static void heapSort(int[] list) {
        // 将无序堆构造成一个大根堆，大根堆有length/2个父节点
        for (int i = list.length / 2 - 1; i >= 0; i--) {
            headAdjust(list, i, list.length);
        }

        // 逐步将每个最大值的根节点与末尾元素交换，并且再调整其为大根堆
        for (int i = list.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;
    }

    /**
     * 遍历打印
     */
    public static void display(int[] list) {
        if (list != null && list.length > 0) {
            for (int num :list) {
                System.out.print(num + " ");
            }
            System.out.println("");
        }
    }
}

/**
 * 直接插入排序
 */
public class InsertSort {
   /**
    * 直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好的有序的表中，从而得到一个新的、记录数增1的有序表。
　　       * 当前元素的前面元素均为有序，要插入时，从当前元素的左边开始往前找（从后往前找），比当前元素大的元素均往右移一个位置，最后把当前元素放在它应该呆的位置就行了。
     * 参考：https://www.cnblogs.com/mengdd/archive/2012/11/24/2786490.html
    */
    public static void main(String[] args) {
       int[] list = {27, 76, 47, 23, 7, 32, 19, 86};
        System.out.println("************直接插入排序************");
        System.out.println("排序前：");
        display(list);
        System.out.println("排序后：");
        insertSort(list);
        display(list);
    }

    /**
     * 直接插入排序算法
     */
    public static void insertSort(int[] list) {
       int len = list.length ;
        // 从无序序列中取出第一个元素 (注意无序序列是从第二个元素开始的)
        for (int i = 1; i < len; 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;
        }
    }

    /**
     * 遍历打印
     */
    public static void display(int[] list) {
        if (list != null && list.length > 0) {
            for (int num :list) {
                System.out.print(num + " ");
            }
            System.out.println("");
        }
    }
}

/**
 * 归并排序
 */
public class MergeSort {
   /**
    * 归并排序（Merge Sort）与快速排序思想类似：将待排序数据分成两部分，继续将两个子部分进行递归的归并排序；然后将已经有序的两个子部分进行合并，最终完成排序。
    * 其时间复杂度与快速排序均为O(nlogn)，但是归并排序除了递归调用间接使用了辅助空间栈，还需要额外的O(n)空间进行临时存储。从此角度归并排序略逊于快速排序，但是归并排序是一种稳定的排序算法，快速排序则不然。
     * 所谓稳定排序，表示对于具有相同值的多个元素，其间的先后顺序保持不变。对于基本数据类型而言，一个排序算法是否稳定，影响很小，但是对于结构体数组，稳定排序就十分重要。例如对于student结构体按照关键字score进行非降序排序：
    */
    public static void main(String[] args) {
        int[] list = {50, 10, 90, 30, 70};
        System.out.println("************归并排序************");
        System.out.println("排序前：");
        display(list);
        System.out.println("排序后：");
        mergeSort(list, new int[list.length], 0, list.length - 1);
        display(list);
    }

    /**
     * 归并排序算法
     * @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--;
        }
    }

    /**
     * 遍历打印
     */
    public static void display(int[] list) {
        if (list != null && list.length > 0) {
            for (int num :list) {
                System.out.print(num + " ");
            }
            System.out.println("");
        }
    }
}

/**
 * 快速排序
 */
public class QuickSort {
   /**
    * 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
    */
    public static void main(String[] args) {
        int[] list = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
        System.out.println("************快速排序************");
        System.out.println("排序前：");
        display(list);
        System.out.println("排序后：");
        quickSort(list, 0, list.length - 1);
        display(list);
    }

    /**
     * 快速排序算法
     */
    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;
        }
    }

    /**
     * 遍历打印
     */
    public static void display(int[] list) {
        if (list != null && list.length > 0) {
            for (int num :list) {
                System.out.print(num + " ");
            }
            System.out.println("");
        }
    }
}

/**
 * 直接选择排序
 */
public class SelectionSort {
   /**
    * 所谓选择排序，就是每次找到未排序中最小的（最大的也行）元素的位置，找到后与该位置与未排序序列的第一个元素交换值，直到该序列成为有序序列。
    * 初始状态整个序列为无序序列，每次交换都使有序序列的长度加一，无序序列的起始位置后移一位。选择排序的平均时间复杂度为O(n^2)，且选择排序相对不稳定。
    */
    public static void main(String[] args) {
       int[] list = {27, 76, 47, 23, 7, 32, 19, 86};
        System.out.println("************直接选择排序************");
        System.out.println("排序前：");
        display(list);
        System.out.println("排序后：");
        selectionSort(list);
        display(list);
    }

    /**
     * 直接选择排序算法
     */
    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;
    }

    /**
     * 遍历打印
     */
    public static void display(int[] list) {
        if (list != null && list.length > 0) {
            for (int num :list) {
                System.out.print(num + " ");
            }
            System.out.println("");
        }
    }
}

/**
 * 希尔排序
 */
public class ShellSort {
   /**
    * Shellsort是最古老的排序算法之一，该算法以其发明者Donald L. Shell的名字命名（1959）。
    * 在ShellSort排序算法之前的算法时间复杂度基本都是O(n2)O(n2)，该算法是突破这个时间复杂度的第一批算法之一。
    * 另外 Shellsort 是快速、易于理解和易于实现的。 然而，其复杂度分析有点复杂。
    */
    public static void main(String[] args) {
       int[] list = {27, 76, 47, 23, 7, 32, 19, 86};
        System.out.println("************希尔排序************");
        System.out.println("排序前：");
        display(list);
        System.out.println("");

        System.out.println("排序后：");
        shellSort(list);
        display(list);
    }

    /**
     * 希尔排序算法
     */
    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;
        }
    }

    /**
     * 遍历打印
     */
    public static void display(int[] list) {
        if (list != null && list.length > 0) {
            for (int num :list) {
                System.out.print(num + " ");
            }
            System.out.println("");
        }
    }
}

/**
 * 
 * 百亿数据中取中位数
 * 场景：股市上一个股票的价格从开市开始是不停的变化的，需要开发一个系统，给定一个股票，它能实时显示从开市到当前时间的这个股票的价格的中位数（中值）。
 * 创建者 柒
 * 创建时间    2018年12月21日
 */
public class FindMedian {
   //maxHeap保存较小的半边数据，minHeap保存较大的半边数据。
    private static PriorityQueue<Integer> maxHeap, minHeap;

    public static void main(String[] args) {

        Comparator<Integer> revCmp = new Comparator<Integer>() {
            @Override
            public int compare(Integer left, Integer right) {
                return right.compareTo(left);
            }
        };

        maxHeap = new PriorityQueue<Integer>(100, revCmp);
        minHeap = new PriorityQueue<Integer>(100);
        Random ra =new Random();
        for(int i=0;i<=100;i++){
           int number = ra.nextInt(200);
           addNumber(number);
        }
        System.out.println(minHeap);
        System.out.println(maxHeap);
        System.out.println(getMedian());
    }

    /*
     * offer 新增元素
     * peek 头部查询元素
     * poll 队列中删除从头部
     * 1)比较两个堆的大小，第一次肯定相同，此时两个堆都没有数据，把第一个数据放入大堆
     * 2)比较两个堆的大小，第二次肯定不同，如果value值小于大堆头部的值，小堆加入大堆头部元素，大堆加入当前值
     * 注意：
     * 并不是线程安全的，多线程访问操作会有并发问题
     */
    public static void addNumber(int value) {
        if (maxHeap.size() == minHeap.size()) {
            if (minHeap.peek() != null && value > minHeap.peek()) {
                maxHeap.offer(minHeap.poll());
                minHeap.offer(value);
            } else {
                maxHeap.offer(value);
            }
        } else {
            if (value < maxHeap.peek()) {
                minHeap.offer(maxHeap.poll());
                maxHeap.offer(value);
            } else {
                minHeap.offer(value);
            }
        }
    }

    /*
     * If maxHeap and minHeap are of different sizes, 
     * then maxHeap must have one extra element.
     */
    public static double getMedian() {
        if (maxHeap.isEmpty()) {
            return -1; 
        }
        
        if (maxHeap.size() == minHeap.size()) {
            return (double)(minHeap.peek() + maxHeap.peek())/2;
        } else {
            return maxHeap.peek();
        }
    }
}