首页 > 代码库 > 深入浅出交换类排序算法(转)

深入浅出交换类排序算法(转)

1)冒泡排序

  冒泡排序在众多排序算法中算比较简单的一个,基本思想是重复的进行整个数列的排序,一次比较两个元素(两两排序),如果它们顺序不符合就交换,重复这样直到数列没有再需要交换的数为止(结束条件)。就好像气泡一样,轻的气泡会往上漂浮,在不断漂浮的过程中,发生了两两交换过程,所以叫冒泡排序。

技术分享

  其实也可以用生活中的例子理解,就比如: 在军训排队时,按个子高的和个子矮的的顺序进行排列,个子高的和个子矮的会进行两两进行比较。

  我们来大致看下算法的流程:

  选一组序列 4, 3 , 5, 6, 2, 1 (极端情况)

  从头开始进行冒泡排序,1号和2号进行交换,4 > 3, 所以需要进行交换:

  -> 3, 4, 5, 6, 2, 1

  2号和3号进行交换,4<5,不交换

  -> 3, 4, 5, 6, 2, 1

  3号和4号进行交换,5<6,不交换

  -> 3, 4, 5, 6, 2, 1

  4号和5号进行交换,6>2,交换

  -> 3, 4, 5, 2, 6, 1

  5号和6号进行交换,6>1,交换

  -> 3, 4, 5, 2, 1, 6

  第一轮冒泡排序结束,把最大的数交换到最后一位,如此循环,直到没有需要交换的元素为止,冒泡排序才结束。

  代码实现如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void BubbletSort(int*a,int len) {
    int m;
    for (bool bSwap=true; bSwap; len--) {
        bSwap = false;
        for (int j=1;j<len;j++) {
            if (a[j-1]>a[j]) {   // 交换值
                m=a[j];
                a[j]=a[j-1];
                a[j-1]=m;
                bSwap=true;
            }
        }
    }
}

  其实冒泡排序整体看来是非常"傻"的,有很多可以优化的余地。比方说,每次比较如果发现较小的元素在后面,就交换两个相邻的元素,而如果我只扫描元素,记下最小元素,等一次扫描完后,再交换两者为止,这样最小元素就排到了前面,每扫描一次,只需要一次真正的交换,而刚才的冒泡可能需要交换多次,刚才说的算法优化其实就是选择排序,以后我会细说,他属于选择排序的范畴。

  我们来考虑下冒泡算法的复杂度:

  在时间复杂度上,若待排序的序列为完全逆序,则每次都需要进行元素之间的交换,所以时间复杂度为O(技术分享 技术分享  ),若待排序为顺序,也就是不需要交换元素,但是需要扫描,所以还是需要O(技术分享)的时间复杂度,平均情况下时间复杂度为O(技术分享技术分享) 。

  在空间复杂度上,需要辅助空间只有一个m(如上面代码),所以空间复杂度为O(1)。

  2) 快速排序

  如果大家还记得折半插入排序的过程:在一个有序序列中,插入关键字和折半序列的中间关键字进行比较,若小则在关键字左边,若大则在关键字右边。而快速排序和折半插入排序有异曲同工之妙,差别在于折半插入排序插入的序列自身是个有序序列,选取中间关键字时两边已经有序。而快速排序在于它不一定是有序的,它的操作过程是:随便选取一个关键字(一般选取第一个),让所有关键字和它进行比较一次,小的放在左边,大的放在它右边,然后递归地对左边和右边进行排序。把该区间内的所有数依次与关键字比较,我们就可以在线性的时间里完成分割的操作。

  我们来看下算法的步骤:

  初始状态:            【49,38,65,97,76,13,27,49‘】
  一次划分后:         【27,38,13】 49 【76,97,65,49‘】
  分别进行快速排序:  【13】 27 【38】 【49‘,65】76【97】
  有序序列:             【13,27,38,49,49‘,65,76,97】

  上面是算法的大致步骤,一般完成分割操作有很多有技巧性的实现方法,比如最常用的一种是定义两个指针,一个从前往后找找到比关键字大的,一个从后往前找到比关键字小的,然后两个指针对应的元素交换位置并继续移动指针重复刚才的过程。这只是大致的方法,具体的实现还有很多细节问题。

  我们来看一下一轮快排序的细节步骤:

  原始序列(i和j分别指向序列的最低和最高位置):


技术分享

  选取第一个数49作为比较排序关键字。

  1、使用j,从序列最右端开始扫描遇到比49小的则停止。


技术分享

  2、将27交换到i的位置


技术分享

  3、使用i,从序列最左端开始扫描遇到比49大的数则停止


技术分享

  4、将65交换到j的位置


技术分享

  5、再使用j向前扫描遇到比49小的13停止,并把13交换到i位置。


技术分享

  6、使用i向后扫描遇到比49大的97停止,并交换到j的位置

技术分享

  7、继续使用j向前扫描遇到比49小的并停止,这时发现i和j相遇,代表扫描结束。


技术分享

  8、最后把49放置在ij的位置


技术分享

  从上面的一轮快排可以看出,49把整个序列划分为两个部分,小于49的在它左边,大于49的在它右边。根据算法思想再分别把49两边的序列进行快排一次。另外从整个排序过程来看,先对整个序列进行一次快排,然后再对其中子序列再进行快排,如此反复直到有序为止,整个过程是个递归的思想。所以代码比较好写,我们来实现一下。

?
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
28
29
30
31
32
33
34
// head=>序列的开头
// tail=>序列的结尾
void quickSort(int array[], int head, int tail) {
    if (head > tail) {
        return;
    }
    // i,j指向头和尾巴
    int i=head;
    int j=tail;
    int iPivot=array[i]; /**< 选取枢轴 */
    while (i<j) {
        // 使用j,从序列最右端开始扫描,直到遇到比枢轴小的数
        while ((i<j) && (iPivot <= array[j])) {
            j--;
        }
        // 交换位置
        if (i<j) {
            array[i++]=array[j];
        }
        // 使用i,从序列最左端开始扫描,直到遇到比枢轴小的数枢轴大的数
        while ( (i<j) && (array[i] <= iPivot) ) {
            i++;
        }
        // 交换位置
        if (i<j) {
            array[j--]=array[i];
        }
    }
    // 最后填入枢轴位置
    array[j]=iPivot;
    // 这里就是对枢轴两边序列进行排序的递归调用
    quickSort(array, head, i-1);
    quickSort(array, i+1, tail);
}

  代码已经严格测试过,一般不会有问题。下面我们来看下时间复杂度空间复杂度。

  快速排序有个特点,待排序列越接近无序,算法效率越高,也就是在基本有序的情况下时间复杂度为O(技术分享技术分享),最好情况下为O(技术分享技术分享技术分享技术分享 技术分享 技术分享),平均复杂度为O(技术分享技术分享技术分享技术分享 技术分享 技术分享),从所有内排序来看,快排是所有内排序中平均复杂度最好的,另外空间复杂度也为O(技术分享 技术分享)。因为上面的算法实现是递归进行的,递归需要栈空间。

 

 

http://kb.cnblogs.com/page/185060/

深入浅出交换类排序算法(转)