排序——交换排序

在上篇文章我们详细介绍了排序的概念与插入排序,大家可以通过下面这个链接去看:

排序的概念及插入排序

这篇文章就介绍一下一种排序方式:交换排序。

一,交换排序

基本思想:两两比较,如果发生逆序则交换,直到所有记录都排好序为止。

而交换排序又分为两种:

        冒泡排序O(n2)

快速排序O( nlog2n )

1,冒泡排序

A 基本内容

学习过C语言的朋友应该对这个比较熟悉,其基本思想就是:  

每趟不断将记录两两比较,并按“前小后大” 规则交换

如图进行一次冒泡排序的过程:

21254925*16,  08

212525*1608 49

21251608 25*49

211608 2525*49

1608 212525*49

0816212525*49

 冒泡排序的优点:

每趟结束时,不仅能挤出一个最大值到最后面位置,还能同时部分理顺其他元素; 

    一旦下趟没有交换,还可提前结束排序

在c语言的代码中实际就是通过两个for循环来实现 

void main() 			 
{	int a[11];		/*a[0]不用,之用a[1]~a[10]*/
	int i,j,t;
	printf("\nInput 10 numbers: \n");
	for(i=1;i<=10;i++)	scanf("%d",&a[i]);	printf("\n");
	for(j=1;j<=9;j++)
	    for(i=1;i<=10-j;i++)
	      if(a[i]>a[i+1])	{t=a[i];a[i]=a[i+1];a[i+1]=t;}//交换
	for(i=1;i<=10;i++)	printf("%d ",a[i]);   
}

下面是一个例子 

下面这段代码与上面的区别是,当遇见数组部分有序时,可以提前结束循环,节省不必要的时间。

  1. 定义了一个名为bubble_sort的函数,接受一个顺序表L作为参数。
  2. 初始化变量m为顺序表的长度减1,flag为1,表示是否需要继续排序。
  3. 使用while循环进行排序,条件是m > 0flag == 1。当m等于0时,说明已经遍历完所有元素;当flag为0时,说明在一次循环中没有发生任何交换,说明已经排序完成。
  4. while循环内部,使用for循环遍历顺序表中的元素,从第一个元素到第m个元素。
  5. for循环内部,比较当前元素L.r[j].key和下一个元素L.r[j+1].key的大小。如果当前元素的键值大于下一个元素的键值,则交换这两个元素的位置,并将flag设置为1,表示发生了交换。
  6. 每次循环结束后,将m减1,缩小未排序部分的范围。
  7. while循环结束时,顺序表L中的元素已经按照升序排列。
void bubble_sort(SqList &L)
 { int m,i,j,flag=1;   RedType x;
   m=n-1;
   while((m>0)&&(flag==1))
   {  flag=0;
      for(j=1;j<=m;j++)
         if(L.r[j].key>L.r[j+1].key)
          {  flag=1;
             x=L.r[j];L.r[j]=L.r[j+1];L.r[j+1]=x; //交换
           }//endif
      m--;
    }//endwhile
 }

B 冒泡排序的算法分析:

设对象个数为 n 
比较次数 移动次数 与初始排列有关

最好情况下: 只需 1趟排序,比较次数为 n-1,不移动  

while((m>0)&&(flag==1))
   {  flag=0;
      for(j=1;j<=m;j++)
        if(L.r[j].key>L.r[j+1].key)
          {  flag=1;  x=L.r[j];L.r[j]=L.r[j+1];L.r[j+1]=x; } 
             ……     

最坏情况下: n-1趟排序,第i趟比较n-i次,移动3(n-i) 

冒泡排序

时间复杂度为 o(n2) 

空间复杂度为 o(1)

是一种稳定的排序方法

2,快速排序

A 基本内容

基本思想:

任取一个元素 ( 如第一个 ) 为中心
所有比它 的元素一律前放,比它 的元素一律后放,形成 左右两个子表
对各子表重新选择 中心 元素并依此规则调整,直到每个子表的元素 只剩一个

 在数组中,我们通过两个指针来实现排序过程

 后面也是一样的操作,我们会发现每趟子表的形成从两头向中间交替式逼近,对各子表操作相似,因此我们可采用递归算法来实现对数据的排序过程。

// 快速排序算法
void main()
{
    QSort(L, 1, L.length); // 对数组L进行快速排序
}

// 快速排序函数,参数为待排序的数组L,起始下标low和结束下标high
void QSort(SqList &L, int low, int high)
{
    if (low < high)
    {
        pivotloc = Partition(L, low, high); // 获取基准元素的位置
        QSort(L, low, pivotloc - 1);       // 对基准元素左边的子数组进行快速排序
        QSort(L, pivotloc + 1, high);      // 对基准元素右边的子数组进行快速排序
    }
}

// 划分函数,参数为待排序的数组L,起始下标low和结束下标high
int Partition(SqList &L, int low, int high)
{
    L.r[0] = L.r[low]; // 将第一个元素作为基准元素
    pivotkey = L.r[low].key;
    while (low < high)
    {
        // 从右向左找到第一个小于基准元素的下标
        while (low < high && L.r[high].key >= pivotkey)
            --high;
        L.r[low] = L.r[high]; // 将找到的元素放到左边

        // 从左向右找到第一个大于基准元素的下标
        while (low < high && L.r[low].key <= pivotkey)
            ++low;
        L.r[high] = L.r[low]; // 将找到的元素放到右边
    }
    L.r[low] = L.r[0]; // 将基准元素放到正确的位置
    return low;        // 返回基准元素的下标
}

 B 快速排序的算法分析:

 最好情况:划分后,左右子序列长度相同

最坏情况:递归树成为单支树 

到此交换排序就结束了, 如果文章对你有用的话请点个赞支持一下吧!

下篇文章将更新选择排序的内容。

上一篇:Windows图形界面(GUI)-SDK-C/C++ - 控件基本概念 - 消息处理机制


下一篇:LabVIEW扬尘控制系统