交换排序

Posted on | In | Visitors:

目录：

  • 起泡排序

  • 快速排序

起泡排序

概述

首先将第一个元素与第二个元素比较，如果为逆序，则交换之，然后比较第二个元素和第三个元素。以此类推，直至第n-1个元素和第n个元素比较后。一趟起泡排序完成，结果是使得一组元素的最大值（或最小值）放置到最后一个位置。然后进行第二趟起泡排序，对前n-1个元素进行类似的操作，使得次大（或者次小）的元素放置到倒数第二个位置上。整个排序过程需进行k（1<=k< n）趟起泡排序。判别起泡排序结束的标志是“在一趟起泡排序中没有发生元素的交换”。

实现(从小到大)

最最最初级版：

1
2
3
4
5
6
7
8
9
10
11
12
13
void swap(int &a,int &b){
    int temp = a;
    a = b;
    b = temp;
}
void BubbleSort1(int a[],int n){
    for(int i = 0;i<n-1;i++){
        for(int j = i+1;j<n;j++){
            if(a[i]>a[j])
                swap(a[i],a[j]);
        }
    }
}

为什么说是最最最初级版的呢？因为它根本就不满足“相邻两两交换”的思想，只可以说是最简单的交换排序并且效率也并不高。因为它并没有对后面的操作有任何帮助,并且还将次小的元素放到了最后一个

下面看下正宗的冒泡排序：

1
2
3
4
5
6
7
8
void BubbleSort2(int a[],int n){
	for(int i = 0;i<n-1;i++){
		for(int j = n-2;j>=i;j--){
			if(a[j]>a[j+1])
				swap(a[j],a[j+1]);
		}
	}
}

j反向循环，将较小的记录交换到前面，如图，不仅将最小值1放到首位，还将次小值2提前。

但这还不是最优，考虑一种情况：当初始序列基本有序时，或者只需要进行1次交换就可以满足整体有序时。用上述的方法，显然后面的几次循环比较都是徒劳的，因为一次循环就满足了。
在最开始我们说过，冒泡排序的结束标志是在一趟排序中没有发生元素交换，下面上冒泡排序的终极版：

1
2
3
4
5
6
7
8
9
10
11
12
void BubbleSort3(int a[],int n){
	bool flag = true;
	for(int i = 0;i<n-1 && flag;i++){
		flag = false;
		for(int j = n-2;j>=i;j--){
			if(a[j]>a[j+1]){
				swap(a[j],a[j+1]);
				flag = true;
			}
		}
	}
}

完整测试代码见本人GitHub

复杂度

容易看出，如果原记录顺序，则只需进行一趟起泡排序，进行n-1次比较，无需移动元素；反之，如果原记录逆序，则需要进行n-1趟起泡排序，共进行n*(n-1)/2次记录的比较（用梯形公式可计算出），并做等量的移动。因此总的时间复杂度为O(n^2)。

快速排序

概述


快速排序是对起泡排序的一种改进。它的基本思想是：通过一趟排序，将待排记录分割成独立的两部分，其中一部分的元素均比另一部分小，然后分别对这两部分继续进行排序，以达到整个序列有序。

假设待排序列为{a[s],a[s+1],a[s+2]…a[t]}。首先任意选取一个记录作为枢轴（一般选最后一个元素）,然后按以下规则重排其余记录：将所有元素比它小的都放在它之前，比它大的都放在它之后。由此可见最后枢轴位置i作该序列的分界线，将序列{a[s],a[s+1],a[s+2]…a[t]}分割成两个子序列{a[s],a[s+1]…a[i-1]},{a[i+1],a[i+2]…a[t]}。这个过程称作一趟快速排序。

一趟快速排序的具体做法如下：

设两个指针left和right，指向待排区间的第一个元素和最后一个元素，初始设枢轴元素为待排区间的第一个记录，首先从right所指的位置其向前搜索找到第一个right位置使得a[right] < a[left]（即小于枢轴元素），则交换a[left]和a[right],left加一，（此时枢轴元素为a[right]）然后从left位置其向后搜索找到第一个left位置使得a[left]>a[right]，交换a[left]与a[right],right加一，(此时a[left]为枢轴元素)。重复以上步骤直到left==right，此时left（或right）所指位置即为枢轴元素的最终位置。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//法一
int Partition(int a,int left,int right){
    int i = left,j = right;
    while(i<j){
        while(i<j && a[j]>=a[i])
            j--;
        if(i<j){
            swap(a[i],a[j]);
            i++;
        }
        while(i<j && a[i]<=a[j])
            i++;
        if(i<j){
            swap(a[i],a[j]);
            j--;
        }
    }
    return i;

}
void QuickSort(int a[],int low,int heigh){
    if(low < heigh){
        int pivotloc = Partition(a,low,heigh);
        QuickSort(a,low,pivotkloc-1);
        QuickSort(a,pivotloc+1,heigh);
    }
}

完整测试代码见本人GitHub

复杂度

在所有同数量级的排序方法中，就平均时间而言，快速排序是被认为最好的一种内部排序方法。时间复杂度可达O(n*logn)。但若初始序列有序或基本有序时，快速排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取基准记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。

参考资料：
《大话数据结构——程杰》
《数据结构——从概念到C实现》
注：原著中有疑问的地方，经本人上机调试验证后，在博客中已进行更改