Java 데이터 구조에 대한 일반적인 정렬 알고리즘(요약 공유)

이 기사에서는 직접 삽입 정렬, Hill 정렬(증분 정렬 감소), 선택 정렬, 힙 정렬 등 몇 가지 일반적인 정렬 알고리즘을 주로 소개하는 Java에 대한 관련 지식을 제공합니다. 모두에게 도움이 될 것입니다.

1. 순서 이해하기

학교에서 운동회나 군사훈련에 참가하고 싶다면 수업시간에 선생님이 들고 계시는 출석부처럼 키가 작은 것부터 긴 것까지 줄을 서게 됩니다. , 일반적으로 학생 수에 따라 낮은 것부터 높은 것까지 정렬됩니다. 또 다른 예는 역시 정렬된 프로그래밍 언어 순위입니다.

정렬이 여전히 매우 중요하다는 것을 알 수 있습니다. 이 장에서는 몇 가지 일반적인 정렬 알고리즘을 소개합니다.

위의 예를 보면 소위 정렬은 하나 또는 일부 키워드의 크기에 따라 오름차순 또는 내림차순으로 정렬하는 작업입니다. 이는 정렬의 안정성과도 관련됩니다.

예를 들어 B D A C A F와 같은 데이터 세트가 있는데, 이는 ascll 코드에 따라 정렬되어야 합니다. 여기에는 두 개의 A가 표시되며, 두 번째 A는 A2라고 합니다. .

정렬 후 결과가 A1 A2 B C D F라고 가정하면 이 정렬 알고리즘은 안정적입니다.

정렬 후 결과가 A2 A1 B C D F라고 가정하면 이 정렬 알고리즘은 불안정합니다.

정렬할 데이터에 동일한 요소가 두 개 있는 경우 정렬이 완료된 후에도 두 요소 간의 관계는 변경되지 않습니다. 예를 들어 정렬 전 A1이 A2 앞에 있습니다. 여전히 A2 앞에선 안정적인 정렬 알고리즘입니다.

참고: 불안정한 정렬 알고리즘은 본질적으로 불안정하지만 안정적인 정렬 알고리즘은 불안정하도록 설계될 수 있습니다.

2. 일반적인 정렬의 분류

이 그림은 나중에 이야기할 정렬 알고리즘을 요약한 것이며, 본격적으로 이번 장의 학습에 들어갑니다! (정렬 알고리즘 장에서는 기본값이 오름차순입니다.) 참고: 나중에 언급되는 복잡도 로그는 2를 기준으로 하며 특수한 로그는 표시됩니다.

3. 직접 삽입 정렬

이제 여러분이 카드 놀이를 하고 있다고 상상해 보시기 바랍니다. 첫 번째 카드를 터치하고 손에 넣은 다음 다른 카드를 터치하고 이것을 넣습니다. 손에 있는 카드를 비교하여 적절한 위치에 놓은 다음, 이 카드를 손에 있는 두 장의 카드와 비교하여 적절한 위치에 놓습니다.

간단히 말하면, 매번 가져오는 요소를 순서대로 삽입하는 것입니다. 즉, 각 카드를 뽑기 전에 손에 있는 카드만 비교하면 됩니다. 새로 뽑은 카드를 주문한 카드와 함께 손에 들고 적절한 위치에 놓기만 하면 됩니다!

여기에서는 정적 그림을 사용하여 간략하게 설명합니다.

우리는 이미 일반적인 아이디어를 이해했으며 이를 구현하려면 코드를 사용해야 합니다.

public void insertSort(int[] array) {
    // 外循环控制趟数, 第一张牌默认有序, 所以 i 从 1 开始
    for (int i = 1; i < array.length; i++) {
        int tmp = array[i]; //当前摸到的牌
        // 每次从手中牌的最后一张牌开始比较, 一直比到第一张牌
        int j = i - 1;
        for (; j >= 0; j--) {
            //如果当前位置的牌,大于我摸到的牌,就往后挪
            if (array[j] > tmp) {
                array[j + 1] = array[j];
            } else {
                break;
            }
        }
        // 把摸到的牌放到对应位置上
        array[j + 1] = tmp;
    }
}

