排序——交换排序

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

排序的概念及插入排序

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

一，交换排序

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

而交换排序又分为两种：

冒泡排序O(n2)

快速排序O( nlog2n )

1，冒泡排序

A 基本内容

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

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

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

21，25，49， 25*，16， 08

21，25，25*，16， 08 ， 49

21，25， 16， 08 ，25*，49

21，16， 08 ，25， 25*，49

16，08 ，21， 25， 25*，49

08，16， 21， 25， 25*，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]);   
}

下面是一个例子

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

定义了一个名为bubble_sort的函数，接受一个顺序表L作为参数。
初始化变量m为顺序表的长度减1，flag为1，表示是否需要继续排序。
使用while循环进行排序，条件是m > 0且flag == 1。当m等于0时，说明已经遍历完所有元素；当flag为0时，说明在一次循环中没有发生任何交换，说明已经排序完成。
在while循环内部，使用for循环遍历顺序表中的元素，从第一个元素到第m个元素。
在for循环内部，比较当前元素L.r[j].key和下一个元素L.r[j+1].key的大小。如果当前元素的键值大于下一个元素的键值，则交换这两个元素的位置，并将flag设置为1，表示发生了交换。
每次循环结束后，将m减1，缩小未排序部分的范围。
当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;        // 返回基准元素的下标
}