1.定义 通过比较来确定输入序列<a1,a2,..,an>的元素间相对次序的排序算法称为比较排序算法。
2.算法解释 (1) 选择排序: 选择排序的基本思想是对待排序的记录序列进行n-1遍的处理,第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样,经过i遍处理之后,前i个记录的位置已经是正确的了。 (2): 冒泡排序 最简单的排序方法是冒泡排序方法。这种方法的基本思想是,将待排序的元素看作是竖着排列的“气泡”,较小的元素比较轻,从而要往上浮。在冒泡排序算法中我 们要对这个“气泡”序列处理若干遍。所谓一遍处理,就是自底向上检查一遍这个序列,并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序 不对,即“轻”的元素在下面,就交换它们的位置。显然,处理一遍之后,“最轻”的元素就浮到了最高位置;处理二遍之后,“次轻”的元素就浮到了次高位置。 在作第二遍处理时,由于最高位置上的元素已是“最轻”元素,所以不必检查。一般地,第i遍处理时,不必检查第i高位置以上的元素,因为经过前面i-1遍的 处理,它们已正确地排好序 (3) 插入排序 插入排序的基本思想是,经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置,使得L[1..i]又是排好序的序列。要达到这个目的,我们可以用顺序比较的方法。首先比较L[i]和L[i-1],如果L[i-1]≤ L[i],则L[1..i]已排好序,第i遍处理就结束了;否则交换L[i]与L[i-1]的位置,继续比较L[i-1]和L[i-2],直到找到某一个位置j(1≤j≤i-1),使得L[j] ≤L[j+1]时为止 (4) 快速排序
快速排序的基本思想是基于分治策略的。对于输入的子序列L[p..r],如果规模足够小则直接进行排序,否则分三步处理:
分解(Divide):将输入的序列L[p..r]划分成两个非空子序列L[p..q]和L[q+1..r],使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。 递归求解(Conquer):通过递归调用快速排序算法分别对L[p..q]和L[q+1..r]进行排序。 合并(Merge):由于对分解出的两个子序列的排序是就地进行的,所以在L[p..q]和L[q+1..r]都排好序后不需要执行任何计算L[p..r]就已排好序。 public class Sort ...{
/**//* * 交换算法 */ public static void swap(int a[], int i, int j) ...{ int tmp = a[i]; a[i] = a[j]; a[j] = tmp; }
// 选择排序法 public void sortSelection(int[] vec) ...{ long begin = System.currentTimeMillis(); // k次循环,增加运算时间. for (int k = 0; k < 1000000; k++) ...{ for (int i = 0; i < vec.length; i++) ...{ for (int j = i; j < vec.length; j++) ...{ if (vec[j] < vec[i]) ...{ swap(vec, i, j); } } } } long end = System.currentTimeMillis(); System.out.println("选择法用时为:" + (end - begin)); for (int i = 0; i < vec.length; i++) ...{ System.out.println(vec[i]); } }
// 冒泡排序法 public void sortBubble(int[] vec) ...{ long begin = System.currentTimeMillis(); for (int k = 0; k < 1000000; k++) ...{ for (int i = 0; i < vec.length; i++) ...{ for (int j = i; j < vec.length - 1; j++) ...{ if (vec[j + 1] < vec[j]) ...{ swap(vec, j + 1, j); } } } } long end = System.currentTimeMillis(); System.out.println("冒泡法用时为:" + (end - begin)); for (int i = 0; i < vec.length; i++) ...{ System.out.println(vec[i]); } }
// 插入排序法 public void sortInsertion(int[] vec) ...{ long begin = System.currentTimeMillis(); for (int k = 0; k < 1000000; k++) ...{ for (int i = 1; i < vec.length; i++) ...{ int j = i; while (vec[j - 1] > vec[j]) ...{ vec[j] = vec[j - 1]; j--; if (j <= 0) ...{ break; } } vec[j] = vec[i]; } } long end = System.currentTimeMillis(); System.out.println("插入法用时为:" + (end - begin)); for (int i = 0; i < vec.length; i++) ...{ System.out.println(vec[i]); } } public int partition(int a[],int low,int high)...{ int pivot,p_pos,i; p_pos=low; pivot=a[p_pos]; for(i=low+1;i<=high;i++)...{ if(a[i]<pivot)...{ p_pos++; swap(a,p_pos,i); } } swap(a,low,p_pos); return p_pos; }
public void quicksort(int a[],int low,int high)...{ int pivot; if(low<high)...{ pivot=partition(a,low,high); quicksort(a,low,pivot-1); quicksort(a,pivot+1,high); } } //快速排序法 public void sortQuick(int[] vec)...{ long begin=System.currentTimeMillis(); for(int k=0;k<1000000;k++)...{ quicksort(vec,0,5); } long end=System.currentTimeMillis(); System.out.println("快速法用时为:" + (end - begin)); for (int i = 0; i < vec.length; i++) ...{ System.out.println(vec[i]); } } /** *//** * @param args */ public static void main(String[] args) ...{ // TODO Auto-generated method stub int[] vec = new int[] ...{ 37, 47, 23, -5, 19, 56 }; Sort sort = new Sort(); sort.sortSelection(vec); sort.sortBubble(vec); sort.sortInsertion(vec); sort.sortQuick(vec);
}
}
本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/zdwzzu2006/archive/2008/04/07/2255867.aspx
|