• 시간 복잡성 분석: 외부 루프는 총 n - 1 번 필요하며, 최악의 경우 내부 루프는 1...n 번 비교해야 합니다. 그런 다음 n 앞의 작은 항, 즉 (n - 1) * n 번을 제거합니다. 즉, n^2 - n, 최소 항을 제거하면 최종 시간 복잡도는 O(n^2)
• 공간 복잡도 분석: 단지 tmp 변수 i, j, 상수를 엽니다. , 공간 복잡성 정도: O(1)
• 안정성: 안정적
• 데이터가 이 정렬의 질서 있는 상황에 가까울수록 시간 효율성이 높아집니다.

4. 힐 정렬(증분 정렬 감소)

이 정렬은 직접 삽입 정렬을 최적화한 것입니다. 앞에 8개의 사랑 번호판이 나란히 놓여 있다고 상상할 수 있지만 그 수는 무한합니다. 요구 사항에 따라 첫 번째 시간 간격은 4개의 번호판을 그룹화한 후 두 번째 시간 간격은 2개의 번호판을 그룹으로 정렬합니다. 삽입정렬을 수행하며, 세 번째 간격은 번호판 1개를 그룹으로 하여 직접 삽입정렬을 수행한다.

이 말을 들으면 조금 불분명합니다. 위에서 말한 내용을 다시 그림으로 이해해 보겠습니다.

由上图我们可以发现，当间隔 > 1 的时候，都是预排序，也就是让我们的数据更接近有序，但是当间隔为 1 的时候，就是直接插入排序了，前面我们说过，直接插入排序，再数据接近有序的时候时间效率是很快的。由此可见，希尔排序，是直接插入排序的优化版。

如何在代码中实现呢？间隔的值如何取呢？代码中把这个间隔的值称为 gap，这个 gap 的取值方法有很多，有的人提出 gap 为奇数好，有的提出 gap 为偶数好，我们就采取一种比较简单的方法来取 gap 值，首次取数组长度一半的值为 gap，后续 gap /= 2，即可。当 gap 为 1，也就是直接插入排序了。

代码实现如下：

public void shellSort(int[] array) {
    // gap初始值设置成数组长度的一半
    int gap = array.length >> 1;
    // gap 为 1 的时候直接插入排序
    while (gap >= 1) {
        shell(array, gap);
        gap >>= 1; // 更新 gap 值 等价于 -> gap /= 2;
    }
}
private void shell(int[] array, int gap) {
    for (int i = gap; i < array.length; i++) {
        int tmp = array[i];
        int j = i - gap;
        for (; j >= 0; j -= gap) {
            if (array[j] > tmp) {
                array[j + gap] = array[j];
            } else {
                break;
            }
        }
        array[j + gap] = tmp;
    }
}

如果实在是不好理解，就结合上边讲的直接插入排序来理解，相信你能理解到的。

• 时间复杂度分析：希尔排序的时间复杂度不好分析， 这里我们就大概记一下，约为 O(n^1.3)，感兴趣的话，可以查阅一下相关书籍。
• 空间复杂度分析：仍然开辟的是常数个变量，空间复杂度为 O(1)
• 稳定性：不稳定

5、选择排序

这个排序是个很简单的排序，你想象一下，有个小屁孩，喜欢玩小球，我给他安排了个任务，把这一排小球从小到大排列起来，摆给我看，于是小屁孩就找，每次从一排小球中找出最大的，放到最后，固定不动，那是不是也就是说，每次能确定一个最大的石子的最终位置了。我们来看图：

通过图片我们也能看出来，每次找到最大值于最后一个值交换，所以每趟都能把最大的放到最后固定不动，每趟能排序一个元素出来，那这样用代码来实现就很简单了：

public void selectSort(int[] array) {
    int end = array.length - 1;
    // 剩最后一个元素的时候, 不用比较了, 已经有序了
    // 所以 i < array.length - 1
    for (int i = 0; i < array.length - 1; i++) {
        int max = 0;
        int j = 0;
        while (j <= end) {
            if (array[j] > array[max]) {
                max = j;
            }
            j++;
        }
        //找到了最大值的下标, 把最大值与最后一个值交换
        swap(array, max, end--); // end-- 最后一个元素固定了, 不用参与比较
    }
}

