建设网站的服务宗旨,霸气业务网站源码,wordpress音乐插件百度云,dede淘宝客网站文章目录 [1]. 堆排序[2]. 冒泡排序[3]. 选择排序[4]. #xff08;直接#xff09;插入排序[5]. 希尔排序#xff08;属于插入算法#xff09;[6]. 快速排序[7]. 归并排序[8]. 基数排序 王道数据结构排序讲解 排序算法最佳时间复杂度最坏时间复杂度平均时间复杂度空间复杂度… 文章目录 [1]. 堆排序[2]. 冒泡排序[3]. 选择排序[4]. 直接插入排序[5]. 希尔排序属于插入算法[6]. 快速排序[7]. 归并排序[8]. 基数排序 王道数据结构排序讲解 排序算法最佳时间复杂度最坏时间复杂度平均时间复杂度空间复杂度适用性稳定性堆排序O(nlogn)O(nlogn)O(nlogn)O(1)适用于大数据量不稳定冒泡排序O(n)O(n^2)O(n^2)O(1)适用于小数据量或基本有序稳定选择排序O(n^2)O(n^2)O(n^2)O(1)适用于小数据量不稳定插入排序O(n)O(n^2)O(n^2)O(1)适用于小数据量或基本有序稳定希尔排序O(nlogn)O(n^2)取决于步长序列O(1)适用于中等规模数据不稳定快速排序O(nlogn)O(n^2)O(nlogn)O(logn)适用于大数据量不稳定归并排序O(nlogn)O(nlogn)O(nlogn)O(n)适用于大数据量稳定基数排序O(n*k)O(n*k)O(n*k)O(nk)适用于非负整数稳定
“最佳时间复杂度”指的是在最理想的情况下而“最坏时间复杂度”则是在最差的情况下。对于每种排序算法空间复杂度表示额外的存储空间需求。适用性方面可以根据数据量的大小和特定的需求来选择合适的排序算法。稳定性指的是相等元素的相对顺序是否在排序后保持不变。
[1]. 堆排序 堆排序是一种高效的选择排序算法。它通过构建一个二叉堆大顶堆或小顶堆并反复从堆顶取出最大或最小元素然后调整堆使其保持性质从而实现排序。具体来说堆排序首先将待排序的元素构建成一个堆然后将堆顶元素与最后一个元素交换位置并将堆的大小减一。接着对根节点进行堆化操作使得剩余元素重新构成一个堆。重复以上步骤直到堆为空最后得到排序完毕的数组。 * 使用Java编写对一组乱序数组进行 堆排序升序使用大根堆*/public class HeapSort {// 堆排序函数public void heapSort(int[] arr) {int n arr.length;// 构建堆for (int i n / 2 - 1; i 0; i--) { //因为从下标 0 到n/2 -1的结点都为分叉结点heapify(arr, n, i);}// 逐步将堆顶元素与最后一个元素交换并重新调整堆for (int i n - 1; i 0; i--) {int temp arr[0];arr[0] arr[i];arr[i] temp;heapify(arr, i, 0);//因为最上面的根元素被弹出堆换成了原堆中的最后那个元素所以重新从最上面开始调整堆结点的个数-1i}}// 调整堆函数public void heapify(int[] arr, int n, int i) {int largest i; // 初始化最大元素为根节点int left 2 * i 1; // 左子节点int right 2 * i 2; // 右子节点// 如果左子节点大于根节点则更新最大元素的索引if (left n arr[left] arr[largest]) {largest left;}// 如果右子节点大于根节点则更新最大元素的索引if (right n arr[right] arr[largest]) {largest right;}// 如果最大元素不是根节点则将最大元素与根节点交换并继续调整堆if (largest ! i) {int swap arr[i];arr[i] arr[largest];arr[largest] swap;heapify(arr, n, largest);//继续递归调整被交换过的子树}}// 测试函数public static void main(String[] args) {int[] arr {4, 10, 3, 5, 1};HeapSort heapSort new HeapSort();System.out.println(排序前);for (int i : arr) {System.out.print(i );}heapSort.heapSort(arr);System.out.println(\n排序后);for (int i : arr) {System.out.print(i );}}
}/** 输出结果:* 排序前* 4 10 3 5 1 * 排序后* 1 3 4 5 10*/[2]. 冒泡排序 冒泡排序是一种简单但效率较低的排序算法。它通过不断地比较相邻的元素并将较大或较小的元素逐渐移动到数组的一端从而实现排序。具体来说它会多次遍历数组每次遍历时比较相邻元素并交换位置直到整个数组排序完毕。因为较大或较小的元素像气泡一样逐渐浮出所以称之为冒泡排序。 //冒泡排序
public class BubbleSort {public static void main(String[] args) {int[] ints new int[]{23,24,54,-324,2,1,1,1,98};bubbleSort(ints);for (int anInt : ints) {System.out.print(anInt );}}public static void bubbleSort(int[] arr) {for (int i 0; i arr.length; i) {boolean flag true;for (int j 0; j arr.length - 1 - i; j) {if (arr[j] arr[j 1]) {flag false;int temp arr[j];arr[j] arr[j 1];arr[j 1] temp;}}//优化如果发现某一层完全没有交换次序即flag没有变为false则该序列已经为有序排列结束循环if (flag) {break;}}}
}[3]. 选择排序 选择排序也是一种简单但效率较低的排序算法。它通过每次选择未排序部分的最小或最大元素然后将其与未排序部分的第一个元素进行交换从而逐渐将最小或最大元素放到已排序部分的末尾。具体来说选择排序会遍历数组每次遍历时找到未排序部分的最小或最大元素并交换位置直到整个数组排序完毕。 //选择排序
public class SelectSort {public static void main(String[] args) {int[] ints new int[]{23,24,54,-324,2,1,1,1,98};selectSort(ints);for (int anInt : ints) {System.out.print(anInt );}}//min 最小值//mindex 最小值的下标public static void selectSort(int[] arr) {for (int i 0; i arr.length; i) {int min arr[i];int minindex i;for (int j i 1; j arr.length; j) {if (min arr[j]) {min arr[j];minindex j;}}//该排序没有分配多余的数组空间经过一轮比较后mindex是最终最小值min的下标//如果mindex变化因为没有申请额外空间存储所以这里交换arr[i]和arr[mindex]的位置if (i ! minindex) {arr[minindex] arr[i];arr[i] min;}}}
}[4]. 直接插入排序 插入排序是一种简单但高效的排序算法。它将数组分为已排序部分和未排序部分然后逐个将未排序部分的元素插入到已排序部分的正确位置从而实现排序。具体来说插入排序从第二个元素开始将其与前面的元素比较并插入正确的位置然后继续对后面的元素进行插入操作直到整个数组排序完毕。 //插入排序
public class InsertSort {public static void main(String[] args) {int[] ints new int[]{23,24,54,-324,2,1,1,1,98};insertSort(ints);for (int anInt : ints) {System.out.print(anInt );}}//insertIndex: 待插入元素的下标//insertValue: 带插入元素的值//排序思想从数组第二个元素开始遍历该排序就是要将此时遍历到的元素插入前面的序列中保证前面的序列从小到大public static void insertSort(int[] arr) {for (int i 1; i arr.length; i) {int insertIndex i;int insertValue arr[i];//while循环的目的将arr[i]与前面的元素比较找到第一个比它大的元素然后插到该元素前面while (insertIndex 0 insertValue arr[insertIndex - 1]) {arr[insertIndex] arr[insertIndex - 1];insertIndex--;}arr[insertIndex] insertValue;}}
}[5]. 希尔排序属于插入算法 希尔排序是一种高效的排序算法它通过将待排序的元素划分为若干组来进行排序然后逐步减小组的大小最终完成排序。 具体步骤如下 首先选择一个增量序列通常为数组长度的一半并将数组分为若干组。对每一组进行插入排序即从第二个元素开始逐个与前面的元素比较并插入正确的位置。逐步缩小增量序列重新分组并进行插入排序直到增量序列为1。最后进行一次增量为1的插入排序完成排序。 希尔排序与插入排序的关系和区别如下 希尔排序是插入排序的改进版本通过分组的方式使得插入排序可以先比较距离较远的元素从而更高效地移动元素。相比于插入排序希尔排序的时间复杂度更优可以达到O(n log n)级别尤其在大规模数据的排序中表现良好。希尔排序是不稳定的排序算法即同值的元素在排序后可能会改变相对顺序。相比于其他高效的排序算法希尔排序的实现较为简单且对于中小规模的数据集也有较好的性能表现。 //希尔排序
public class ShellSort {public static void main(String[] args) {int[] ints new int[]{23,24,54,-324,2,1,1,1,98};shellSort(ints);for (int anInt : ints) {System.out.print(anInt );}}public static void shellSort(int[] arr) {//gap步长for (int gap arr.length / 2; gap 0; gap / 2) {for (int i gap; i arr.length; i) {//插入式 间隔为gap的插入排序int insertIndex i;int insertValue arr[i];while (insertIndex - gap 0 insertValue arr[insertIndex - gap]) {arr[insertIndex] arr[insertIndex - gap];insertIndex - gap;}arr[insertIndex] insertValue;}}}
}[6]. 快速排序 快速排序是一种高效的分治排序算法。它选择一个基准元素将数组分为两个子数组一个子数组中的元素都小于基准元素另一个子数组中的元素都大于基准元素然后递归地对子数组进行排序最后通过合并子数组得到排序完毕的数组。具体来说快速排序选择一个基准元素通过比较将其他元素分别放到基准元素的左边或右边然后对左右子数组递归地进行快速排序最后合并子数组得到排序完毕的数组。 import java.util.Arrays;public class QuickSort {public static void main(String[] args) {int[] ints new int[]{23, -9, 78, 3, 34,3, 0, 34,23};quickSort(ints, 0, ints.length - 1);System.out.println(Arrays.toString(ints));}public static void quickSort(int[] arr, int left, int right) {if (left right) {//递归调用函数结束return;}int l left;int r right;while (l r) {//每次都以arr[left]为标准进行对比while (l r arr[r] arr[left]) r--;while (l r arr[l] arr[left]) l;//两次循环后最终是lr 此时arr[r]一定小于等于arr[left]if (r l) {//此时该循环就结束了int temp arr[r];arr[r] arr[left];arr[left] temp;} else {int temp arr[r];arr[r] arr[l];arr[l] temp;}}//此时r l 索引r左边的元素小于arr[r] 索引r右边的元素大于arr[r];//在分别对左右部分进行快排quickSort(arr, left, l - 1);quickSort(arr, r 1, right);}}[7]. 归并排序 归并排序是一种高效的分治排序算法。它的思想是将数组不断地二分分解直到每个子数组只有一个元素然后将相邻的子数组进行合并直到最终得到排序完毕的数组。具体来说归并排序会递归地将数组二分然后对每个子数组进行归并操作通过比较两个子数组的元素按顺序合并成一个有序的子数组最后不断合并子数组直到整个数组排序完毕。 import java.util.Arrays;public class MergeSort {public static void main(String[] args) {int[] ints new int[]{23, -9, 78, 3, 34,3, 0, 34,23};//临时存储合并之后的数组int[] temp new int[ints.length];mergeSort(ints, 0, ints.length - 1, temp);System.out.println(Arrays.toString(ints));}public static void mergeSort(int[] arr, int left, int right, int[] temp) {//递归的结束条件 如果leftright,说明可以继续分则继续可以调用该函数否则就不能分就直接returnif (left right) {//mid被分的两个部分的中间索引 用于之后合并两个部分时用int mid (left right) / 2;//将左边部分继续分mergeSort(arr, 0, mid, temp);//将右边部分继续分mergeSort(arr, mid 1, right, temp);//代码运行到这里递归已经调用完毕开始回溯从最开始的左右部分各一个元素开始回溯merge(arr, left, mid, right, temp);}}public static void merge(int[] arr, int left, int mid, int right, int[] temp) {int i left; //左边部分的最左侧索引int j mid 1; //右边部分的最左侧索引当只有每个部分只有一个元素时此时midleft mid1rightint t 0;//临时数组temp的索引从0开始//将分开的两部分合并while (i mid j right) {if (arr[i] arr[j]) {temp[t] arr[i];t;i;} else {temp[t] arr[j];t;j;}}//如果左边部分有没有合并进去的接着i继续合并while (i mid) {temp[t] arr[i];t;i;}//如果右边部分有没有合并进去的接着j继续合并while (j right) {temp[t] arr[j];t;j;}//将临时数组temp的所存储的值赋值给原数组arrt 0;//原数组的索引需要从left开始right结束int tempLeft left;while (tempLeft right) {arr[tempLeft] temp[t];t;tempLeft;}}}[8]. 基数排序 基数排序是一种非比较的排序算法适用于有非负整数的数组。它按照个位、十位、百位等位数的大小进行排序通过多次遍历数组根据每个位数的值将数组元素进行分配和收集最终得到排序完毕的数组。具体来说基数排序首先选取一个最高位数将数组按照该位数进行排序然后再对下一位数进行排序直到最低位数排序完成。基数排序利用了稳定排序的特性在位数排序时保持相同位数值的元素相对顺序不变。 import java.util.Arrays;public class RedixSort {public static void main(String[] args) {int[] ints new int[]{24,74, 3, 34,14, 4, 34,3434,24,3435,324,544,234,124};//临时存储合并之后的数组redixSort(ints);System.out.println(Arrays.toString(ints));}public static void redixSort(int[] arr) {int[][] bucket new int[10][arr.length];int[] bucketElementCounts new int[10];//求出数组中高度最大值的位数最大值拥有最大位数int max arr[0];for (int i 1; i arr.length; i) {if (max arr[i]) max arr[i];}int maxCount (max ).length(); //小技巧将数转换成字符串其长度即是其位数for (int i 0; i maxCount; i) {//将arr数组中的每个数存在bucket二维数组中 一维数组bucketElementCount用于记录每个桶所存的数的个数for (int k 0; k arr.length; k) {int value arr[k] / (int)Math.pow(10, i) % 10;bucket[value][bucketElementCounts[value]] arr[k];bucketElementCounts[value];}int index 0;//多次循环后最终将bucket中最后存的所有数按顺序赋值给arrfor (int k 0; k bucketElementCounts.length; k) {if (bucketElementCounts[k] ! 0) {for (int x 0; x bucketElementCounts[k]; x) {arr[index] bucket[k][x];index;}}//对k进行清0用于下一循环bucketElementCounts[k] 0;}}}
}
