Java中的七大排序(上)
发布时间:2020-12-15 07:26:28 所属栏目:Java 来源:网络整理
导读:一般排序通常认为是升序。 稳定性:两个相等的数据若在排序前后的相对位置不发生改变,则称该算法是具备稳定性的算法。 一:插入排序 原理: 将数组分为有序区间和无序区间,每次用无需区间的 第一个数与有序区间进行比较。 时间复杂度:O(n*n),空间复杂度:
一般排序通常认为是升序。
稳定性:两个相等的数据若在排序前后的相对位置不发生改变,则称该算法是具备稳定性的算法。 一:插入排序 原理: 将数组分为有序区间和无序区间,每次用无需区间的 第一个数与有序区间进行比较。 时间复杂度:O(n*n),空间复杂度:O(1) 稳定性:稳定 代码如下: public static void insertSort0(int[] array) { for (int i = 1; i < array.length; i++) { // 有序区间 [0,i) // 无序区间 [i,array.length) int key = array[i]; int j; for (j = i - 1; j >= 0 && array[j] > key; j--) { array[j + 1] = array[j]; } array[j + 1] = key; } } 二:希尔排序 public static void shellSort(int[] array){ int gap=array.length; while(true){ gap=(gap/3)+1;//or gap=gap/2 insertSortWithGap(array,gap); if(gap==1){ break; } } } private static void inserSortWithGap(int[] array,int gap){ for(int i=gap;i<array.length;i++){ int key=array[i]; int j; for(j=i-gap;j>=0&&array[j]>key;j-=gap){ array[j+gap]=array[j]; } array[j+gap]=key; } } 三:选择排序 public static void selsctSort1(int[] array){ //每次选最小的放在无序区间的前面 for(int i=0;i<array.length-1;i++){//需要排序的次数 //有序:[0,i) //无序:[i,array.length) int minIndex=i; for(int j=i+1;j<array.length;j++){ if(array[j]<array[minIndex]){ minIndex=j; } } swap(array,mindex,i); } } public static void selsctSort2(int[] array){ //每次选最大的放在无序区间的后面 for(int i=0;i<=array.length-1;i++){ //无序:[0,array.length-i) //有序:[array.length-i,array.length) int maxIndex=0; for(int j=1;j<array.length-i;j++){ if(array[j]>array[max]){ max=j; } } int t=array[max]; array[max]=array[array.length-i-1]; array[array.length-i-1]=t; } 2.双向排序比较 原理:每一次从无序区间选出最小 + 最大的元素,存放在无序区间的最前和最后,直到全部待排序的数据元素排完 。 时间复杂度:O(n^2),空间复杂度:O(1) 稳定性:不稳定 代码如下: public static void selectSort3(int[] array){ int low=0; int high=array.length-1; //[low,high]表示整个无序区间 while(low<=high){ int min=low; int high=low; for(int i=low+1;i<=max;i++){ if (array[i] < array[min]) { min = i; } if (array[i] > array[max]) { max = i; } swap(array,min,low); if (max == low) { max = min; } swap(array,max,high); } private void swap(int[] array,int i,int j) { int t = array[i]; array[i] = array[j]; array[j] = t; } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |