关于算法:数据结构与算法基础排序

43次阅读

共计 964 个字符,预计需要花费 3 分钟才能阅读完成。

「数据结构与算法」根底排序

替换排序:

  • 疾速排序
  • 冒泡排序

替换排序

疾速排序

思路:

在数组中找一个元素 (节点),比它小的放在节点的右边,比它大的放在节点左边。一趟下来,比节点小的在右边,比节点大的在左边。
一直执行这个操作 …

实现:

    public static void quickSort(int[] array, int l, int r) {
        int leftPos = l;
        int rightPos = r;

        // 支点
        // 该值能够选任意值
        int pivot = array[(l + r) / 2];

        // 支点右边的值全副小于支点
        // 支点左边的值全副大于支点
        while (leftPos <= rightPos) {
            // 从左开始,寻找比支点大的地位
            while (array[leftPos] < pivot) {leftPos++;}

            // 从右开始,寻找比支点小的地位
            while (array[rightPos] > pivot) {rightPos--;}

            if (leftPos <= rightPos) {
                // 替换左右数值
                int temp = array[leftPos];
                array[leftPos] = array[rightPos];
                array[rightPos] = temp;
                leftPos++;
                rightPos--;
            }
        }

        if (rightPos > l) {quickSort(array, l, rightPos);
        }

        if (leftPos < r) {quickSort(array, leftPos, r);
        }
    }

冒泡排序

思路:

俩俩替换,大的放在前面,第一次排序后最大值已在数组开端
因为俩俩替换,须要 n-1 趟排序,比方 10 个数,须要 9 趟排序

实现:

    public static void popupSort(int[] array) {
        // 每一轮把最大的值像冒泡泡一样冒到最初一位
        for (int i = 0; i < array.length - 1; i++) {
            // 判断是否批改
            boolean isChange = false;
            for (int j = 0; j < array.length - 1 - i; j++) {if (array[j] > array[j + 1]) {int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;

                    isChange = true;
                }
            }

            // 若无批改代表数组曾经有序
            if (isChange == false) {break;}
        }
    }

正文完
 0