`
鬼眼小菜刀
  • 浏览: 41042 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
最近访客 更多访客>>
zhanboqi
社区版块
存档分类
最新评论

java排序大全

JavaJ# 
阅读更多

java排序大全

插入排序：

  1. 　　packageorg.rut.util.algorithm.support;
  2. 　　importorg.rut.util.algorithm.SortUtil;
  3. 　　/**
  4. 　　*@authortreeroot
  5. 　　*@since2006-2-2
  6. 　　*@version1.0
  7. 　　*/
  8. 　　publicclassInsertSortimplementsSortUtil.Sort
  9. 　　{
  10. 　　　/*(non-Javadoc)
  11. 　　　*@seeorg.rut.util.algorithm.SortUtil.Sort#sort(int[])
  12. 　　　*/
  13. 　　　publicvoidsort(int[]data)
  14. 　　　{
  15. 　　　　inttemp;
  16. 　　　　for(inti=1;ifor(intj=i;(j>0)&&(data[j]SortUtil.swap(data,j,j-1);
  17. 　　　}
  18. 　　}

　　冒泡排序：

  1. 　　packageorg.rut.util.algorithm.support;
  2. 　　importorg.rut.util.algorithm.SortUtil;
  3. 　　/**
  4. 　　*@authortreeroot
  5. 　　*@since2006-2-2
  6. 　　*@version1.0
  7. 　　*/
  8. 　　publicclassBubbleSortimplementsSortUtil.Sort
  9. 　　{
  10. 　　　/*(non-Javadoc)
  11. 　　　*@seeorg.rut.util.algorithm.SortUtil.Sort#sort(int[])
  12. 　　　*/
  13. 　　　publicvoidsort(int[]data)
  14. 　　　{
  15. 　　　　inttemp;
  16. 　　　　for(inti=0;ifor(intj=data.length-1;j>i;j--)
  17. 　　　　{
  18. 　　　　　if(data[j]SortUtil.swap(data,j,j-1);
  19. 　　　　}
  20. 　　　}
  21. 　　}

　　选择排序：

　　

  1. packageorg.rut.util.algorithm.support;
  2. 　　importorg.rut.util.algorithm.SortUtil;
  3. 　　/**
  4. 　　*@authortreeroot
  5. 　　*@since2006-2-2
  6. 　　*@version1.0
  7. 　　*/
  8. 　　publicclassSelectionSortimplementsSortUtil.Sort
  9. 　　{
  10. 　　　/*
  11. 　　　*(non-Javadoc)
  12. 　　　*
  13. 　　　*@seeorg.rut.util.algorithm.SortUtil.Sort#sort(int[])
  14. 　　　*/
  15. 　　　publicvoidsort(int[]data)
  16. 　　　{
  17. 　　　　inttemp;
  18. 　　　　for(inti=0;i<data.length;i++)
  19. 　　　　{
  20. 　　　　　intlowIndex=i;
  21. 　　　　　for(intj=data.length-1;j>i;j--)
  22. 　　　　　{
  23. 　　　　　　if(data[j]<data[lowIndex])
  24. 　　　　　　{
  25. 　　　　　　　lowIndex=j;
  26. 　　　　　　}
  27. 　　　　　}
  28. 　　　　　SortUtil.swap(data,i,lowIndex);
  29. 　　　　}
  30. 　　　}
  31. 　　}

Shell排序：

　　

  1. packageorg.rut.util.algorithm.support;
  2. 　　importorg.rut.util.algorithm.SortUtil;
  3. 　　/**
  4. 　　*@authortreeroot
  5. 　　*@since2006-2-2
  6. 　　*@version1.0
  7. 　　*/
  8. 　　publicclassShellSortimplementsSortUtil.Sort
  9. 　　{
  10. 　　　/*(non-Javadoc)
  11. 　　　*@seeorg.rut.util.algorithm.SortUtil.Sort#sort(int[])
  12. 　　　*/
  13. 　　　publicvoidsort(int[]data)
  14. 　　　{
  15. 　　　　for(inti=data.length/2;i>2;i/=2)
  16. 　　　　{
  17. 　　　　　for(intj=0;jinsertSort(data,j,i);
  18. 　　　　}
  19. 　　　}
  20. 　　　insertSort(data,0,1);
  21. 　　}
  23. 　　/**
  24. 　　*@paramdata
  25. 　　*@paramj
  26. 　　*@parami
  27. 　　*/
  28. 　　privatevoidinsertSort(int[]data,intstart,intinc)
  29. 　　{
  30. 　　　inttemp;
  31. 　　　for(inti=start+inc;ifor(intj=i;(j>=inc)&&(data[j]SortUtil.swap(data,j,j-inc);
  32. 　　}

　　快速排序：

　

  1. 　packageorg.rut.util.algorithm.support;
  2. 　　importorg.rut.util.algorithm.SortUtil;
  3. 　　/**
  4. 　　*@authortreeroot
  5. 　　*@since2006-2-2
  6. 　　*@version1.0
  7. 　　*/
  8. 　　publicclassQuickSortimplementsSortUtil.Sort
  9. 　　{
  10. 　　　/*(non-Javadoc)
  11. 　　　*@seeorg.rut.util.algorithm.SortUtil.Sort#sort(int[])
  12. 　　　*/
  13. 　　　publicvoidsort(int[]data)
  14. 　　　{
  15. 　　　　quickSort(data,0,data.length-1);
  16. 　　　}
  17. 　　　privatevoidquickSort(int[]data,inti,intj)
  18. 　　　{
  19. 　　　　intpivotIndex=(i+j)/2;
  20. 　　　　//swap
  21. 　　　　SortUtil.swap(data,pivotIndex,j);
  22. 　　　　intk=partition(data,i-1,j,data[j]);
  23. 　　　　SortUtil.swap(data,k,j);
  24. 　　　　if((k-i)>1)quickSort(data,i,k-1);
  25. 　　　　if((j-k)>1)quickSort(data,k+1,j);
  26. 　　　}
  27. 　　　/**
  28. 　　　*@paramdata
  29. 　　　*@parami
  30. 　　　*@paramj
  31. 　　　*@return
  32. 　　　*/
  33. 　　　privateintpartition(int[]data,intl,intr,intpivot)
  34. 　　　{
  35. 　　　　do
  36. 　　　　{
  37. 　　　　　while(data[++l]while((r!=0)&&data[--r]>pivot);
  38. 　　　　　SortUtil.swap(data,l,r);
  39. 　　　　}
  40. 　　　　while(lSortUtil.swap(data,l,r);
  41. 　　　　returnl;
  42. 　　　}
  43. 　　}

　　改进后的快速排序：

　　

  1. packageorg.rut.util.algorithm.support;
  2. 　　importorg.rut.util.algorithm.SortUtil;
  3. 　　/**
  4. 　　*@authortreeroot
  5. 　　*@since2006-2-2
  6. 　　*@version1.0
  7. 　　*/
  8. 　　publicclassImprovedQuickSortimplementsSortUtil.Sort
  9. 　　{
  10. 　　　privatestaticintMAX_STACK_SIZE=4096;
  11. 　　　privatestaticintTHRESHOLD=10;
  12. 　　　/*(non-Javadoc)
  13. 　　　*@seeorg.rut.util.algorithm.SortUtil.Sort#sort(int[])
  14. 　　　*/
  15. 　　　publicvoidsort(int[]data)
  16. 　　　{
  17. 　　　　int[]stack=newint[MAX_STACK_SIZE];
  18. 　　　　inttop=-1;
  19. 　　　　intpivot;
  20. 　　　　intpivotIndex,l,r;
  21. 　　　　stack[++top]=0;
  22. 　　　　stack[++top]=data.length-1;
  23. 　　　　while(top>0)
  24. 　　　　{
  25. 　　　　　intj=stack[top--];
  26. 　　　　　inti=stack[top--];
  27. 　　　　　pivotIndex=(i+j)/2;
  28. 　　　　　pivot=data[pivotIndex];
  29. 　　　　　SortUtil.swap(data,pivotIndex,j);
  30. 　　　　　//partition
  31. 　　　　　l=i-1;
  32. 　　　　　r=j;
  33. 　　　　　do
  34. 　　　　　{
  35. 　　　　　　while(data[++l]while((r!=0)&&(data[--r]>pivot));
  36. 　　　　　　SortUtil.swap(data,l,r);
  37. 　　　　　}
  38. 　　　　　while(lSortUtil.swap(data,l,r);
  39. 　　　　　SortUtil.swap(data,l,j);
  40. 　　　　　if((l-i)>THRESHOLD)
  41. 　　　　　{
  42. 　　　　　　stack[++top]=i;
  43. 　　　　　　stack[++top]=l-1;
  44. 　　　　　}
  45. 　　　　　if((j-l)>THRESHOLD)
  46. 　　　　　{
  47. 　　　　　　stack[++top]=l+1;
  48. 　　　　　　stack[++top]=j;
  49. 　　　　　}
  50. 　　　　}
  51. 　　　　//newInsertSort().sort(data);
  52. 　　　　insertSort(data);
  53. 　　　}
  54. 　　　/**
  55. 　　　*@paramdata
  56. 　　　*/
  57. 　　　privatevoidinsertSort(int[]data)
  58. 　　　{
  59. 　　　　inttemp;
  60. 　　　　for(inti=1;ifor(intj=i;(j>0)&&(data[j]SortUtil.swap(data,j,j-1);
  61. 　　　}
  62. 　　}

归并排序：

　　

  1. packageorg.rut.util.algorithm.support;
  2. 　　importorg.rut.util.algorithm.SortUtil;
  3. 　　/**
  4. 　　*@authortreeroot
  5. 　　*@since2006-2-2
  6. 　　*@version1.0
  7. 　　*/
  8. 　　publicclassMergeSortimplementsSortUtil.Sort
  9. 　　{
  10. 　　　/*(non-Javadoc)
  11. 　　　*@seeorg.rut.util.algorithm.SortUtil.Sort#sort(int[])
  12. 　　　*/
  13. 　　　publicvoidsort(int[]data)
  14. 　　　{
  15. 　　　　int[]temp=newint[data.length];
  16. 　　　　mergeSort(data,temp,0,data.length-1);
  17. 　　　}
  18. 　　　privatevoidmergeSort(int[]data,int[]temp,intl,intr)
  19. 　　　{
  20. 　　　　intmid=(l+r)/2;
  21. 　　　　if(l==r)return;
  22. 　　　　mergeSort(data,temp,l,mid);
  23. 　　　　mergeSort(data,temp,mid+1,r);
  24. 　　　　for(inti=l;i<=r;i++){
  25. 　　　　temp[i]=data[i];
  26. 　　　}
  27. 　　　inti1=l;
  28. 　　　inti2=mid+1;
  29. 　　　for(intcur=l;cur<=r;cur++)
  30. 　　　{
  31. 　　　　if(i1==mid+1)
  32. 　　　　data[cur]=temp[i2++];
  33. 　　　　elseif(i2>r)
  34. 　　　　data[cur]=temp[i1++];
  35. 　　　　elseif(temp[i1]data[cur]=temp[i1++];
  36. 　　　　else
  37. 　　　　data[cur]=temp[i2++];
  38. 　　　}
  39. 　　}
  40. 　

　　改进后的归并排序:

　

  1. 　packageorg.rut.util.algorithm.support;
  2. 　　importorg.rut.util.algorithm.SortUtil;
  3. 　　/**
  4. 　　*@authortreeroot
  5. 　　*@since2006-2-2
  6. 　　*@version1.0
  7. 　　*/
  8. 　　publicclassImprovedMergeSortimplementsSortUtil.Sort
  9. 　　{
  10. 　　　privatestaticfinalintTHRESHOLD=10;
  11. 　　　/*
  12. 　　　*(non-Javadoc)
  13. 　　　*
  14. 　　　*@seeorg.rut.util.algorithm.SortUtil.Sort#sort(int[])
  15. 　　　*/
  16. 　　　publicvoidsort(int[]data)
  17. 　　　{
  18. 　　　　int[]temp=newint[data.length];
  19. 　　　　mergeSort(data,temp,0,data.length-1);
  20. 　　　}
  21. 　　　privatevoidmergeSort(int[]data,int[]temp,intl,intr)
  22. 　　　{
  23. 　　　　inti,j,k;
  24. 　　　　intmid=(l+r)/2;
  25. 　　　　if(l==r)
  26. 　　　　return;
  27. 　　　　if((mid-l)>=THRESHOLD)
  28. 　　　　mergeSort(data,temp,l,mid);
  29. 　　　　else
  30. 　　　　insertSort(data,l,mid-l+1);
  31. 　　　　if((r-mid)>THRESHOLD)
  32. 　　　　mergeSort(data,temp,mid+1,r);
  33. 　　　　else
  34. 　　　　insertSort(data,mid+1,r-mid);
  35. 　　　　for(i=l;i<=mid;i++)
  36. 　　　　{
  37. 　　　　　temp[i]=data[i];
  38. 　　　　}
  39. 　　　　for(j=1;j<=r-mid;j++)
  40. 　　　　{
  41. 　　　　　temp[r-j+1]=data[j+mid];
  42. 　　　　}
  43. 　　　　inta=temp[l];
  44. 　　　　intb=temp[r];
  45. 　　　　for(i=l,j=r,k=l;k<=r;k++)
  46. 　　　　{
  47. 　　　　　if(a<b)
  48. 　　　　　{
  49. 　　　　　　data[k]=temp[i++];
  50. 　　　　　　a=temp[i];
  51. 　　　　　}
  52. 　　　　　else
  53. 　　　　　{
  54. 　　　　　　data[k]=temp[j--];
  55. 　　　　　　b=temp[j];
  56. 　　　　　}
  57. 　　　　}
  58. 　　　}
  60. 　　　/**
  61. 　　　*@paramdata
  62. 　　　*@paraml
  63. 　　　*@parami
  64. 　　　*/
  65. 　　　privatevoidinsertSort(int[]data,intstart,intlen)
  66. 　　　{
  67. 　　　　for(inti=start+1;ifor(intj=i;(j>start)&&data[j]SortUtil.swap(data,j,j-1);
  68. 　　　}
  69. 　　}

堆排序：

  1. 　　packageorg.rut.util.algorithm.support;
  2. 　　importorg.rut.util.algorithm.SortUtil;
  3. 　　/**
  4. 　　*@authortreeroot
  5. 　　*@since2006-2-2
  6. 　　*@version1.0
  7. 　　*/
  8. 　　publicclassHeapSortimplementsSortUtil.Sort
  9. 　　{
  10. 　　　/*(non-Javadoc)
  11. 　　　*@seeorg.rut.util.algorithm.SortUtil.Sort#sort(int[])
  12. 　　　*/
  13. 　　　publicvoidsort(int[]data)
  14. 　　　{
  15. 　　　　MaxHeaph=newMaxHeap();
  16. 　　　　h.init(data);
  17. 　　　　for(inti=0;ih.remove();
  18. 　　　　System.arraycopy(h.queue,1,data,0,data.length);
  19. 　　　}
  20. 　　　privatestaticclassMaxHeap
  21. 　　　{
  22. 　　　　voidinit(int[]data)
  23. 　　　　{
  24. 　　　　　this.queue=newint[data.length+1];
  25. 　　　　　for(inti=0;iqueue[++size]=data[i];
  26. 　　　　　fixUp(size);
  27. 　　　　}
  28. 　　　}
  29. 　　　privateintsize=0;
  30. 　　　privateint[]queue;
  31. 　　　publicintget()
  32. 　　　{
  33. 　　　　returnqueue[1];
  34. 　　　}
  35. 　　　publicvoidremove()
  36. 　　　{
  37. 　　　　SortUtil.swap(queue,1,size--);
  38. 　　　　fixDown(1);
  39. 　　　}
  40. 　　　//fixdown
  41. 　　　privatevoidfixDown(intk)
  42. 　　　{
  43. 　　　　intj;
  44. 　　　　while((j=k<<1)<=size)
  45. 　　　　{
  46. 　　　　　if(j<size&&queue[j]j++;
  47. 　　　　　if(queue[k]>queue[j])//不用交换
  48. 　　　　　break;
  49. 　　　　　SortUtil.swap(queue,j,k);
  50. 　　　　　k=j;
  51. 　　　　}
  52. 　　　}
  53. 　　　privatevoidfixUp(intk)
  54. 　　　{
  55. 　　　　while(k>1)
  56. 　　　　{
  57. 　　　　　intj=k>>1;
  58. 　　　　　if(queue[j]>queue[k])
  59. 　　　　　break;
  60. 　　　　　SortUtil.swap(queue,j,k);
  61. 　　　　　k=j;
  62. 　　　　}
  63. 　　　}
  64. 　　}
  66. 　　SortUtil：
  68. 　　packageorg.rut.util.algorithm;
  69. 　　importorg.rut.util.algorithm.support.BubbleSort;
  70. 　　importorg.rut.util.algorithm.support.HeapSort;
  71. 　　importorg.rut.util.algorithm.support.ImprovedMergeSort;
  72. 　　importorg.rut.util.algorithm.support.ImprovedQuickSort;
  73. 　　importorg.rut.util.algorithm.support.InsertSort;
  74. 　　importorg.rut.util.algorithm.support.MergeSort;
  75. 　　importorg.rut.util.algorithm.support.QuickSort;
  76. 　　importorg.rut.util.algorithm.support.SelectionSort;
  77. 　　importorg.rut.util.algorithm.support.ShellSort;
  79. 　　/**
  80. 　　*@authortreeroot
  81. 　　*@since2006-2-2
  82. 　　*@version1.0
  83. 　　*/
  84. 　　publicclassSortUtil
  85. 　　{
  86. 　　　publicfinalstaticintINSERT=1;
  87. 　　　publicfinalstaticintBUBBLE=2;
  88. 　　　publicfinalstaticintSELECTION=3;
  89. 　　　publicfinalstaticintSHELL=4;
  90. 　　　publicfinalstaticintQUICK=5;
  91. 　　　publicfinalstaticintIMPROVED_QUICK=6;
  92. 　　　publicfinalstaticintMERGE=7;
  93. 　　　publicfinalstaticintIMPROVED_MERGE=8;
  94. 　　　publicfinalstaticintHEAP=9;
  95. 　　　publicstaticvoidsort(int[]data)
  96. 　　　{
  97. 　　　　sort(data,IMPROVED_QUICK);
  98. 　　　}
  99. 　　　privatestaticString[]name=
  100. 　　　{
  101. 　　　　"insert","bubble","selection","shell","quick","improved_quick","merge","improved_merge","heap"
  102. 　　　};
  103. 　　　privatestaticSort[]impl=newSort[]
  104. 　　　{
  105. 　　　　newInsertSort(),
  106. 　　　　newBubbleSort(),
  107. 　　　　newSelectionSort(),
  108. 　　　　newShellSort(),
  109. 　　　　newQuickSort(),
  110. 　　　　newImprovedQuickSort(),
  111. 　　　　newMergeSort(),
  112. 　　　　newImprovedMergeSort(),
  113. 　　　　newHeapSort()
  114. 　　　};
  115. 　　　publicstaticStringtoString(intalgorithm)
  116. 　　　{
  117. 　　　　returnname[algorithm-1];
  118. 　　　}
  119. 　　　publicstaticvoidsort(int[]data,intalgorithm)
  120. 　　　{
  121. 　　　　impl[algorithm-1].sort(data);
  122. 　　　}
  123. 　　　publicstaticinterfaceSort
  124. 　　　{
  125. 　　　　publicvoidsort(int[]data);
  126. 　　　}
  127. 　　　publicstaticvoidswap(int[]data,inti,intj)
  128. 　　　{
  129. 　　　　inttemp=data[i];
  130. 　　　　data[i]=data[j];
  131. 　　　　data[j]=temp;
  132. 　　　}
  133. 　　}
分享到：
| JAVA面试题精选
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

Magicbox
Global site tag (gtag.js) - Google Analytics