首页 > 编程语言 > 详细

Java排序算法【总结】

时间：2014-10-30 12:31:32      阅读：258      评论：0      收藏：0      [点我收藏+]

1、冒泡排序

冒泡排序是排序算法中最基本的一种排序方法，该方法逐次比较两个相邻数据的大小并交换位置来完成对数据排序，每次比较的结果都找出了这次比较中数据的最大项，因为是逐次比较，所以效率是O（N^2）的。

[java]?view plaincopy
?
  1. public?void?bubbleSort()?{??
  2. ????????int?out,in;??
  3. ????????for(out=index-1;?out>1;?--out)?{??
  4. ????????????for(in=0;?in<out;?++in)?{??
  5. ????????????????if(array[in]>array[in+1])?{??
  6. ????????????????????swap(in,?in+1);??
  7. ????????????????}??
  8. ????????????}??
  9. ????????}??
  10. ????}??
  11. ??????
  12. ????public?void?swap(int?dex1,?int?dex2)?{??
  13. ????????int?temp?=?array[dex1];??
  14. ????????array[dex1]?=?array[dex2];??
  15. ????????array[dex2]?=?temp;??
  16. ????}??

2、选择排序

?

选择排序对冒泡排序进行了优化，在每次遍历比较的过程中不进行交换，而是记录本次遍历的最小值，在遍历结束后再将最小值移到这次遍历的开始位置。这样虽然比较次数没有改变，但交换的次数大大减少，一共只需要N次交换。因为比较的次数没变，所以效率任然是O（N^2）的。

[java]?view plaincopy
?
  1. public?void?selectionSort()?{??
  2. ????????int?out,?in;??
  3. ????????for(out=0;?out<index-1;?++out)?{??
  4. ????????????int?temp?=?out;??
  5. ????????????for(in=out+1;?in<index;?++in)?{??
  6. ????????????????if(array[in]?<?array[temp])?{??
  7. ????????????????????temp?=?in;??
  8. ????????????????}??
  9. ????????????}??
  10. ????????????swap(out,?temp);??
  11. ????????}??
  12. ????}??

?

3、插入排序

?

插入排序充分利用已排列好的数据，然后将未排序的数据插入到已排数据的队伍当中，这样每插入一个未排序数据已排队伍都将增加一个成员，最终达到排序的目的。

?

[java]?view plaincopy
?
  1. public?void?insertionSort()?{??
  2. ????????int?out?,in;??
  3. ????????for(out=1;?out<index;?++out)?{??
  4. ????????????int?temp?=?array[out];??
  5. ????????????in?=?out;??
  6. ????????????while(in>0?&&?temp<array[in-1])?{??
  7. ????????????????array[in]?=?array[in-1];??
  8. ????????????????--in;??
  9. ????????????}??
  10. ????????????array[in]?=?temp;??
  11. ????????}??
  12. ????}??

?

4、归并排序

归并排序是将两个有序数组合并为一个有序数组的排序，应用在一般排序上要结合二分法递归地将数组依次归并，最终得到一个大的有序数组。归并的效率是O（NlogN）的，但要额外开辟一个数组来存放临时数据，所以占用空间要大一倍。

?

[java]?view plaincopy
?
  1. public?void?mergeSort()?{??
  2. ????????int[]?newArray?=?new?int[index];??
  3. ????????recMergeSort(newArray,?0,?index-1);??
  4. ??????????
  5. ????}??
  6. ??????
  7. ????private?void?recMergeSort(int[]?data,?int?low,?int?upper)?{??
  8. ????????if(low?==?upper)?{??
  9. ????????????return;??
  10. ????????}??
  11. ????????int?mid?=?(low?+?upper)/2;??
  12. ????????recMergeSort(data,?mid+1,?upper);??
  13. ????????recMergeSort(data,?low,?mid);??
  14. ????????merge(data,?low,?mid+1,?upper);??
  15. ????}??
  16. ??????
  17. ????private?void?merge(int[]?data,?int?lowStart,?int?highStart,?int?upperBound)?{??
  18. ????????int?j?=?0;??
  19. ????????int?lowBound?=?lowStart;??
  20. ????????int?mid?=?highStart?-?1;??
  21. ????????int?num?=?upperBound?-?lowStart?+?1;??
  22. ??????????
  23. ????????while(lowStart<=mid?&&?highStart<=upperBound)?{??
  24. ????????????if(array[lowStart]?<?array[highStart])?{??
  25. ????????????????data[j++]?=?array[lowStart++];??
  26. ????????????}?else?{??
  27. ????????????????data[j++]?=?array[highStart++];??
  28. ????????????}??
  29. ????????}??
  30. ??????????
  31. ????????while(lowStart<=mid)?{??
  32. ????????????data[j++]?=?array[lowStart++];??
  33. ????????}??
  34. ??????????
  35. ????????while(highStart<=upperBound)?{??
  36. ????????????data[j++]?=?array[highStart++];??
  37. ????????}??
  38. ??????????
  39. ????????for(j=0;?j<num;?j++)?{??
  40. ????????????array[lowBound+j]?=?data[j];??
  41. ????????}??
  42. ????}??

