看到这句话的时候证明:此刻你我都在努力
加油陌生人
个人主页: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]--; } }}
排序步骤:
统计频次:创建一个计数数组,用于统计每个整数出现的次数。计算前缀和:计算计数数组的前缀和,前缀和表示每个整数在排序后数组中的起始位置。构建排序数组:根据计数数组构建排序数组,将每个整数放置到其在排序数组中的相应位置。