专注细节
努力进步

交换排序

利用交换数据元素的位置进行排序的方法称作叫换排序,常用的交换排序包括冒泡排序方法和快速排序方法。

1,冒泡排序

冒泡排序的基本思想是:第一次时,设数组a中存放了n和数据元素,循环进行n-1次比较相邻两个元素大小,若前一个大于后一个则交换,这样作为n-1次后,最大的元素就放置在a[n-1]中,第二次同理最大元素放置到a[n-2]中,以此类推,当n-1次排序后,数组能够得到排序。冒泡法的一个优化,通过设计一个flag变量,flag常量用于标记本次过程是否有交换动作,若没有交换动作则证明已经排序完成,无需后续操作。

冒泡排序代码文件

2,快速排序

快速排序是一种二叉树结构的交换排序方法,其基本思想是:设数组a中存放了n个数据元素,low为数组的低端下标,high为数组的高端下标,从数组a中人去一个元素通常取a[low]作为标注,调整数组a中各个元素的位置,使排在标准元素前面的关键字均小于标准元素的关键字,排在标准元素后面的关键字均大于后者等于标准元素的关键字,这样一次排序过程后,一方面将标准元素放在了未来排好序的位置,另一方面,将数组中以该标准元素分为两个子数组,左边的均小于标准值,右边的均大于标准值,然后对这两个子数组中的元素分别进行相同的递归快速排序,递归的出口条件是high>low。

快速排序我认为最重要的部分,我认为是如何把数组分成比标准元素小的和比标准元素大的两个部分。 即代码中的这部分,一定要记住思路,机试什么的要写出来:

while (first<last)
{
while(first<last&&a[last]>=temp)//从后到前,找到第一个比标准元素小的
–last;
a[first]=a[last];
while(first<last&&a[first]<=temp)//从前到后,找到第一个比标准元素大的
++first;
a[last]=a[first];
}

快速排序代码文件

分享到:更多 ()