?

5、希尔排序

希尔排序是一种高级排序，它是由插入排序进化来的，插入排序是将未排的数据依次与前面已排好的数据进行比较移动，这样如果一个较小的数排在靠后的位置，那么要找到这个数的正确位置就要进行较多次移动。希尔排序改进了这种方式，它将每次比较的间隔扩大，排过一次之后数据就分阶段有序了，之后逐渐缩小这个间隔再进行排序。这样做的目的就是让数据一开始可以在一个较大的范围内进行移动，待基本有序后数据的移动量就小了很多。

[java]?view plaincopy
?
  1. public?void?shellSort()?{??
  2. ????????int?in,?out;??
  3. ????????int?h?=?1;??
  4. ????????int?temp;??
  5. ????????while(h?<?index/3)?{??
  6. ????????????h?=?h*3+1;??
  7. ????????}??
  8. ????????while(h>0)?{??
  9. ????????????for(out=h;?out<index;?++out)?{??
  10. ????????????????temp?=?array[out];??
  11. ????????????????in?=?out;??
  12. ????????????????while(in>h-1?&&?array[in-h]?>?temp)?{??
  13. ????????????????????array[in]?=?array[in-h];??
  14. ????????????????????in?-=h;??
  15. ????????????????}??
  16. ????????????????array[in]?=?temp;??
  17. ????????????}??
  18. ????????????h?=?(h-1)/3;??
  19. ????????}??
  20. ????}??


?

希尔排序中关键是对数据间隔h的选择，一个间隔序列是由Knuth提出的，即h=h*3+1，h的初始值为1，这是希尔排序中最优的间隔序列。

6、快速排序

快速排序是一种广泛使用的排序方法，效率可以达到O（NlogN），快速排序的原理是确定一个中间值pivot，将所有小于pivot的数据放在左侧，大于pivot的值放在右侧，之后再对左右两侧分别采取这种策略进行排序，直到这个过程结束。

[java]?view plaincopy
?
  1. private?int?partition(int?left,?int?right,?int?pivot)?{??
  2. ????????int?leftPtr?=?left;??
  3. ????????int?rightPtr?=?right-1;??
  4. ????????while(true)?{??
  5. ????????????while(array[++leftPtr]?<?pivot)?;??
  6. ????????????while(array[--rightPtr]?>?pivot);??
  7. ????????????if(leftPtr?>=?rightPtr)?{??
  8. ????????????????break;??
  9. ????????????}?else?{??
  10. ????????????????swap(leftPtr,?rightPtr);??
  11. ????????????}??
  12. ????????}??
  13. ????????swap(leftPtr,?right-1);??
  14. ????????return?leftPtr;??
  15. ????}??
  16. ??????
  17. ????private?int?median(int?left,?int?right)?{??
  18. ????????int?center?=?(left+right)/2;??
  19. ????????if(array[left]>array[center])?{??
  20. ????????????swap(left,?center);??
  21. ????????}??
  22. ????????if(array[left]>array[right])?{??
  23. ????????????swap(left,?right);??
  24. ????????}??
  25. ????????if(array[center]>array[right])?{??
  26. ????????????swap(center,?right);??
  27. ????????}??
  28. ????????swap(center,?right-1);??
  29. ????????return?array[right-1];??
  30. ????}??
  31. ??????
  32. ????private?void?manulSort(int?left,?int?right)?{??
  33. ????????int?size?=?right-left+1;??
  34. ????????if(size?<=?1)?return;??
  35. ????????if(size?==?2)?{??
  36. ????????????if(array[left]>array[right])?swap(left,?right);??
  37. ????????}?else?{??
  38. ????????????if(array[left]>array[right-1])?swap(left,?right-1);??
  39. ????????????if(array[left]>array[right])?swap(left,?right);??
  40. ????????????if(array[right-1]>array[right])?swap(right-1,?right);??
  41. ????????}??
  42. ????}??
  43. ??????
  44. ????private?void?recQuickSort(int?left,?int?right)?{??
  45. ????????int?size?=?right-left+1;??
  46. ????????if(size<=3)?{??
  47. ????????????manulSort(left,?right);??
  48. ????????}?else?{??
  49. ????????????int?pivot?=?median(left,?right);??
  50. ????????????int?partition?=?partition(left,?right,?pivot);??
  51. ????????????recQuickSort(left,?partition-1);??
  52. ????????????recQuickSort(partition+1,?right);??
  53. ????????}??
  54. ??????????
  55. ????}??
  56. ??????
  57. ????public?void?quickSort()?{??
  58. ????????recQuickSort(0,?index-1);??
  59. ????}??

快速排序的关键是确定中间值pivot，如果中间值选取的不好，会使快速排序的效率降到O（N^2）。上面的例子采用了三选一的策略来确定中间值，即在要排序的数据中选择左端、中间和右端三个数据后比较取中间值；还有在数据量较小时，比如小于三个则直接手动排序。

?

Java排序算法【总结】

原文：http://zhu-zhiguo.iteye.com/blog/2148134
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！