排序一冒泡选择快速

《排序一冒泡选择快速》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、排序一：冒泡排序、选择排序、快速排序厦门六中肖海排序（sort）是很常见的操作，是编程的基本功。排序就是将数据按一定的顺序重新排列，排序的基础是不断的比较以及交换数据的位置。排序的方法和策略有多种，以下假设数据保存在A[n]数组里，并且排序的顺序为升序。一、冒泡排序(BubbleSort)1.1、主要策略：不断地比较相邻的两个元素，并让相邻的两个元素保持有序。让J从1到N－1循环扫描A[J]，并检查A[j]以及紧接其后A[j+1]的数值，若A[j]>A[j+1]就让A[j]与A[j+1]交换数据，这样A[j]就比A[j+1]小，A[j]和A[j+1]就是升序了。注意

2、这样不能保证A[j]与其前面的A[j-1]是否有序。上述J从1到N－1循环扫描A[J]，让相邻的两个元素保持有序，这叫一轮扫描比较。这一轮扫描，有部分数据经过与相邻元素交换后为比原先更接近他应该在的位置了。重复多轮的轮扫描比较，直到整轮比较都没有元素进行交换，说明大功告成了。1.2、优化：每次交换时，小的数只向前移动一个位置，但大的数会跟着扫描往下沉，因此每轮扫描后最大的数一定沉到最后，但小的数只移动一个位置。这样每轮扫面可以比上轮扫描少比较一个元素。我们可以确定经过n-1轮的扫描就能排好顺序。另外的优化就是检测在一轮扫描过程中如果没有发生交换，那就可以结束排序。双

3、向冒泡优化，每轮扫描最大的沉底，如果第一轮从1到n-1扫描，第2轮从n-1到2反向扫描，如此一正一反的双向冒泡也能大大提高排序速度。1.3、程序片断：（未优化）Fori:=1Ton-1do｛需要进行n-1轮扫描。思考为什么只要n-1轮｝Forj:=1ton-Idobegin｛准备一轮扫描。为什么只扫描到n-I，而不是n-I+1｝Ifa[j]>a[j+1]thenbegin｛a[j]与a[j+1]顺序不对，需要交换数值｝temp:=a[j];｛a[j]与a[j+1]交换数值｝a[j]:=a[j+1];a[j+1]:=temp;End;End;｛这是未经优化的程序｝1.

4、4、优缺点：思路简单，比较和交换的操作太频繁了速度很慢。1.5、排序过程演示：下标0123456数值57832比较57832比较57832比较57832交换57382比较57382交换57328一轮57328比较57328比较57328交换53728比较53728交换53278二轮53278……一、选择排序（Selectionsort）2.1、主要策略：冒泡排序，交换的操作太频繁了，我们的策略改成每轮找出最小的数，然后把他与第1个元素交换。第1轮从A[1]到A[N]扫描找出最小的数，然后把他与A[1]交换。第2轮从A[2]到A[N]扫描找出最小的数，然后把他与A[2

5、]交换。依此类推2.2、优化：为了减少交换的次数，每轮扫描时记住最小数的位置，直到该轮扫描结束后才交换。2.3、程序片断：（未优化）Fori:=1Ton-1do｛需要进行n-1轮扫描｝Forj:=i+1tondobegin｛一轮扫描,该轮最小数保存在a[i]因此从i+1扫描｝Ifa[i]>a[j]thenbegin｛a[i]不是最小数，需要交换｝t:=a[j];a[j]:=a[i];a[i]:=t;｛a[i]与a[j]交换｝End;End;｛这是未经优化的程序｝2.4、排序过程演示：下标0123456数值57832比较57832比较57832比较57832交换378

6、52比较37852交换27853一轮27853比较27853交换27853比较25873比较25873交换23875二轮23875……二、快速排序（quicksort）3.1、主要策略：找一个数X，把A[]数组分成小于X和大于X的两边，再对这两边继续用这个方法做下去。分成两边后，剩下的数要比较的范围缩小了，比较的次数就大大减少，因此排序速度很快。分好的两边递归调用上述操作，递归到排序的范围内只有1个元素。3.2、优化：X必须是A[]数组中的数，X的确定有很多方法，其中一种是随机在A[]数组中取一个数，更常用的是在A[]数组最中间位置上的数。X是分界的基准。分成两边的

7、方法是，把左边大于X的数移到右边，把右边小于X的数移到左边。先在左边找到要移动的“大数”的位置，在右边找到要移动的“小数”的位置，然后把他们交换位置，同时解决了两边不符合要求的数的移动。3.3、注意事项基准数X虽然是从数组的中间位置取得的，但是分完后的左右两边的元素个数并不一样多，X数值也就不再是在中间的位置了，所以要用变量X来保存一开始得到的基准值。X需要被移动，因此在左右两边寻找“大数”“小数”时，碰到X也算“大数”“小数”或小数必须移动。X可能被归到左边或右边一组的任何位置，但是分完左右两边后，左边一组中的X是该组的最大数，将来会被移动该组的最右边。同理，