TOP

Java快速排序和归并排序详解(一)
2019-08-14 00:08:49 】 浏览:91
Tags:Java 快速 排序 归并 详解

快速排序算法借鉴的是二叉树前序遍历的思想,最终对数组进行排序。


对于数据量比较大的数组排序,由于采用的具有二叉树二分的思想,故排序速度比较快


只适用于顺序存储结构的数据排序(数组 ,ArrayList等),不适用于链式的数据结构


1.取出数组第0个数据


2.从数组最右边开始遍历,如果遍历位置的数据比第0个位置的数据小,将该位置的数据赋值给左边指针停留下的位置。


3.改变遍历方向,从左边开始开始遍历,如果发现左边的数据比第0个位置的数据大,将该位置的数据赋值给2步骤停留下来的位置,并变换方向。


4.循环2、3步骤直到左右遍历到的下标重合
5.将取出的第0个位置的值赋值给循环结束后左右指针停留下的位置


private void quickSort(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }
        int key = array[start];
        int left = start;
        int right = end;
        boolean direction = true;
        L1:
        while (left < right) {
            if (direction) {
                for (int i = right; i > left; i--) {
                    if (array[i] < key) {
                        array[left++] = array[i];
                        right = i;
                        direction = !direction;
                        continue L1;
                    }
                }
                right = left;
            } else {
                for (int i = left; i < right; i++) {
                    if (array[i] > key) {
                        array[right--] = array[i];
                        left = i;
                        direction = !direction;
                        continue L1;
                    }
                }
                left = right;
            }
        }
        array[left] = key;
        quickSort(array, start, left - 1);
        quickSort(array, left + 1, end);


    }


结果测试


@Test
    public void testQuickSort() {
        int[] array = new int[]{1, 3, 4, 10, 2, 5, 6, 9, 7, 8};
        quickSort(array, 0, array.length - 1);
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }


结果打印


1
2
3
4
5
6
7
8
9
10


private void mergeSort(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) >> 1;
        mergeSort(array, left, mid);
        mergeS
Java快速排序和归并排序详解(一) https://www.cppentry.com/bencandy.php?fid=54&id=228538

首页 上一页 1 2 下一页 尾页 1/2/2
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇Java InvocationHandler 与 Proxy.. 下一篇HashMap集合排序方法