这个算法有没有可以优化的空间呢？

有！那么既然小屁孩能一次找出最大的球，那能不能让小屁孩一次找出两个球出来呢？分别是这些球中，最大的和最小的，最大的放在最右边，最小的放在最左边，那么我们每次就能确定两个球的最终位置，也就是我们一次能排序两个元素。图解：

代码实现如下：

public void selectSort(int[] array) {
    int left = 0;
    int right = array.length - 1;
    while (left < right) {
        int maxIndex = left;
        int minIndex = left;
        // i = left + 1 -> 每次找最大最小值下标的时候, 可以不用算默认给的最大值和最小值下标
        for (int i = left + 1; i <= right; i++) {
            if (array[i] > array[maxIndex]) {
                maxIndex = i;
            }
            if (array[i] < array[minIndex]) {
                minIndex = i;
            }
        }
        swap(array, minIndex, left);
        // 如果最大值为 left 的位置情况的话, 走到这, 最大值已经被交换到 min 位置上了
        if (maxIndex == left) {
            // 更新最大值的位置
            maxIndex = minIndex;
        }
        swap(array, maxIndex, right);
        left++;
        right--;
    }
}

• 时间复杂度分析：虽然是优化了，但去小项之后，还是 O(n^2)
• 空间复杂度分析：O(1)
• 稳定性：不稳定
• 实际开发中用的不多

6、堆排序

如果你有学习过优先级队列，或者看过博主优先级队列的文章，那么这个排序对于你来说还是很轻松的，当然在堆排序的讲解中，不会过多的去介绍堆的概念，如果对这部分概念还不理解，可以移至博主的上一篇文章进行学习。

堆排序，简单来说，就是把一组数据，看成一个完全二叉树，再把这棵树，建大堆或者建小堆，接着进行排序的一种思路。至于如何建大堆或小堆，和向上调整算法以及向下调整算法，这里也不多介绍了，博主的上篇文章都详细介绍过。

这里我们来分析一下，排升序应该建什么堆？大堆！排降序建小堆！

这里我们来排升序，建大堆，因为大堆堆顶元素一定是堆中最大的，所以我们可以把堆顶元素和最后一个元素进行交换，这样我们就确认了最大值的位置，接着将交换后的堆顶元素进行向下调整，仍然使得该数组满足大堆的特性！图解如下：

如上图步骤也很简单，先是将数组建成大堆，然后利用大堆来进行堆排序，首先将堆顶元素和最后一个元素交换，由此最大的元素就有序了，接着将该堆进行向下调整，使继续满足大堆性质，依次进行下去即可。

代码实现：

public void heapSort(int[] array) {
    // 建大堆 从最后一个非叶子节点开始向下调整
    // 非叶子节点下标 = (孩子节点下标 - 1) / 2
    for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
        shiftDown(array, parent, array.length);
    }
    // 建大堆完成后, 每次堆顶元素与最后一个元素交换, 锁定最大元素的位置
    for (int len = array.length - 1; len > 0; len--) {
        swap(array, 0, len); //根节点与最后一个元素交换
        shiftDown(array, 0, len); //根节点位置向下调整
    }
}
private void shiftDown(int[] array, int parent, int len) {
    int child = parent * 2 + 1;
    while (child < len) {
        if (child + 1 < len && array[child + 1] > array[child]) {
            child++;
        }
        // 判断父节点是否大于较大的孩子节点
        if (array[parent] < array[child]) {
            swap(array, parent, child);
            // 更新下标的位置
            parent = child;
            child = parent * 2 + 1;
        } else {
            return;
        }
    }
}

• 时间复杂度分析：建堆的时间复杂度优先级队列那期有说过为 O(n)，排序调整堆的时候，一共要调整 n-1 次，每次向下调整的时间复杂度是 logn，所以即 logn(n - 1)，即 O(n*logn)，加上面建堆的时间复杂度：O(n) + O(n*logn)，最终时间复杂度也就是：O(n*logn)。
• 空间复杂度分析：O(1)
• 稳定性：不稳定

推荐学习：《java视频教程》

위 내용은 Java 데이터 구조에 대한 일반적인 정렬 알고리즘(요약 공유)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!