当前位置:首页 » 《资源分享》 » 正文

【用Java学习数据结构系列】七大排序要悄咪咪的学(直接插入,希尔,归并,选择,堆排,冒泡,快排)以及计数排序(非比较排序)

12 人参与  2024年10月28日 08:41  分类 : 《资源分享》  评论

点击全文阅读


 看到这句话的时候证明:此刻你我都在努力

加油陌生人

个人主页:Gu Gu Study
专栏:用Java学习数据结构系列
喜欢的一句话: 常常会回顾努力的自己,所以要为自己的努力留下足迹

喜欢的话可以点个赞谢谢了。
作者:小闭


前言

今天就写一篇关于排序的文章,本文章包含了,如标题所写的八大排序。八大排序各有各的使用场景,在某个特定场景,那么可能有一个排序就非常适合,所以排序我们是多多益善。


直接插入排序(Straight Insertion Sort)

直接插入排序(Straight Insertion Sort)是一种简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

排序特点:

稳定性:直接插入排序是稳定的排序算法,因为相等的元素的相对顺序不会改变。

时间复杂度:在最好的情况下(数组已经是排序的),时间复杂度为O(n);在最坏的情况下(数组是逆序的),时间复杂度为O(n^2);平均时间复杂度为O(n^2)。

空间复杂度:由于直接插入排序是原地排序,不需要额外的存储空间,所以空间复杂度为O(1)。

排序适用场景:

数据规模较小:直接插入排序由于其简单性,适用于数据规模较小的情况。

部分已经排序:如果数组部分已经排序,直接插入排序的性能会比较好。

代码实现:

public static void insetSort(int[] array) {    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;    }}

排序实现:

从第一个元素开始,该元素可以认为已经被排序。取出下一个元素,在已经排序的元素序列中从后向前扫描。如果该元素(已排序)大于新元素,将该元素移到下一位置。重复步骤3,直到找到已排序的元素小于或者等于新元素的位置。将新元素插入到该位置后,即挑出循环直接给array[j+1]赋值,然后重复步骤2~4。对于所有的元素重复步骤1~5

希尔排序(Shell Sort)

希尔排序(Shell Sort)是一种经典的排序算法,由Donald Shell在1959年提出。它是插入排序的一种改进版,也称为缩小增量排序。希尔排序的核心思想是将待排序的序列分割成若干子序列,对每个子序列进行插入排序,随着增量的逐渐减小,子序列逐渐合并,最终整个序列变得有序。

排序特点:

希尔排序是不稳定的排序算法,因为相同元素可能在排序过程中改变相对位置。

它的时间复杂度在最坏情况下为O(n^2),但平均情况下通常为O(nlogn)到O(n^(3/2)),这取决于增量序列的选择。

希尔排序的空间复杂度为O(1),因为它是一种原地排序算法。

适用场景:

希尔排序适用于中等规模的数据排序,因为它比简单的插入排序有更快的效率,但比快速排序和归并排序慢。在数据规模不是特别大的情况下,希尔排序可以作为一个不错的选择。

复杂度分析:

希尔排序的性能与增量序列的选择密切相关。一个好的增量序列可以使得算法在最坏情况下的时间复杂度接近O(nlogn)。然而,目前还没有找到一个通用的最优增量序列,这仍然是一个开放的数学问题。

代码实现:

public static void shellSort(int[] array) {    int gap = array.length;    while (gap > 1) {        gap = gap / 2;        shell(array, gap);    }}private static 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;    }}

排序实现:

选择一个增量序列,常见的选择是将增量逐渐缩小,例如初始增量为gap/2,然后每次缩小一半,直到增量为1。按照增量将待排序序列分割成若干子序列,每个子序列的元素在原序列中间隔增量个位置。对每个子序列进行插入排序。逐步缩小增量,重复步骤2和3,直到增量减小到1,此时对整个序列进行插入排序。

选择排序(Selection Sort)

选择排序(Selection Sort)是一种简单直观的比较排序算法。它的工作原理是每次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。

算法特点:

选择排序是一种不稳定的排序算法,因为相同的元素可能因为排序而改变顺序。

它的时间复杂度为O(n^2),其中n是序列的长度。无论数组是否已经排序,选择排序的性能都是最差的。

选择排序的空间复杂度为O(1),因为它是一种原地排序算法,不需要额外的存储空间。

