经典排序算法

《经典排序算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、十大排序算法选择排序选择排序的基本思想是对待排序的记录序列进行n-1遍的处理，第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样，经过i遍处理之后，前i个记录的位置已经是正确的了。选择排序是不稳定的。算法复杂度是O(n^2)。classSelectionSorter{privateintmin;publicvoidSort(int[]arr){for(inti=0;i

2、n=j;}intt=arr[min];arr[min]=arr[i];arr[i]=t;}}}冒泡排序冒泡排序方法是最简单的排序方法。这种方法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。显然，处理一遍之后，“最轻”的元素就浮到了最高位置；处理二遍之后，“次轻”的元素就浮到了次高位置。

3、在作第二遍处理时，由于最高位置上的元素已是“最轻”元素，所以不必检查。一般地，第i遍处理时，不必检查第i高位置以上的元素，因为经过前面i-1遍的处理，它们已正确地排好序。冒泡排序是稳定的。算法时间复杂度是O(n^2)classEbullitionSorter{publicvoidSort(int[]arr){inti,j,temp;booldone=false;j=1;while((j

4、[i]>arr[i+1]){done=false;temp=arr[i];arr[i]=arr[i+1];//交换数据arr[i+1]=temp;}}j++;}}}快速排序快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。快速排序是

5、不稳定的。最理想情况算法时间复杂度O(nlog2n)，最坏O(n^2)。classQuickSorter{privatevoidswap(refintl,refintr){inttemp;temp=l;l=r;r=temp;}publicvoidSort(int[]list,intlow,inthigh){intpivot;//存储分支点intl,r;intmid;if(high<=low)return;elseif(high==low+1){if(list[low]>list[high])swap(reflist[low],r

6、eflist[high]);return;}mid=(low+high)>>1;pivot=list[mid];swap(reflist[low],reflist[mid]);l=low+1;r=high;do{while(l<=r&&list[l]=pivot)r--;if(l

7、1);if(r+1

8、为止。图1演示了对4个元素进行插入排序的过程，共需要(a),(b),(c)三次插入。直接插入排序是稳定的。算法时间复杂度是O(n^2)。publicclassInsertionSorter{publicvoidSort(int[]arr){for(inti=1;