免费下载ppt模板网站推荐,制作网页软件列表html代码,百度帐号登录个人中心,archlinux wordpress数据结构中的八大排序算法是计算机科学领域经典的排序方法#xff0c;它们各自具有不同的特点和适用场景。以下是这八大排序算法的详细介绍#xff1a;
一、插入排序#xff08;Insertion Sort#xff09;
核心思想#xff1a;将数组中的所有元素依次跟前面已经排好的元… 数据结构中的八大排序算法是计算机科学领域经典的排序方法它们各自具有不同的特点和适用场景。以下是这八大排序算法的详细介绍
一、插入排序Insertion Sort
核心思想将数组中的所有元素依次跟前面已经排好的元素相比较如果选择的元素比已排序的元素小则交换再和前一个比较直到全部元素都比较过。时间复杂度O(n^2)其中n是待排序元素的个数。在元素接近有序时时间复杂度可以降低到O(n)。空间复杂度O(1)因为排序过程中只需要常量的额外空间。稳定性稳定即相同元素在排序后的相对位置不变。
package 排序;import java.util.Arrays;public class Insert{//插入排序public static void main(String[] args) {int[] arr {5,7,4,2,0,3,1,6};sort(arr);System.out.println(Arrays.toString(arr));}public static void sort(int[] arr) {for(int i1;iarr.length;i) {for(int ji-1;j0;j--) {if(arr[j]arr[j1]) {int temp arr[j];arr[j]arr[j1];arr[j1]temp;}else {break;}}}}
}
二、希尔排序Shell Sort
核心思想希尔排序是插入排序的一种优化版本也称为缩小增量排序。它先将数组分成若干子数组每个子数组进行插入排序然后逐渐缩小子数组的大小直到整个数组有序。时间复杂度不固定但通常在O(n2)之间取决于gap的取值方法。空间复杂度O(1)。稳定性不稳定因为相同元素可能在不同的子数组中进行排序导致相对位置改变。
package 排序;import java.util.Arrays;public class Shell{//希尔排序缩小增量public static void main(String[] args) {int[] arr {5,7,4,2,0,3,1,6};sort(arr);System.out.println(Arrays.toString(arr));}public static void sort(int[] arr) {for(int greparr.length/2;grep0;grepgrep/2) { for(int igrep;iarr.length;i) {for(int ji-grep;j0;jj-grep) {if(arr[j]arr[jgrep]) {int temp arr[j];arr[j]arr[jgrep];arr[jgrep]temp;}else {break;}}}}}
} 三、冒泡排序Bubble Sort
核心思想相邻两个元素进行比较如果前一个比后一个大则交换它们的位置。这样每一轮循环都会将一个最大的元素“冒泡”到数组的末尾。时间复杂度O(n^2)因为每一轮都需要遍历整个数组。空间复杂度O(1)。稳定性稳定因为相同元素不会进行交换。
package 排序;import java.util.Arrays;public class Bubble{//冒泡public static void main(String[] args) {int[] arr {5,6,71,25,31,42,36,9,4};sort(arr);System.out.println(Arrays.toString(arr));}public static void sort(int[] arr) {for(int j0;jarr.length;j) {for(int i0;iarr.length-1;i) {if(arr[i]arr[i1]) {int temp arr[i];arr[i]arr[i1];arr[i1]temp;}}}}
}四、快速排序Quick Sort
核心思想选择一个元素作为基准pivot将数组分成两部分一部分小于基准一部分大于基准。然后递归地对这两部分进行排序。时间复杂度平均情况下为O(nlogn)但在最坏情况下如数组已经有序会蜕化为冒泡排序时间复杂度为O(n^2)。不过通过随机选择基准或三数取中法等方法可以降低最坏情况的发生概率。空间复杂度O(logn)递归调用栈空间但在最坏情况下会达到O(n)当数组极度不平衡时。稳定性不稳定因为相同元素可能在不同的分区过程中被交换。
package 排序;import java.util.Arrays;public class Quick{//快速排序public static void main(String[] args) {int[] arr {5,6,71,25,36,9,4};int left0;int rightarr.length-1;sort(arr,left,right);System.out.println(Arrays.toString(arr));}private static void sort(int[] arr,int left,int right) {if(leftright) {return;}int basearr[left];int ileft;int jright;while(i!j) {while(arr[j]baseij) {j--;}//i游标从前往后走找比基准数大的while(arr[i]baseij) {i;}//i和j进行交换int temparr[i];arr[i]arr[j];arr[j]temp;}//i和j相遇 基准数和相遇位置进行交换arr[left]arr[i];arr[i]base;//排序左边sort(arr,left,i-1);//排序右边sort(arr,i1,right);}}