适用场景:

选择排序由于其简单性,适用于数据规模较小的情况。在数据规模较大时,由于其时间复杂度较高,通常不推荐使用。

性能分析:

最好、最坏和平均时间复杂度都是O(n^2)。

空间复杂度为O(1)。

代码实现:

public static void selectSort2(int[] array) {    for (int i = 0; i < array.length; i++) {        int mindIndex = i;        for (int j = i + 1; j < array.length; j++) {            if (array[j] < array[mindIndex]) {                mindIndex = j;            }        }        swap(array, i, mindIndex);    }}private static void swap(int[] array, int i, int j) {    int tmp = array[i];    array[i] = array[j];    array[j] = tmp;}

排序实现:

找到最小值:从未排序的序列中找到最小(或最大)的元素。交换:将找到的最小(或最大)元素与序列的起始位置交换。重复查找:从剩余的未排序元素中继续寻找最小(或最大)元素,然后与下一个位置交换,重复这个过程。结束:当所有元素都被排序时,算法结束。

我们也可以对这个排序进行优化,即:让数组两边都开始找,一边找最大值,一边找最小值。

优化后的选择排序:

public static void selectSort(int[] array) {    int left = 0;    int right = array.length - 1;    while (left < right) {        int minIndex = left;        int maxIndex = left;        for (int i = left + 1; i <= right; i++) {            if (array[i] < array[minIndex]) {                minIndex = i;            }            if (array[i] > array[maxIndex]) {                maxIndex = i;            }        }        swap(array, left, minIndex);        //最大值正好是  left下标  此时 把最大值换到了minIndex的位置了        if (maxIndex == left) {            maxIndex = minIndex;        }        swap(array, right, maxIndex);        left++;        right--;    }}

冒泡排序(Bubble Sort)

冒泡排序(Bubble Sort)是一种简单的排序算法,它重复地遍历待排序的序列,比较每对相邻元素,如果它们的顺序错误就把它们交换过来,遍历序列的工作重复进行,直到没有再需要交换的元素,这表明序列已经排序完成。

排序特点:

冒泡排序是一种稳定的排序算法,因为它不会改变相同元素之间的顺序。

它的时间复杂度为O(n^2),在所有情况下都是如此,无论是最好、最坏还是平均情况。

冒泡排序的空间复杂度为O(1),因为它是原地排序,不需要额外的存储空间。

适用场景:

冒泡排序由于其简单性,适用于数据规模较小且要求稳定性的场景。在数据规模较大时,由于其时间复杂度较高,通常不推荐使用。

代码实现:

public static void bubbleSort(int[] array) {    for (int i = 0; i < array.length - 1; i++) {        boolean flg = false;        for (int j = 0; j < array.length - 1 - i; j++) {            if (array[j] > array[j + 1]) {                swap(array, j, j + 1);                flg = true;            }        }        if (!flg) {            break;        }    }}

排序步骤:

比较相邻的元素:从第一个元素开始,比较相邻的元素对,如果它们的顺序错误(即前一个比后一个大),就交换它们。交换元素:对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在一趟遍历中,最大的元素会移动到它最终的位置。重复遍历:针对所有的元素重复以上的步骤,除了最后一个已经排好的元素。优化:在每次遍历中,最大的元素会移动到序列的末端,因此下一次遍历时可以忽略这个元素,即减少下一次遍历的序列长度。

堆排序(Heap Sort)

堆排序(Heap Sort)是一种高效的比较类排序算法,利用了二叉堆的数据结构来实现。堆是一个满足以下性质的完全二叉树:对于最大堆,父节点的值总是大于或等于它的子节点的值;对于最小堆,父节点的值总是小于或等于它的子节点的值。

排序特点:

堆排序是一种选择排序,它不改变相同元素之间的顺序,因此是一种稳定的排序算法。

它的时间复杂度为O(nlogn),无论是最好、最坏还是平均情况。

堆排序的空间复杂度为O(1),因为它是原地排序,不需要额外的存储空间。

适用场景:

堆排序适用于数据规模较大且对排序效率有一定要求的场景。由于其时间复杂度稳定,它在很多情况下都是一个不错的选择。

复杂度分析:

时间复杂度:O(nlogn)。

空间复杂度:O(1)。

代码实现:

public static void heapSort(int[] array) {    createHeap(array);    int end = array.length - 1;    while (end > 0) {        swap(array, 0, end);        siftDown(array, 0, end);        end--;    }}private static void createHeap(int[] array) {    for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {        siftDown(array, parent, array.length);    }} private static void siftDown(int[] array, int parent, int length) {        int child = 2 * parent + 1;        while (child < length) {            if (child + 1 < length && array[child] < array[child + 1]) {                child++;            }            if (array[child] > array[parent]) {                swap(array, parent, child);                parent = child;                child = 2 * parent + 1;            } else {                break;            }        }    }

排序步骤:

建立最大堆:将待排序的序列构造成一个最大堆,即父节点的值总是大于或等于它的子节点的值。交换并调整堆:将堆顶元素(最大值)与序列的最后一个元素交换,然后将序列的最后一个元素移除(即排序完成),并对交换后的堆进行调整,使其继续保持最大堆的性质。重复交换和调整:重复步骤2,直到整个序列排序完成。

注意:这里我们将建堆和向下调整单独封装成单个私有函数。


快速排序(Quick Sort)

快速排序(Quick Sort)是一种高效的排序算法,由C. A. R. Hoare在1960年提出。它采用分治法(Divide and Conquer)的策略来对一个数组进行排序。但是他最坏的情况时间复杂度为O(n^2),但是下面我们将用到三数取中法,范围内进行直接插入排序来优化快排,在一般情况下快排还是很高效的。

排序特点:

快速排序是一种分治法策略的应用,它将一个大问题分解成小问题解决。

它是一个原地排序(不需要额外存储空间)。

快速排序是非稳定的排序算法,相同元素的相对顺序可能会改变。

在平均状况下,快速排序的时间复杂度为O(nlogn),但最坏情况下会退化到O(n^2)。

适用场景:

快速排序适用于大部分需要排序的场景,尤其是数据规模较大的情况。它通常比其他O(nlogn)算法更快,因为它的内部循环非常高效。

性能分析:

最佳和平均时间复杂度:O(nlogn)。

最坏时间复杂度:O(n^2),当数据已经是有序或接近有序时(包括逆序)。

空间复杂度:O(logn),递归栈的深度。

public static void quick(int[] array, int start, int end) {    if (start >= end) {        return;    }    if (end - start + 1 <= 7) {        insertSortRange(array, start, end);        return;    }       int midIndex = getMiddleNum(array, start, end);    swap(array, start, midIndex);    int pivot = partition(array, start, end);    quick(array, start, pivot - 1);    quick(array, pivot + 1, end);}private static void insertSortRange(int[] array, int start, int end) {    for (int i = start + 1; i <= end; i++) {        int tmp = array[i];        int j = i - 1;        for (; j >= start; j--) {            if (array[j] > tmp) {                array[j + 1] = array[j];            } else {                array[j + 1] = tmp;                break;            }        }        array[j + 1] = tmp;    }}private static int getMiddleNum(int[] array, int left, int right) {    int mid = (left + right) / 2;    if (array[left] < array[right]) {        if (array[mid] < array[left]) {            return left;        } else if (array[mid] > array[right]) {            return right;        } else {            return mid;        }    } else {        if (array[mid] > array[left]) {            return left;        } else if (array[mid] < array[right]) {            return right;        } else {            return mid;        }    }}private static int partition(int[] array, int left, int right) {        int tmp = array[left];        while (left < right) {            while (left < right && array[right] >= tmp) {                right--;            }            array[left] = array[right];            while (left < right && array[left] <= tmp) {                left++;            }            array[right] = array[left];        }        array[left] = tmp;        return left;    }

这里展示的是经过优化后的快排,这样的快排就不会那么容易出现时间复杂度为:O(n^2)的情况

排序步骤:

选择基准值:在数据集之中,选择一个元素作为基准值(pivot)。分区操作:重新排列数据集,比基准值小的元素摆放在基准前面比基准值大的元素摆在基准后面,相等的则可以放到任一边。在这个分区退出之后,该基准就处于集合的中间位置。递归排序:递归地将小于基准值的子数组和大于基准值的子数组排序。

然后就是优化部分:

首先我们在递归过程中如果此时子数组的长度小于等于7时,我们就对这个数组进行直接插入排序,因为这时数组其实已经趋于有序,这时使用直接插入排序的效率是比较高的。然后我们取基准值时我们尽量取数组中值比较中间得数作为基准值(pviot),这样也可以提高快排得效率。


归并排序(Merge Sort)

归并排序(Merge Sort)是一种高效的比较排序算法,采用分治法(Divide and Conquer)的一个典型应用。它将数组分成两半,对每一半递归地进行排序,然后将结果归并(合并)起来。

排序特点:

归并排序是稳定的排序算法,它保持相同元素的相对顺序不变。

它的时间复杂度为O(nlogn),无论是最好、最坏还是平均情况。

归并排序的空间复杂度为O(n),因为它需要额外的空间来存储合并后的数组。

适用场景:

归并排序适用于数据规模较大且需要稳定排序结果的场景。它在外部排序(数据太大,无法一次性加载到内存中)中特别有用。

复杂度分析:

时间复杂度:O(nlogn)。

空间复杂度:O(n)。

private static void mergeSortTmp(int[] array, int left, int right) {    if (left >= right) {        return;    }    int mid = (left + right) / 2;    mergeSortTmp(array, left, mid);    mergeSortTmp(array, mid + 1, right);    //走到这里 全部分解完毕    // 合并    merge(array, left, mid, right);}private static void merge(int[] array, int left, int mid, int right) {    int[] tmp = new int[right - left + 1];    int k = 0;    int s1 = left;        int s2 = mid + 1;       while (s1 <= mid && s2 <= right) {        if (array[s1] <= array[s2]) {            tmp[k++] = array[s1++];        } else {            tmp[k++] = array[s2++];        }    }    while (s1 <= mid) {        tmp[k++] = array[s1++];    }    while (s2 <= right) {        tmp[k++] = array[s2++];    }    //可以保证tmp数组 是有序的    for (int i = 0; i < k; i++) {        array[i + left] = tmp[i];    }}

排序步骤:

分解:将当前序列从中间分成两个子序列。递归排序:递归地对两个子序列进行归并排序。合并:将两个排序好的子序列合并成一个最终的排序序列。

计数排序(Counting Sort)

计数排序一个不需要进行比较也能进行排序的排序方式,是不是觉得很神奇呢。那么下面我们就看看吧。

计数排序(Counting Sort)是一种非比较型整数排序算法,其核心思想是使用一个额外的数组(称为计数数组)来统计待排序数组中每个元素的出现次数,然后根据这些计数来确定每个元素在排序数组中的位置。

排序特点:

计数排序是一种稳定的排序算法,它不会改变相同元素之间的相对顺序。

它的时间复杂度为O(n+k),其中n是待排序数组的长度,k是待排序数组中最大和最小值的差。

计数排序的空间复杂度为O(k),因为需要额外的数组来存储计数信息。

适用场景:

计数排序适用于整数排序,特别是当整数的数值范围不是很大时。它在处理大量数据时非常高效,尤其是当数据分布比较均匀时。

性能分析:

时间复杂度:O(n+k),n是数组长度,k是数值范围。空间复杂度:O(k)。
public static void countSort(int[] array) {    //1. 找最大值 和 最小值 来确定 计数数组的大小    int maxVal = array[0];    int minVal = array[0];    for (int i = 1; i < array.length; i++) {        if (array[i] < minVal) {            minVal = array[i];        }        if (array[i] > maxVal) {            maxVal = array[i];        }    }    int len = maxVal - minVal + 1;    int[] count = new int[len];    //2. 遍历原来的数组array把 每个元素 放到对应的计数数组当中 进行计数    for (int i = 0; i < array.length; i++) {        int index = array[i];        count[index - minVal]++;    }    //3.依次 遍历计数数组 O(范围)    int index = 0;    for (int i = 0; i < count.length; i++) {        while (count[i] != 0) {            array[index] = i + minVal;            index++;            count[i]--;        }    }}

排序步骤:

统计频次:创建一个计数数组,用于统计每个整数出现的次数。计算前缀和:计算计数数组的前缀和,前缀和表示每个整数在排序后数组中的起始位置。构建排序数组:根据计数数组构建排序数组,将每个整数放置到其在排序数组中的相应位置。

点击全文阅读


本文链接:http://zhangshiyu.com/post/178809.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1