首页 > 代码库 > 排序算法(一)
排序算法(一)
1.冒泡排序
//基本算法for(i=1;i<list.length;k++){ //perform the kth pass for(j=0;list.length-i;j++){ if(list[j]<list[j+1]){ swap list[j] with list[j]; } }}//改进算法//如果在某次遍历时没有发生交换，那么就不用进行下一次遍历for(i=1;i<list.length;k++){ needNextPass=false; for(j=0;list.length-i;j++){ if(list[j]<list[j+1]){ swap list[j] with list[j]; needNextPass=true;//need next pass } }}
对于改进算法的排序时间，最佳情况：O(n);最坏情况:O(n2)
2.归并排序
算法描述：将数组分为两半，对每部分递归地应用归并排序。在两部分都排好序后，对他们进行归并。
public static void mergeSort(int[] list){ if(list.lenght>1){ mergeSort(list[0~list.length/2]); mergeSort(list[list.length/2+1~list.length-1]); merge list[0~list.length/2] with list[list.length/2+1~list.length-1]; } }
算法实现：
public class MergeSort{ public static void mergeSort(int[] list){ if(list.length>1){ int[] firstHalf=new int[list.length/2]; System.arraycopy(list,0,firstHalf,0,list.length/2); mergeSort(firstHalf); int[] secondHalf=new int[list.length-list.length/2]; System.arraycopy(list,list.length/2,secondHalf,0,secondHalf.length); mergeSort(secondHalf); int[] temp=merge(firstHalf,secondHalf); System.arraycopy(temp,0,list,0,temp.length); } } private static int[] merge(int[] list1,int[] list2){ int[] temp=new int[list1.length+list2.length]; int current1=0,current2=0,current3=0; while(current1<list1.length&¤t2<list2.length){ if(list1[current1]<list2[current2]) temp[current3++]=list1[current1++]; else temp[current3++]=list2[current2++]; } while(current1<list1.length){ temp[current3++]=list1[current1++]; } while(current2<list2.length){ temp[current3++]=list2[current2++]; } return temp; } public static void main(String[] args){ int[] list={2,3,2,5,6,1,-1,3,14,12}; mergeSort(list); for(int e:list) System.out.print(e+" "); }}
归并排序时间O(nlogn)。该算法优于选择排序，插入排序和冒泡排序。java.util.Arrays类中的sort方法是使用归并排序算法的变体实现的。
3.快速排序
算法描述：在数组中选择一个称为主元(pivot)的元素，将数组分为两部分使得第一部分中的所有元素都小于或等于主元，而第二部分都大于或等于主元。依次对两部分递归地应用快速排序算法。
public static void quicksort(int[] list){ if(list.length>1){ select a pivot; patition list into list1 an list2 such that all elements in list1 <= pivot and all elements in list2 > pivot quicksort(list1); quicksort(list2); }}
算法实现：
package Algorithm;public class QuickSort{ public static void quicksort(int[] list){ quicksort(list,0,list.length-1); } public static void quicksort(int[] list,int left,int right){ if(right>left){ int temp=list[left]; int i=left; int j=right; while(i!=j){ //顺序很重要，要先从右边开始找 while(list[j]>=temp && i<j){ j--; } //再找左边的 while(list[i]<=temp && i<j){ i++; } //交换两个数在数组中的位置 if(i<j){ int t=list[i]; list[i]=list[j]; list[j]=t; } } //最终将基准数归位 list[left]=list[i]; list[i]=temp; quicksort(list,left,i-1); quicksort(list,i+1,right); } } public static void main(String[] args) { int[] list={6,5,3,8,4,9,7}; quicksort(list); for(int u:list) System.out.print(u+","); }}
在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实作出来。
排序算法(一)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。