java实现各种排序

public class BubbleSort {
   
    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 {
   
    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 {
   
    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 {
   
    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);
    }

    
    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);
        }
    }

    
    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 {
   
    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 {
   
    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("");
        }
    }
}

public class FindMedian {
   //maxHeap保存较小的半边数据，minHeap保存较大的半边数据。
    private static PriorityQueue maxHeap, minHeap;

    public static void main(String[] args) {

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

        maxHeap = new PriorityQueue(100, revCmp);
        minHeap = new PriorityQueue(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());
    }

    
    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);
            }
        }
    }

    
    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();
        }
    }
}