数据结构与算法——排序算法
1.排序算法的分类 2.冒泡排序算法 、、、 3.选择排序算法 、、、 for(int i=1; i<a.length; i++){ index = i; for(int j=i+1; j<a.length;j++){ if(a[j] < a[j+1]){ index = j; } } if(index != i){ //比较相邻数据大小 temp = a[j]; a[j] = a[index]; a[index] = temp; } System.out.print("每步排序结果:"); for(int k=0; k<a.lenhth; k++){ System.out.print(a[k]+" "); } } } 4.插入排序算法 、、、 for(i=1; i<a.length; i++){ t=a[i]; j=i-1; while(j >= 0 && t<a[j]){ a[j+1] = a[j]; j--; } a[j+1]=t; System.out.print("每步排序结果:"); for(int k=0; k<a.lenhth; k++){ System.out.print(a[k]+" "); } } } 5.Shell排序算法 、、、 for(r=a.length/2; r>=1;r/=2){ for(i=r; i<a.length; i++){ temp=a[i]; j=i-r; while(j >= 0 && temp<a[j]){ a[j+r]=a[j]; j-=r; } a[j+r]=temp; } x++; System.out.print("第" +x+"步排序结果:"); for(int k=0; k<a.lenhth; k++){ System.out.print(a[k]+" "); } } } 6.快速排序算法 、、、 ltemp=left; rtemp=right; f=arr[(left+right)/2]; while(ltemp<rtemp){ while(arr[ltemp]<f){ ++itemp; } while(arr[rtemp]>f){ --rtemp; } if(ltemp<=rtemp){ t=arr[ltemp]; arr[ltemp]=arr[rtemp]; arr[rtemp]=t; --rtemp; ++ltemp; } } if(ltemp==rtemp){ ltemp++; } if(left<rtemp){ quickSort(arr,left,ltemp-1); } if(ltemp<right){ quickSort(arr,rtemp+1,right); } } 7.堆排序算法 (1)流程(要求:从小到大输出) 、、、 for(i=n/2-1; i>=0; i--){ while(2*i+1<n){ j=2*i+1; if(j+1<n ){ if(a[j])<a[j+1]{ j++; } } if(a[i]<a[j]){ t=a[i]; a[i]=a[j]; a[j]=t; i=j; }else{ break; } } } //输出构成的堆 System.out.print("原数据构成的堆:"); for(h=0; h<n; h++){ System.out.print(a[h]+" "); } System.out.print("n "); for(i=n-1; i>0; i--){ t=a[0]; a[0]=a[i]; a[i]=t; k=0; while(2*k+1<i){ j=2*k+1; if(j+1<i){ if(a[j]<a[j+1]){ j++; } } if(a[k]<a[j]){ t=a[k]; a[k]=a[j]; a[j]=t; k=j; }else{ break; } } System.out.print("第"+(n-i)+"步排序结果:"); for(h=0; h<n; h++){ System.out.print(a[h]+" "); } System.out.print("n "); } } 8.合并排序算法 、、、 void mergeSort(int a[],int n ){ 9.排序算法的效率 数据量大小 n,各种排序算法的计算复杂度: (1)冒泡排序:平均速度O(n^2),最坏情况下速度O(n^2); (2)快速排序:平均速度O(nlogn),最坏情况下速度O(n^2); (3)选择排序:平均速度O(n^2),最坏情况下速度O(n^2); (4)堆排序:平均速度O(nlogn),最坏情况下速度O(nlogn); (5)插入排序:平均速度O(n^2),最坏情况下速度O(n^2); (6)Shell排序:平均速度O(n^(3/2)),最坏情况下速度O(n^2); (7)合并排序:平均速度O(nlogn),最坏情况下速度O(nlogn). 其它概念: 稳定排序算法:依照相等的关键字维持记录的相对次序来进行排序。通俗地讲,对于两个有相等关键字的数据D1和D2,在待排序的数据中D1出现在D2之前,在排序过后的数据中D1也在D2之前,称为稳定排序算法。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |