胡言乱语之交换排序

it2022-05-05  152

废话不多说直接开始

第三种武功:交换排序

 

 

  交换排序分为两类,冒泡排序(BubbleSort)和快速排序(QuickSort)。

一、算法实现思想;

  BubbleSort算法实现思想:

      两两比较相邻记录的关键码,如果反序则交换。直到所有记录顺序为止。

  QuickSort算法实现思想:

     首先选择一个轴值(一般选平均值,我们这里选数组的第一个值)作为比较基准。将待排序的记录分割成两部分。左侧记录的关键码均小于轴值,右侧记录的关键码均大    于轴值。进过若干次调整直到整个序列有序为止。

二、关于算法的思考,以及执行步骤的区分;

      BubbleSort算法实现分解

             在一趟冒泡排序中若干个记录位于最终为止如何调整?

                在每一次的比较中,会逐步筛选下去。每次都是选择最大的记录后移。而且一次排序结束后又标志位标记。 

            如何确定每一次冒泡的范围,使得已经位于最终位置的记录不参与下一趟排序?

                设置标志位,使得每次排序过程中最后一次的交换位置存放到暂存变量exchange中。

            如何判定冒泡排序的结束?

               判定当前的暂存值是否为零。

      QuickSort算法实现

          如何有效的选择轴值?

            一般情况下,算法的性能根据实际情况不同而不同,一般选择整个序列的平均值。本程序选择数组的一个元素

         如何进行一次划分?

            以轴值交换位置作为标准,将记录关键码小于轴值得存放在左边,将记录关键码大于轴值得放在右边。

        如何判别排序结束?

            进行递归划分直到所有的记录有序。

三、对算法的具体代码实现(JAVA,C++);

冒泡排序的C++代码实现

* * 交换排序之冒泡排序 * 前置条件:无顺序的一个数组 * 输 入:数组以及数组长度 * 处 理:对数组完成冒泡排序 * 输 出:有序数组 * 后置条件:无 */ void BubbleSort(int r[],int n) { int exchange=n; int temp; while(exchange) { int bound=exchange; exchange=0; for(int i=0;i<bound;i++) { if(r[i]>r[i+1]) { temp=r[i+1]; r[i+1]=r[i]; r[i]=temp; exchange=i; } } } }

 

快速排序的C++代码实现

/* * 交换排序之一次划分 * 前置条件:无顺序的一个数组 * 输 入:数组以及数组起始位置和终止位置 * 处 理:进行一次划分 * 输 出:轴值的位置 * 后置条件:无 */ int Partition(int r[],int first,int end) { int i=first; int j=end; int temp; while(i<j) { while(i<j&&r[i]<r[j])//左边开始 i++; if(i<j) { temp=r[i]; r[i]=r[j]; r[j]=temp; j--; } while(i<j&&r[i]<r[j])//右边开始 j--; if(i<j) { temp=r[i]; r[i]=r[j]; r[j]=temp; i++; } } return i; } /* * 交换排序之快速排序 * 前置条件:无顺序的一个数组 * 输 入:数组以及数组起始位置终止位置 * 处 理:对数组完成快速排序 * 输 出:有序数组 * 后置条件:无 */ void QuickSort(int r[],int first,int end) { if(first<end) { int pivot=Partition( r,first, end); QuickSort( r, first,pivot-1); QuickSort( r,pivot+1, end); } }

 

 

 

四、时间空间、效率、稳定性分析:

排序类型

快速排序(QuickSort)

冒泡排序(BubbleSort)

最好执行时间

O(nlog2n)

O(n)

最坏执行时间

O(n2)

O(n2)

平均执行时间

O(nlog2n)

O(n2)

额外辅存空间

1

-------

稳定性

不稳定

稳定

 

    

五、实际应用;

快速排序时已知性能最好的排序算法,UNIX系统中的qsort()函数基于快速排序实现。应用于记录个数多,随机排列的待排序序列中。

参考文献:算法导论

 

 

 

转载于:https://www.cnblogs.com/sunny-shiny/p/3871064.html

相关资源:DirectX修复工具V4.0增强版

最新回复(0)