[快速排序和选择排序1.pptVIP

* * * * * * * * * * * * * * * * * 第10章 内部排序 10.1 排序的基本概念 10.2 插入排序 10.3 交换排序 10.4 选择排序 10.5 归并排序 10.6 基数排序 10.7 各种内部排序方法的比较 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 10.3 交换排序 1. 起泡排序 2. 快速排序 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 1）起泡排序的基本思想 小的浮起，大的沉底 具体做法： 第一趟：第1个与第2个比较，大则交换；第2个与第3个 比较，大则交换，… 关键字最大的记录交换 到最后一个位置上； 第二趟：对前n-1个记录进行同样的操作，关键字次大 的记录交换到第n-1个位置上； 依次类推，则完成排序。 1.起泡排序 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 36 25 11 第 六 趟 36 41 25 11 第 五 趟 36 41 49 11 25 第 四 趟 41 36 56 11 49 25 第 三 趟 65 36 41 11 56 49 25 第 二 趟 11 36 41 65 78 49 56 25 第 一 趟 11 36 41 65 78 49 56 25 初 始 状 态 起 泡 排 序 示 例 49 56 11 78 78 65 78 41 78 36 56 11 65 41 65 36 49 11 56 41 56 36 25 11 49 41 49 36 41 36 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. void Bubblesort(ElemType R[],int n) { int flag=1; //当flag为0则停止排序 for (int i=n; i1; i--) { //i表示趟数，最多n-1趟 flag=0; //开始时元素未交换 for (int j=2; j=i; j++) if (R[j]R[j-1]) { //发生逆序 temp=R[j]; R[j]=R[j-1]; R[j-1]=temp; flag=1; } if(flag==0) return; } } // Bubblesort 2）起泡排序算法描述 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 正序： 只需进行一趟排序，在排序过程中进行n-1次关键字间的比较，且不移动记录；时间复杂度为O(n) 。 逆序： 需要进行n-1趟排序，需要进行n(n-1)/2次比较，并作等数量级的记录移动。总的时间复杂度为O(n2) 。 起泡排序方法是稳定的。适合于数据较少的情况。 3）起泡排序算法分析 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 2.快速排序 背景 起泡排序的过程可见，起泡排序是一个增加有序序列长度的过程，也是一个缩小无序序列长度的过程，每经过一趟起泡，无序序列的长度只缩小 1。 试设想：若能在经过一趟排序，使无序序列的长度缩小一半，则必能加快排序的速度。 Evaluation only. Created with Aspose.Slides for .NET 3.5 C